#include<stdlib.h> #include<stdio.h> struct node { int data; struct node *next; }; int main(){ struct node *start=NULL; printf("Hello, World!\n"); int n; while(1) { printf("1:insert/2:delete/3:search/4:print/else:end -> "); scanf("%d",&n); switch(n) { case 1:{ printf("Input: "); scanf("%d",&n); struct node *newa = (struct node*) malloc (sizeof(struct node)); newa->data=n; if(start==NULL){ newa->next=NULL; start=newa; } else if(n<=start->data){ newa->next=start; start=newa; } else{ } break; } case 2: break; case 3: break; case 4:{ printf("\n"); break; } default: printf("Bye, World!"); return 0; } } }

/*#define abs(x) (x>-(x)?x:-(x)) #include<stdio.h> int a[1002][1002]={},n,m; int r(int x,int y){ if(x==n&&y==m)return 1; int memo=a[x][y], min=2147483647, t; a[x][y]=0; if(a[x+1][y]&&abs(a[x+1][y]-memo)<2){ t=r(x+1,y); if(t&&t<min)min=t; } if(min==n+m-x-y)return min+1; if(a[x][y+1]&&abs(a[x][y+1]-memo)<2){ t=r(x,y+1); if(t&&t<min)min=t; } if(min==n+m-x-y)return min+1; if(a[x-1][y]&&abs(a[x-1][y]-memo)<2){ t=r(x-1,y); if(t&&t<min)min=t; } if(min==n+m-x-y)return min+1; if(a[x][y-1]&&y>1&&abs(a[x][y-1]-memo)<2){ t=r(x,y-1); if(t&&t<min)min=t; } if(min==n+m-x-y)return min+1; if(min==2147483647){ return 0; } if(min==n+m-x-y)return min+1; a[x][y]=memo; return min+1; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); a[i][j]++; a[i][j]=1; if(i+j==n)a[i][j]=3; } } printf("%d",r(1,1)); return 0; }*/ //놀이공원(실패) /*#include<stdio.h> int a[501][501]={},n; int sh[501]={},ta[501]={}; void sho(int x){ if(sh[x])return; sh[x]=1; for(int i=1;i<=n;i++){ if(a[x][i]){ sho(i); for(int j=1;j<=n;j++){ if(a[i][j])a[x][i]=1; } } } } void tal(int x){ if(ta[x])return; ta[x]=1; for(int i=1;i<=n;i++){ if(a[i][x]){ tal(i); for(int j=1;j<=n;j++){ if(a[j][i])a[j][x]=1; } } } } int main(){ int m,x,y,t=0; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&x,&y); a[x][y]=1; } for(int i=1;i<=n;i++){ sho(i); tal(i); } for(int i=1;i<=n;i++){ int r=1; for(int j=1;j<=n;j++){ if(a[i][j]||a[j][i])r++; } if(r==n)t++; } printf("%d",t); return 0; }*/ //키 순서 /*#include<stdio.h> int a[26][26]={},n,guchim[26]={},s,e; int minroad(int start,int nl){ printf("function started:%d %d\n",start,nl); if(start==e){printf("function ended:%d=>%d\n",e,0);return 0;} guchim[start]=1; int min=2147483647; for(int i=0;i<n;i++){ if(a[start][i]&&guchim[i]==0&&(nl+a[start][i]<=a[s][i]||a[s][i]==0)){ a[s][i]=nl+a[start][i]; a[i][s]=a[s][i]; int t=minroad(i,a[s][i]); if(a[i][e]<t||a[i][e]==0)a[i][e]=t; a[e][i]=a[i][e]; if(t==-1)continue; t+=a[i][start]; if(t<min)min=t; } } guchim[start]=0; printf("function ended:%d=>%d\n",start,min); if(min==2147483647)return -1; return min; } int main(){ int m,l; char x,y; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("\n%c %c %d",&x,&y,&l); a[x-'A'][y-'A']=l; a[y-'A'][x-'A']=l; } scanf("\n%c %c",&x,&y); s=x-'A'; e=y-'A'; printf("%d",minroad(s,0)); return 0; }*/ //최단 경로 1(실패)

/*#include<stdio.h> int n,m,a[20]={}; int x(int p,int q){ if(q==m){ if(p==0)return 1; return 0; } return x(p-a[q],q+1)+x(p+a[q],q+1); } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d",&a[i]); } printf("%d",x(n,0)); return 0; }*/ //덧셈, 뺄셈으로 n만들기 /*#include<stdio.h> int n,k,a[33]={1}; int sit(int p, int q){ int s=0; if(p+q>n+1){ }else if(q==0){ s=1; }else{ s=sit(p+1,q); if(p==1||(a[p-2]+a[p-1]<2&&a[p-1]+a[p+1]<2)){ a[p]=1; s+=sit(p+1,q-1); a[p]=0; } } return s; } int main(){ scanf("%d%d",&n,&k); a[n+1]=1; printf("%d",sit(1,k)); }*/ //극장 좌석 배치 3 /*#include<stdio.h> int main(){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); if((a-c)*(a-d)*(b-c)*(b-d)<0){ printf("cross"); }else{ printf("not cross"); } return 0; }*/ //케잌 자르기 /*#include<stdio.h> int n; int stair(int k,int t){ if(k<0)return 0; if(k==0)return 1; int s=stair(k-1,t-1); s+=stair(k-2,t-1); if(t<0)s+=stair(k-3,1); return s; } int main(){ scanf("%d",&n); printf("%d",stair(n,-1)); return 0; }*/ //숏다리의 계단 오르기(small) /*#include<stdio.h> int main(){ int n; scanf("%d",&n); int s=0; for(int i=1;i<(n+1)/2;i++){ for(int j=i;j<(n+1)/2;j++){ if(i+2*j<=n&&2*i+2*j>n)s++; } } printf("%d",s); }*/ //삼각형 화단 만들기 /*#include<stdio.h> int main(){ int n,k,x; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&x); if(x>=k){ printf("%d",i); return 0; } } printf("%d",n+1); return 0; }*/ //Lower Bound /*#include<stdio.h> int n,s,a[21]={}; int r(int x,int y){ if(x==n)return y?0:1; int z=r(x+1,y)+r(x+1,y-a[x]); return z; } int main(){ scanf("%d%d",&n,&s); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } if(s==0){ printf("%d",r(0,s)-1); }else{ printf("%d",r(0,s)); } return 0; }*/ //부분수열의 합 /*#include<stdio.h> int a,b,c,d,m=11; struct w{ int aa; int bb; }; struct w wa[11]={}; void water(int A,int B,int k){ if(k>=m)return; for(int i=0;i<k;i++){ if(wa[i].aa==A&&wa[i].bb==B)return; } if(A==c&&B==d&&k<m){ m=k; return; } wa[k].aa=A; wa[k].bb=B; water(a,B,k+1); water(A,b,k+1); water(0,B,k+1); water(A,0,k+1); int move=A<(b-B)?A:(b-B); water(A-move,B+move,k+1); move=B<a-A?B:a-A; water(A+move,B-move,k+1); wa[k].aa=0; wa[k].bb=0; } int main(){ scanf("%d%d%d%d",&a,&b,&c,&d); water(0,0,0); if(m==11){ printf("-1"); return 0; } printf("%d",m); return 0; }*/ //물통(tiny) /*#include<stdio.h> int a[9][9]={},s=0; int c(int x,int y,int f){ if(a[x][y]-f)return 0; a[x][y]=0; return 1+c(x-1,y,f)+c(x+1,y,f)+c(x,y+1,f)+c(x,y-1,f); } int main(){ for(int i=1;i<8;i++){ for(int j=1;j<8;j++){ scanf("%d",&a[i][j]); } } for(int i=1;i<8;i++){ for(int j=1;j<8;j++){ if(a[i][j]&&c(i,j,a[i][j])>2)s++; } } printf("%d",s); return 0; }*/ //캔디팡 /*#include<stdio.h> int a[102][102]={},b[102][102]={},s1=0,s2=0,m,n; void c(int x,int y){ if(a[x][y])return; a[x][y]=1; c(x-1,y); c(x+1,y); c(x,y+1); c(x,y-1); } void d(int x,int y){ if(b[x][y]==0)return; b[x][y]=0; d(x-1,y); d(x+1,y); d(x,y+1); d(x,y-1); } int main(){ scanf("%d%d",&m,&n); for(int i=0;i<m+2;i++){ for(int j=0;j<n+2;j++){ a[i][j]=1; } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ scanf("%d",&a[i][j]); b[i][j]=a[i][j]; } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(a[i][j]==0){ c(i,j); s1++; } if(b[i][j]){ s2++; d(i,j); } } } printf("%d %d",s1,s2); return 0; }*/ //전광판 전구 조작 /*#include<stdio.h> int a[21][21]={}; int omok(int x,int y,int xup,int yup,int color,int length){ if(length==6)return 0; if(a[x][y]!=color){ if(length==5)return 1; return 0; } return omok(x+xup,y+yup,xup,yup,color,length+1); } int main(){ for(int i=1;i<20;i++){ for(int j=1;j<20;j++){ scanf("%d",&a[i][j]); } } for(int i=1;i<20;i++){ for(int j=1;j<20;j++){ if(a[i][j]){ for(int xup=-1;xup<2;xup++){ for(int yup=-0;yup<2;yup++){ if(a[i-xup][j-yup]!=a[i][j]&&omok(i,j,xup,yup,a[i][j],0)){ printf("%d\n%d %d",a[i][j],i,j); return 0; } } } } } } printf("0"); return 0; }*/ //오목 /*#include<stdio.h> int a[1002][1002]={},n,m; int r(int bx,int by,int x,int y){ } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); a[i][j]++; } } printf("%d",) return 0; }*/ //놀이공원(푸는중)

/*#include <stdio.h> int home[313]={}; int danji=0,n; int a[26][26]={}; int bfs(int x,int y){ if(a[x][y]==0||x==-1||y==-1)return 0; a[x][y]=0; return bfs(x,y+1)+bfs(x,y-1)+bfs(x-1,y)+bfs(x+1,y)+1; } int main() { scanf("%d",&n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%1d",&a[i][j]); } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(a[i][j]){ home[danji]=bfs(i,j); danji++; } } } printf("%d\n",danji); for(int i=0;i<danji;i++){ int m=home[0]; int mi=0; for(int j=1;j<danji;j++){ if(home[j]<m){ m=home[j]; mi=j; } } printf("%d\n",m); home[mi]=999; } return 0; }*/ //단지 번호 붙이기 /*#include<stdio.h> int graph[101][101]={}; int q[100]={1}; int head=1,tail=0; int n,m,x,y; void virus(){ if(head==tail)return; int t=q[tail]; for(int i=1;i<=n;i++){ if(graph[t][i]){ int p=1; for(int j=tail;j<head;j++){ if(q[j]==i){ p=0; break; } } if(p){ q[head]=i; head++; } graph[t][i]=0; graph[i][t]=0; } } q[tail]=0; tail++; virus(); } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&x,&y); graph[x][y]=1; graph[y][x]=1; } virus(); printf("%d",head-1); return 0; }*/ //바이러스 /*#include<stdio.h> int a[1001][1001]={}; int qx[1000000]={}; int qy[1000000]={}; int n,m,day=0,head=0,tail=0,z=0; int main(){ scanf("%d%d",&m,&n); for(int i=0;i<n;i++){ a[i][m]=-1; for(int j=0;j<m;j++){ scanf("%d",&a[i][j]); if(a[i][j]==1){ qx[head]=i; qy[head]=j; head++; z++; }else if(a[i][j]==0){ z++; } } } for(int i=0;i<=m;i++){ a[n][i]=-1; } while(head-tail){ int x=qx[tail]; int y=qy[tail]; if(a[x+1][y]==0){ day=a[x][y]; a[x+1][y]=day+1; qx[head]=x+1; qy[head]=y; head++; } if(a[x-1][y]==0&&x){ day=a[x][y]; a[x-1][y]=day+1; qx[head]=x-1; qy[head]=y; head++; } if(a[x][y+1]==0){ day=a[x][y]; a[x][y+1]=day+1; qx[head]=x; qy[head]=y+1; head++; } if(a[x][y-1]==0&&y){ day=a[x][y]; a[x][y-1]=day+1; qx[head]=x; qy[head]=y-1; head++; } qx[tail]=0; qy[tail]=0; tail++; z--; } if(z){ printf("-1"); }else{ printf("%d",day); } }*/ //토마토(고등) /*#include<stdio.h> int a[100][100][100]= {}; int qx[1000000]= {}; int qy[1000000]= {}; int qz[1000000]= {}; int m,n,h,day=0,o,head=0,tail=0; int main() { scanf("%d%d%d",&m,&n,&h); o=m*n*h; for(int i=0; i<h; i++) { for(int j=0; j<n; j++) { for(int k=0; k<m; k++) { scanf("%d",&a[j][k][i]); if(a[j][k][i]==1) { qx[head]=j; qy[head]=k; qz[head]=i; head++; } else if(a[j][k][i]==-1) o--; } } } while(head-tail) { int x=qx[tail]; int y=qy[tail]; int z=qz[tail]; if(x-n+1&&a[x+1][y][z]==0) { day=a[x][y][z]; a[x+1][y][z]=day+1; qx[head]=x+1; qy[head]=y; qz[head]=z; head++; } if(x&&a[x-1][y][z]==0) { day=a[x][y][z]; a[x-1][y][z]=day+1; qx[head]=x-1; qy[head]=y; qz[head]=z; head++; } if(y-m+1&&a[x][y+1][z]==0) { day=a[x][y][z]; a[x][y+1][z]=day+1; qx[head]=x; qy[head]=y+1; qz[head]=z; head++; } if(y&&a[x][y-1][z]==0) { day=a[x][y][z]; a[x][y-1][z]=day+1; qx[head]=x; qy[head]=y-1; qz[head]=z; head++; } if(z-h+1&&a[x][y][z+1]==0) { day=a[x][y][z]; a[x][y][z+1]=day+1; qx[head]=x; qy[head]=y; qz[head]=z+1; head++; } if(z&&a[x][y][z-1]==0) { day=a[x][y][z]; a[x][y][z-1]=day+1; qx[head]=x; qy[head]=y; qz[head]=z-1; head++; } qx[tail]=0; qy[tail]=0; qz[tail]=0; tail++; o--; } if(o) { printf("-1"); } else { printf("%d",day); } return 0; }*/ //토마토(초등) /*#include<stdio.h> int a[11][11]={},b[10][10]={},r,c;//b:공개되면 1, 아니면 0 void ifb(int x,int y){ if(x==0||y==0||x==10||y==10||b[x][y])return; if(a[x][y]==9){ return; }else if(a[x][y]==0){ b[x][y]=1; ifb(x+1,y+1); ifb(x+1,y-1); ifb(x+1,y); ifb(x-1,y+1); ifb(x-1,y-1); ifb(x-1,y); ifb(x,y+1); ifb(x,y-1); }else{ b[x][y]=1; } } int main(){ for(int i=1;i<10;i++){ for(int j=1;j<10;j++){ scanf("%d",&a[i][j]); a[i][j]*=9; } } scanf("%d%d",&r,&c); if(a[r][c]==9){ for(int i=1;i<10;i++){ for(int j=1;j<10;j++){ if(i==r&&j==c){ printf("-1 "); }else{ printf("_ "); } } printf("\n"); } return 0; } for(int i=1;i<10;i++){ for(int j=1;j<10;j++){ if(a[i][j]-9){ if(a[i+1][j+1]==9)a[i][j]++; if(a[i+1][j-1]==9)a[i][j]++; if(a[i+1][j]==9)a[i][j]++; if(a[i-1][j+1]==9)a[i][j]++; if(a[i-1][j-1]==9)a[i][j]++; if(a[i-1][j]==9)a[i][j]++; if(a[i][j+1]==9)a[i][j]++; if(a[i][j-1]==9)a[i][j]++; } } } ifb(r,c); for(int i=1;i<10;i++){ for(int j=1;j<10;j++){ if(b[i][j]){ printf("%d ",a[i][j]); }else{ printf("_ "); } } printf("\n"); } }*/ //지뢰찾기 2 /*#include<stdio.h> int p[201]={0,1}; int P(n){ if(p[n])return p[n]; if(n==0)return 0; p[n]=(P(n-1)+P(n-2))%10009; return P(n); } int main(){ int n; scanf("%d",&n); printf("%d",P(n)); return 0; }*/ //피보나치수열 /*#include<stdio.h> int block(int n){ if(n==0)return 1; if(n%3)return 0; return (2*block(n-3))%100000007; } int main(){ int n; scanf("%d",&n); printf("%d",block(n)); }*/ //블럭 채우기 2 /*#include<stdio.h> int p[10001]={1,1}; int b(int n){ if(p[n])return p[n]; p[n]=(b(n-1)+2*b(n-2))%100007; return p[n]; } int main(){ int n; scanf("%d",&n); printf("%d",b(n)); }*/ //블럭 채우기 3 /*#include<stdio.h> int p[10001]={1,1,5}; int b(int n){ if(p[n])return p[n]; p[n]=(b(n-1)+4*b(n-2)+2*b(n-3))%100007; return p[n]; } int main(){ int n; scanf("%d",&n); printf("%d",b(n)); return 0; }*/ //블럭 채우기 4 /*#include<stdio.h> int p[10001]={0,1,2,6}; int b(int n){ if(p[n])return p[n]; p[n]=(b(n-1)+b(n-2)+3*b(n-3))%1000; return p[n]; } int main(){ int n; scanf("%d",&n); printf("%d",b(n)); return 0; }*/ //블럭 채우기 5 /*#include<stdio.h> int p[10001]={1,2,7}; int b(int n){ if(p[n])return p[n]; p[n]=(3*b(n-1)+b(n-2)-b(n-3))%100007; if(p[n]<0)p[n]+=100007; return p[n]; } int main(){ int n; scanf("%d",&n); printf("%d",b(n)); return 0; }*/ //블럭 채우기 6 /*#include<stdio.h> int p[10001]={1,0,3}; int b(int n){ if(n%2)return 0; if(p[n])return p[n]; p[n]=(4*b(n-2)-b(n-4))%100007; if(p[n]<0)p[n]+=100007; return p[n]; } int main(){ int n; scanf("%d",&n); printf("%d",b(n)); return 0; }*/ //블럭 채우기 7 /*#include<stdio.h> int p[10001]={0,1,5,11,36}; int b(int n){ if(n%2)return 0; if(p[n])return p[n]; p[n]=(4*b(n-2)-b(n-4))%100007; if(p[n]<0)p[n]+=100007; return p[n]; } int main(){ int n; scanf("%d",&n); printf("%d",b(n)); return 0; }*/ //블럭 채우기 8 점화식 못찾음

/*#include <stdio.h> #include<math.h> double cityr[10000]={}; int cityp[10000]={}; void swap(int l,int r){ double t=cityr[l]; cityr[l]=cityr[r]; cityr[r]=t; int tt=cityp[l]; cityp[l]=cityp[r]; cityp[r]=tt; } int piv(int begin,int end){ int p=begin; int l=begin+1; int r=end; while(l<r){ while(cityr[l]<=cityr[p]&&l<=r)l++; while(cityr[r]>=cityr[p]&&l<=r)r--; double t=cityr[l]; cityr[l]=cityr[r]; cityr[r]=t; int tt=cityp[l]; cityp[l]=cityp[r]; cityp[r]=tt; } if(cityr[p]>cityr[l]){ t=cityr[l]; cityr[l]=cityr[p]; cityr[p]=t; tt=cityp[p]; cityp[p]=cityp[l]; cityp[l]=tt; } return l; } void quick(int begin,int end){ if(begin>=end)return; int p=piv(begin,end); quick(begin,p-1); quick(p,end); return; } int main() { int n,p,x,y; scanf("%d%d",&n,&p); for(int i=0;i<n;i++){ scanf("%d%d%d",&x,&y,&cityp[i]); cityr[i]=sqrt(x*x+y*y); } quick(0,n-1); int i=0; for(i;i<n;i++){ p+=cityp[i]; if(p>=1000000){ printf("%.3lf",cityr[i]); return 0; } } printf("-1"); return 0; }*/ // 광역시 /*#include<stdio.h> char a[101][101]={}; void lake(int x,int y){ if(a[x][y]!='L')return; a[x][y]='.'; lake(x-1,y-1); lake(x,y-1); lake(x+1,y-1); lake(x+1,y); lake(x+1,y+1); lake(x,y+1); lake(x-1,y+1); lake(x-1,y); return; } int main(){ int w,h; char enter; scanf("%d %d",&w,&h); for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ scanf(" %c",&a[i][j]); } } int n=0; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ if(a[i][j]=='L'){ lake(i,j); n++; } } } printf("%d",n); return 0; }*/ //호수의 수 구하기 /*#include<stdio.h> int a[100][100]={}; int res[5000]={}; int lake(int x,int y){ if(a[x][y]==0)return 0; a[x][y]=0; return (lake(x-1,y)+lake(x+1,y)+lake(x,y-1)+lake(x,y+1)+1); } int main(){ int m,n,k,x1,x2,y1,y2,t; scanf("%d%d%d",&m,&n,&k); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ a[i][j]=1; } } for(int i=0;i<k;i++){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); for(int j=x1;j<x2;j++){ for(int ij=y1;ij<y2;ij++){ a[j][ij]=0; } } } int s=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]){ res[s]=lake(i,j); s++; } } } printf("%d\n",s); for(int i=1;i<s;i++){ for(int j=0;j<s-i;j++){ if(res[j+1]<res[j]){ t=res[j]; res[j]=res[j+1]; res[j+1]=t; } } } for(int i=0;i<s;i++){ printf("%d ",res[i]); } return 0; }*/ //영역 구하기 /*#include<stdio.h> int a[1001][1001]={}; int h[110][110]={}; void lake(int x,int y){ if(a[x][y]==0)return; if(x<0 || y<0 ) return; a[x][y]=0; lake(x-1,y); lake(x+1,y); lake(x,y-1); lake(x,y+1); } int main(){ int n,m=101,M=0; scanf("%d",&n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&h[i][j]); if(h[i][j]>M)M=h[i][j]; if(h[i][j]<m)m=h[i][j]; } } int s,S=0; for(int i=m;i<=M;i++){ s=0; for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ if(h[j][k]>=i)a[j][k]=1; printf("%d ", a[j][k]); } printf("\n"); } printf("\n"); for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ if(a[j][k]==1){ lake(j,k); s++; } } } if(s>S)S=s; } printf("%d",S); return 0; }*/ //안전 영역 /*# include<stdio.h> int a[1002][1002]={}; int b[1002][1002]={}; int h,w,z=0,day=1; int no(int x,int y){ if(x>h||y>w||x<=0||y<=0)return 0; if(b[x][y]==1)return 1; if(b[x][y]==0){ b[x][y]=-1; return no(x-1,y)+no(x+1,y)+no(x,y-1)+no(x,y+1); } if(b[x][y]==-1)return 0; } void go(int x,int y){ if(a[x][y]==0){ a[x][y]=day; z--; } } int main(){ scanf("%d%d",&w,&h); int yes=0; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ scanf("%d",&a[i][j]); b[i][j]=a[i][j]; if(a[i][j]==1)yes=1; if(a[i][j]==0)z++; } } if(yes==0){ printf("-1"); return 0; } for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ if(b[i][j]==0){ if(no(i,j)==0){ printf("-1"); return 0; } } } } for(day=0;z;day++){ for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ if(a[i][j]==day-1){ go(i-1,j); go(i,j-1); go(i+1,j); go(i,j+1); } } } for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ printf("%d",a[i][j]); } printf("\n"); } } printf("%d",day-1); }*/ //토마토(보류중)

/*#include <stdio.h> int a[50001]={}; int b[50001]={}; int c[500001]={}; int t; int n; int piv(int begin, int end){ int p=begin; int l=begin+1; int r=end; while(l<r){ while(a[l]<=a[p]&&l<r)l++; while(a[r]>=a[p]&&l<r)r--; t=a[l]; a[l]=a[r]; a[r]=t; } if(a[p]>a[l]){ t=a[p]; a[p]=a[l]; a[l]=t; } return r; } void q(int begin, int end){ if(begin>=end)return; int p=piv(begin,end); q(begin,p-1); q(p,end); return; } int main() { scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); b[i]=a[i]; } q(0,n-1); for(int i=0;i<n;i++){ c[a[i]]=i; } for(int i=0;i<n;i++){ printf("%d ",c[b[i]]); } return 0; }*/ //데이터 재정렬 /*#include<stdio.h> int stack[500000]={}; int stacki[500000]={}; void push(int *top, int k, int ki){ stack[*top]=k; stacki[*top]=ki; (*top)++; return; } void pop(int *top){ (*top)--; stack[*top]=0; stacki[*top]=0; return; } int main(){ int a; int n; int top=0; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a); while(top>0&&stack[top-1]<=a)pop(&top); if(top==0){ printf("0\n"); }else{ printf("%d\n",stacki[top-1]); } push(&top,a,i); } return 0; }*/ //탑 /*#include<stdio.h> int a[100000]={}; int main(){ int n,k; scanf("%d %d",&n,&k); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } int s=a[0]; int num=0; int l=0,r=0; while(r<n){ if(s<k){ r++; s+=a[r]; }else if(s>k){ s-=a[l]; l++; }else{ num++; r++; s+=a[r]; } } printf("%d",num); }*/ //보물 /*#include<stdio.h> int stack[80000]={}; int a[80000]={}; void push(int *top, int k){ stack[*top]=k; (*top)++; return; } void pop(int *top){ (*top)--; stack[*top]=0; return; } int main(){ int n; int top=0; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } int s=0; int t=0; for(int i=n-1;i>=0;i--){ if(a[i]>=stack[top-1]&&top>0){ s+=top; while(top)pop(&top); }else{ while(top>0&&stack[top-1]>=a[i])pop(&top); s+=top; } push(&top,a[i]); } printf("%d",s); return 0; }*/ //소들의 헤어스타일 실패(1) /*#include<stdio.h> int a[80000]={}; int asdf(int l,int r){ if(l>=r)return 0; int m=0; int s=0; int mi=0; for(int i=l;i<=r;i++){ if(m<a[i]){ m=a[i]; mi=1; }else if(m==a[i]){ mi++; } } int ll=l; int rr=ll; for(int i=0;i<mi;i++){ ll=rr; if(i)rr++; while(a[rr]<m)rr++; if(i==0){ s+=asdf(ll,rr-1); }else{ s+=asdf(ll+1,rr-1); } if(i>0&&rr-1>ll)s+=rr-ll-1; } s+=asdf(rr+1,r); s+=r-rr; return s; } int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } printf("%d",asdf(0,n-1)); return 0; }*/ //소들의 헤어스타일 실패(2)

/*#include <stdio.h> #include <string.h> int num(char x){ if(x>='0'&&x<='9'){ return 1; }else{ return 0; } } void push(int *stack,int *top,int k){ stack[*top]=k; (*top)++; return; } void pop(int *stack,int *top){ (*top)--; stack[*top]=0; return; } int main() { char s[201]={}; int stack[101]={}; fgets(s,200,stdin); int k; int top=0; for(int i=0;i<=strlen(s);i+=2){ if(num(s[i])){ k=s[i]-48; while(s[i+1]!=' '){ i++; k*=10; k+=s[i]-48; } push(stack,&top,k); }else if(s[i]=='+'){ k=stack[top-2]+stack[top-1]; pop(stack,&top); pop(stack,&top); push(stack,&top,k); }else if(s[i]=='-'){ k=stack[top-2]-stack[top-1]; pop(stack,&top); pop(stack,&top); push(stack,&top,k); }else if(s[i]=='*'){ k=stack[top-2]*stack[top-1]; pop(stack,&top); pop(stack,&top); push(stack,&top,k); }else if(s[i]=='/'){ k=stack[top-2]/stack[top-1]; pop(stack,&top); pop(stack,&top); push(stack,&top,k); } } printf("%d",stack[0]); return 0; }*/ /*#include<stdio.h> int q[10]={}; void push(int *head, int *tail, int k){ if(*tail==10){ if(*head==0){ printf("full!!\n"); return; }else{ for(int i=*head;i<10;i++){ q[i-*head]=q[i]; q[i]=0; } *tail=10-*head; *head=0; } } q[*tail]=k; (*tail)++; return; } void pop(int *head, int *tail){ if(*head==*tail){ printf("empty!\n"); return; } q[*head]=0; (*head)++; return; } void print(int *head,int *tail){ if(*head==*tail){ printf("-nothing-\n"); return; } for(int i=*head;i<*tail;i++){ printf("%d ",q[i]); } printf("\n"); return; } int main(){ int head=0; int tail=0; int k; int n; printf("length:10\n"); while(1){ printf("1:push,2:pop,3:print,4:end->"); scanf("%d",&n); switch(n){ case 1: printf("input number:"); scanf("%d",&k); push(&head,&tail,k); break; case 2: pop(&head,&tail); break; case 3: print(&head,&tail); break; case 4: printf("The End"); return 0; default: printf("error!!!!!!!!!!!\n"); } } return 0; }*/ //#include<stdio.h> //int q[11]={}; //void push(int *head, int *tail, int k){ // if(*tail+1==*head||(*tail==10&&*head==0)){ // printf("full!\n"); // return; // } // q[*tail]=k; // (*tail)++; // if(*tail==11)*tail=0; // return; //} //void pop(int *head, int *tail){ // if(*tail==*head){ // printf("empty!\n"); // return; // } // q[*head]=0; // (*head)++; // if(*head==11)*head=0; // return; //} //void print(int *head,int *tail){ // if(*tail==*head){ // printf("-nothing-\n"); // return; // } // for(int i=*head;i!=*tail;i++){ // printf("q[%d]:%d\n",i,q[i]); // if(i==10)i=-1; // } // return; //} //int main(){ // int head=0; // int tail=0; // int k; // int n; // printf("length:10\n"); // while(1){ // printf("1:push,2:pop,3:print,4:end->"); // scanf("%d",&n); // switch(n){ // case 1: // printf("input number:"); // scanf("%d",&k); // push(&head,&tail,k); // break; // case 2: // pop(&head,&tail); // break; // case 3: // print(&head,&tail); // break; // case 4: // printf("The End"); // return 0; // default: // printf("error!!!!!!!!!!!\n"); // } // } // return 0; //} //0 ascii: 48 // log (n) // O(log(n)) // O(n^2) // bubble sort, insertion sort, selection sort, // quick sort, merge sort, heap sort /*#include <stdio.h> int a[10001]; int n, i, j, temp,asdf; int main() { scanf("%d", &n); for (i=1; i<=n; i++) scanf("%d", &a[i]); for(i=1; i<n; i++) { for(int j=1;j<=n-i;j++) { if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } asdf=0; for(int j=1;j<n;j++){ if(a[j+1]<a[j]){ asdf=1; break; } } if(asdf==0){ printf("%d",i); break; } } return 0; }*/ /*#include <stdio.h> int a[100001]; int n,t; int piv(int begin,int end){ int pivot=begin; int l=begin+1; int r=end; //printf("[%d]", a[pivot]); while(l<r){ while(a[l]<a[pivot] && l<r)l++; while(a[r]>=a[pivot] && l<r)r--; t=a[r]; a[r]=a[l]; a[l]=t; } if(a[pivot]>a[l]){ t=a[pivot]; a[pivot]=a[l]; a[l]=t; } //printf("[%d, %d][%d] ", begin, end, a[pivot]); return r; } void quick(int begin,int end){ if(begin>=end)return; int p=piv(begin,end); quick(begin,p-1); quick(p,end); } int main() { scanf("%d", &n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } quick(1,n); for(int i=1;i<=n;i++){ printf("%d\n",a[i]); } return 0; }*/ /*#include<stdio.h> int a[100001]={}; int main(){ int n; scanf("%d",&n); int k,m=100001,M=0; for(int i=0;i<n;i++){ scanf("%d",&k); if(k<m)m=k; if(k>M)M=k; a[k]++; } for(int i=m;i<=M;i++){ for(int j=0;j<a[i];j++){ printf("%d ",i); } } }*/

/*#include <stdio.h> void push(char *stack,int *top,char k){ if(*top==50001){ return; } stack[*top]=k; (*top)++; return; } void pop(char *stack,int *top){ if(*top==0)return; (*top)--; stack[*top]=0; return; } void print(char *stack,int *top){ for(int i=0;i<*top;i++){ printf("%d",stack[i]); } printf("\n"); return; } int main(){ char s[50001]={}; scanf("%s",s); char stack[50001]={}; int i=0; int top=0; while(s[i]=='('||s[i]==')'){ if(s[i]=='('){ push(stack,&top,'('); }else{ if(stack[0]=='('){ pop(stack,&top); }else{ printf("bad"); return 0; } } i++; } if(stack[0]=='\0'){ printf("good"); }else{ printf("bad"); } return 0; }*/ /*#include<stdio.h> #include<string.h> int d(int k){ int c=1; for(int i=0;i<k;i++){ c*=2; } return c; } int t(int k){ int c=1; for(int i=0;i<k;i++){ c*=3; } return c; } void push(char *stack,int *top,char k){ if(*top==16){ return; } stack[*top]=k; (*top)++; return; } void pop(char *stack,int *top){ if(*top==0)return; (*top)--; stack[*top]=0; return; } char s[31]={}; int main(){ char rstack[16]={}; char sstack[16]={}; int rtop=0,stop=0; scanf("%s",s); int sum=0; for(int i=0;i<strlen(s);i++){ if(s[i]=='('){ if(s[i+1]==')'){ sum+=2*(d(rtop)*t(stop)); i++; }else{ push(rstack,&rtop,'('); } }else if(s[i]=='['){ if(s[i+1]==']'){ sum+=3*(d(rtop)*t(stop)); i++; }else{ push(sstack,&stop,'['); } }else if(s[i]==')'){ if(rtop&&s[i-1]!='['){ pop(rstack,&rtop); }else{ printf("0"); return 0; } }else if(s[i]==']'){ if(stop&&s[i-1]!='('){ pop(sstack,&stop); }else{ printf("0"); return 0; } } } if(rtop==0&&stop==0){ printf("%d",sum); }else{ printf("0"); } return 0; }*/ /*#include<stdio.h> #include<string.h> void push(char *stack,int *top,char k){ if(*top==100001){ return; } stack[*top]=k; (*top)++; return; } void pop(char *stack,int *top){ if(*top==0)return; (*top)--; stack[*top]=0; return; } char s[100001]={}; int main(){ char stack[100001]={}; scanf("%s",s); int sum=0; int top=0; for(int i=0;i<strlen(s);i++){ if(s[i]=='('){ if(s[i+1]==')'){ sum+=top; i++; }else{ push(stack,&top,'('); } }else{ pop(stack,&top); sum++; } } printf("%d",sum); return 0; }*/