ACM-ICPC 2011 Japan domestic contest(Exercise)

I solved ACM-ICPC 2011 Japan domestic contest for my exercise. I can't take part in the contest because I'm not university student, however. I can solve only three problems.

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++;

}