Some ACM-ICPC Problems & Solutions (ACM-ICPC: 2011 in Fukuoka)

Problems here: http://icpc2011.ait.kyushu-u.ac.jp/icpc2011/contest/all_en.html

Solution (s) by Tatuyan:

Problem-A: I did not have a hard time so much because this problem looks like my self-made problem. When we made the problem, I checked all number with for-loop. This time, I prepare prime table with using Eratosthenes’s sifter.
Problem-B: There is Kind Problem at UTPC2011(University of Tokyo Programming Contest 2011). I solved with making stack.
Problem-C: I solved this problem with back track. In Japan domestic contest, We usually see problem which require counting cells,do we?
Problems are here.

C Source.

A.Chebyshev’s Theorem.
01 #include<stdio.h>
02 #include<stdlib.h>
03 #define NUM 123456
04 unsigned int list[NUM];
05 void makelist(void);
06 int main(void){
07 unsigned int i,j,n,ans;
08 makelist();
09 while(scanf("%u",&n) && n){
10 ans=0;
11 if(n==1){
12 puts("1");
13 continue;
14 }else if(n==2){
15 puts("1");
16 continue;
17 }
18 for(i=((n+1)>>1);i<n;i++) if(list[i]!=0) ans++;
19 printf("%u\n",ans);
20 }
21 return 0;
22 }
23 void makelist(void){
24 unsigned int i,j;
25 for(i=0;i<NUM;i++) list[i]=(i<<1)+1;
26 for(i=1;i*i<NUM;i++){
27 if(list[i]==0) continue;
28 for(j=(i*(i+1))<<1;j<NUM;j+=(i<<1)+1) list[j]=0;
29 }
30 }

B. The Balance of the World

01 #include<stdio.h>
02 #include<string.h>
03 #define NUM 100
04 int main(void){
05 int brac[NUM+1],now,i,flg;
06 char str[NUM+2];
07 while(fgets(str,sizeof(str),stdin) && strcmp(str,".\n")){
08 memset(brac,0,sizeof(brac));
09 flg=0;
10 now=0;
11 for(i=0;i<strlen(str)-1;i++){
12 if(str[i]=='('){
13 brac[now]=1;
14 now++;
15 }else if(str[i]=='['){
16 brac[now]=2;
17 now++;
18 }else if(str[i]==')'){
19 if(now==0 || brac[now-1]!=1){
20 flg=1;
21 break;
22 }
23 now--;
24 }else if(str[i]==']'){
25 if(now==0 || brac[now-1]!=2){
26 flg=1;
27 break;
28 }
29 now--;
30 }
31 }
32 if(now!=0) flg=1;
33 if(flg==0) puts("yes");
34 else puts("no");
35 }
36 return 0;
37 }

C.Identically Colored Panels Connection

01 #include<stdio.h>
02 #include<stdlib.h>
03 typedef struct{
04 int col;
05 int check;
06 } panels;
07 int max,h,w,c,num;
08 void getmax(panels **panel,int color,int nest,int n);
09 void change(panels **panel,int color,int i,int j);
10 void countnum(panels **panel,int i,int j);
11 int main(void){
12 panels **panel;
13 int i,j,colors;
14 while(scanf("%d %d %d",&h,&w,&c) && h && w && c){
15 panel=(panels **)calloc(h,sizeof(panels *));
16 for(i=0;i<h;i++) *(panel+i)=(panels *)calloc(w,sizeof(panels *));
17 for(i=0;i<h;i++){
18 for(j=0;j<w;j++){
19 scanf("%d",&colors);
20 (*(panel+i)+j)->col=colors;
21 (*(panel+i)+j)->check=0;
22 }
23 }
24 max=0;
25 for(i=0;i<6;i++) getmax(panel,i+1,0,0);
26 printf("%d\n",max);
27 for(i=0;i<h;i++) free(*(panel+i));
28 free(panel);
29 }
30 return 0;
31 }
32 void getmax(panels **panel,int color,int nest,int n){
33 panels **tmp;
34 int i,j,k;
35 if(nest==4 && color!=c) return;
36 tmp=(panels **)calloc(h,sizeof(panels *));
37 for(i=0;i<h;i++) *(tmp+i)=(panels *)calloc(w,sizeof(panels *));
38 for(i=0;i<h;i++){
39 for(j=0;j<w;j++){
40 (*(tmp+i)+j)->col=(*(panel+i)+j)->col;
41 (*(tmp+i)+j)->check=0;
42 }
43 }
44 change(tmp,color,0,0);
45 num=0;
46 countnum(tmp,0,0);
47 if(max<num) max=num;
48 if(nest==4 || num==n){
49 for(i=0;i<h;i++) free(*(tmp+i));
50 free(tmp);
51 return;
52 }
53 for(i=0;i<6;i++) getmax(tmp,i+1,nest+1,1);
54 for(i=0;i<h;i++) free(*(tmp+i));
55 free(tmp);
56 }
57 void change(panels **panel,int color,int i,int j){
58 (*(panel+i)+j)->check=1;
59 if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check==0) change(panel,color,i-1,j);
60 if(i<h-1 && (*(panel+i)+j)->col==(*(panel+i+1)+j)->col && (*(panel+i+1)+j)->check==0) change(panel,color,i+1,j);
61 if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check==0) change(panel,color,i,j-1);
62 if(j<w-1 && (*(panel+i)+j)->col==(*(panel+i)+j+1)->col && (*(panel+i)+j+1)->check==0) change(panel,color,i,j+1);
63 (*(panel+i)+j)->col=color;
64 }
65 void countnum(panels **panel,int i,int j){
66 (*(panel+i)+j)->check=2;
67 if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check!=2) countnum(panel,i-1,j);
68 if(i<h-1 && (*(panel+i)+j)->col==(*(panel+i+1)+j)->col && (*(panel+i+1)+j)->check!=2) countnum(panel,i+1,j);
69 if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check!=2) countnum(panel,i,j-1);
70 if(j<w-1 && (*(panel+i)+j)->col==(*(panel+i)+j+1)->col && (*(panel+i)+j+1)->check!=2) countnum(panel,i,j+1);
71 num++;
72

Leave a Reply

Your email address will not be published. Required fields are marked *