Google Code Jam Japan 2011(Qual) report

I joined Google Code Jam Japan. This contest is first time!

I read all problems, and I solved C first. Binary operation problem. I missed such problem at Google Code Jam 2011, so I revenge this!I submitted small at 44:59, and large at 45:59.

I was too hungry after solving C. So, I go lunch. I spent about 1.5 hours.

Next, I challenge problem B. When I was eating lunch, I think this problem's algorithm, and I get one. So, I could solve it. I think, it's greedy. I submitted small at 2:46:18, large at 2:47:04.

Then, I wanted to submit all problems. So, I challenge problem A. I made a recursion, so I can solve this a little easily. I submitted small at 3:37:57, large at 3:34:44.

Result, Perfect score!
Score:54/54,Rank:86/918.
Problems are here.(Japanese)

All source is C(language).

[A.カードシャッフル]

#include<stdio.h>

int main(void){
  int t,m,c,w,a[100],b[100],i,j;
  scanf("%d",&t);
  for(i=1;i<=t;i++){
    scanf("%d %d %d",&m,&c,&w);
    for(j=0;j<c;j++) scanf("%d %d",&a[j],&b[j]);
    for(j=c;j;j--){
      if(w < b[j-1]+1) w+=a[j-1]-1;
      else if(w>=a[j-1]+b[j-1]) continue;
      else w-=b[j-1];
    }
    printf("Case #%d: %d\n",i,w);
  }
  return 0;
}


[B.最高のコーヒー]

#include<stdio.h>
#include<stdlib.h>

#define MIN(x,y) (((x)<(y))?(x):(y))

typedef unsigned long long int llu_int;

typedef struct{
  llu_int cup;
  llu_int kigen;
  llu_int man;
  llu_int can;
  llu_int drink;
}coffee;

int comp(const void *p1,const void *p2);

int main(void){
  coffee *datas;
  llu_int t,i,j,k,l,n,tmp,ans;
  scanf("%llu",&t);
  for(i=1;i<=t;i++){
    scanf("%llu %llu",&n,&k);
    datas=(coffee *)calloc(n,sizeof(coffee));
    for(j=0;j<n;j++){
      scanf("%llu %llu %llu",&((datas+j)->cup),&((datas+j)->kigen),&((datas+j)->man));
      (datas+j)->can=MIN((datas+j)->cup,(datas+j)->kigen);
    }
    qsort(datas,n,sizeof(coffee),comp);
   
    for(j=0;j<n;j++){
      (datas+j)->drink=(datas+j)->can;
      for(l=j+1;l<n;l++){
if((datas+j)->kigen-(datas+j)->drink>=(datas+l)->kigen) continue;
if((datas+j)->kigen<=(datas+l)->kigen){
 (datas+l)->kigen-=(datas+j)->drink;
 (datas+l)->can=MIN((datas+l)->kigen,(datas+l)->cup);
 continue;
}
tmp=(datas+l)->kigen-((datas+j)->kigen-(datas+j)->drink);
(datas+l)->kigen-=tmp;
(datas+l)->can=MIN((datas+l)->kigen,(datas+l)->cup);
      }
    }
    for(ans=0,j=0;j<n;j++) ans+=(datas+j)->drink*(datas+j)->man;
    printf("Case #%llu: %llu\n",i,ans);
    free(datas);
  }
  return 0;
}

int comp(const void *p1,const void *p2){
  coffee n1,n2;
  n1=*(const coffee *)p1;
  n2=*(const coffee *)p2;
  if(n1.man < n2.man) return 1;
  else if(n1.man>n2.man) return -1;
  else return n1.kigen-n2.kigen;
  return 0;
}


[C.ビット数]

#include<stdio.h>

typedef unsigned long long int u_int;

int main(void){
  u_int t,n,ans,flg,i;
  scanf("%llu",&t);
  for(i=1;i<=t;i++){
    scanf("%llu",&n);
    ans=0;
    flg=0;
    while(n!=0){
      if(n&1){
if(flg==0) ans++;
else if(n>>1){
 ans+=2;
 flg=1;
}
      }else{
if(flg==1) ans++;
else{
 ans+=2;
 flg=1;
}
      }
      n>>=1;
    }
    printf("Case #%llu: %llu\n",i,ans);
  }
  return 0;
}