9 July 2011

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.
#include<stdio.h>
#include<stdlib.h>
#define NUM 123456
unsigned int list[NUM];
void makelist(void);
int main(void){
unsigned int i,j,n,ans;
makelist();
while(scanf("%u",&n) && n){
ans=0;
if(n==1){
puts("1");
continue;
}else if(n==2){
puts("1");
continue;
}
for(i=((n+1)>>1);i<n;i++) if(list[i]!=0) ans++;
printf("%u\n",ans);
}
return 0;
}
void makelist(void){
unsigned int i,j;
for(i=0;i<NUM;i++) list[i]=(i<<1)+1;
for(i=1;i*i<NUM;i++){
if(list[i]==0) continue;
for(j=(i*(i+1))<<1;j<NUM;j+=(i<<1)+1) list[j]=0;
}
}

B. The Balance of the World

#include<stdio.h>
#include<string.h>
#define NUM 100
int main(void){
int brac[NUM+1],now,i,flg;
char str[NUM+2];
while(fgets(str,sizeof(str),stdin) && strcmp(str,".\n")){
memset(brac,0,sizeof(brac));
flg=0;
now=0;
for(i=0;i<strlen(str)-1;i++){
if(str[i]=='('){
brac[now]=1;
now++;
}else if(str[i]=='['){
brac[now]=2;
now++;
}else if(str[i]==')'){
if(now==0 || brac[now-1]!=1){
flg=1;
break;
}
now--;
}else if(str[i]==']'){
if(now==0 || brac[now-1]!=2){
flg=1;
break;
}
now--;
}
}
if(now!=0) flg=1;
if(flg==0) puts("yes");
else puts("no");
}
return 0;
}

C.Identically Colored Panels Connection

#include<stdio.h>
#include<stdlib.h>
typedef struct{
int col;
int check;
} panels;
int max,h,w,c,num;
void getmax(panels **panel,int color,int nest,int n);
void change(panels **panel,int color,int i,int j);
void countnum(panels **panel,int i,int j);
int main(void){
panels **panel;
int i,j,colors;
while(scanf("%d %d %d",&h,&w,&c) && h && w && c){
panel=(panels **)calloc(h,sizeof(panels *));
for(i=0;i<h;i++) *(panel+i)=(panels *)calloc(w,sizeof(panels *));
for(i=0;i<h;i++){
for(j=0;j<w;j++){
scanf("%d",&colors);
(*(panel+i)+j)->col=colors;
(*(panel+i)+j)->check=0;
}
}
max=0;
for(i=0;i<6;i++) getmax(panel,i+1,0,0);
printf("%d\n",max);
for(i=0;i<h;i++) free(*(panel+i));
free(panel);
}
return 0;
}
void getmax(panels **panel,int color,int nest,int n){
panels **tmp;
int i,j,k;
if(nest==4 && color!=c) return;
tmp=(panels **)calloc(h,sizeof(panels *));
for(i=0;i<h;i++) *(tmp+i)=(panels *)calloc(w,sizeof(panels *));
for(i=0;i<h;i++){
for(j=0;j<w;j++){
(*(tmp+i)+j)->col=(*(panel+i)+j)->col;
(*(tmp+i)+j)->check=0;
}
}
change(tmp,color,0,0);
num=0;
countnum(tmp,0,0);
if(max<num) max=num;
if(nest==4 || num==n){
for(i=0;i<h;i++) free(*(tmp+i));
free(tmp);
return;
}
for(i=0;i<6;i++) getmax(tmp,i+1,nest+1,1);
for(i=0;i<h;i++) free(*(tmp+i));
free(tmp);
}
void change(panels **panel,int color,int i,int j){
(*(panel+i)+j)->check=1;
if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check==0) change(panel,color,i-1,j);
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);
if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check==0) change(panel,color,i,j-1);
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);
(*(panel+i)+j)->col=color;
}
void countnum(panels **panel,int i,int j){
(*(panel+i)+j)->check=2;
if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check!=2) countnum(panel,i-1,j);
if(i<h-1 && (*(panel+i)+j)->col==(*(panel+i+1)+j)->col && (*(panel+i+1)+j)->check!=2) countnum(panel,i+1,j);
if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check!=2) countnum(panel,i,j-1);
if(j<w-1 && (*(panel+i)+j)->col==(*(panel+i)+j+1)->col && (*(panel+i)+j+1)->check!=2) countnum(panel,i,j+1);
num++;
}

You may have missed:

Comments are closed.