Google Code Jam Japan 2011(final) report

I joined final round!

I read B first, and I think I can solve this. So, I begin to think the algorithm without reading other problems! It's big miss!

About 1:30, I can't solve B, so I read A. It's easy. So, I solve A about 30 minute. I should read A first and solve A first!

Then, I think about B, however, I can't solve.

After contest, I watch the explanation, B's algorithm is correct. So, my source has bug.

Result:Score=15/150,Rank=306. Problems are here.

[A,Correct]

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

int comp(const void *p1,const void *p2){
  int n1,n2;
  n1=*((const int *)p1);
  n2=*((const int *)p2);
  return n1-n2;
}

int main(void){
  int k,*ante;
  double S;
  const double pi=atan(1.0)*4;
  int i,j,t;
  double sins;
  scanf("%d",&t);
  for(i=1;i<=t;i++){
    scanf("%d",&k);
    ante=(int *)calloc(k,sizeof(int));
    for(j=0;j<k;j++) scanf("%d",ante+j);
    qsort(ante,k,sizeof(int),comp);
    S=0;
    sins=sin(2*pi/k)*0.5;
    for(j=0;j<k-2;j++) S+=*(ante+j)*(*(ante+j+2))*sins;
    S+=*ante*(*(ante+1))*sins;
    S+=*(ante+k-2)*(*(ante+k-1))*sins;
    printf("Case #%d: %.9f\n",i,S);
    free(ante);
  }
  return 0;
}

[B,Wrong]

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


typedef unsigned long long int ull_int;


ull_int intpow(ull_int a,ull_int b,ull_int c);
ull_int getexp(ull_int now,ull_int bef,ull_int befexp,ull_int c);
ull_int exppow(ull_int a,ull_int b,ull_int c,ull_int min);


int main(void){
  ull_int i,j,k,a,b,c,t;
  ull_int calca,exps;
  scanf("%llu",&t);
  for(i=1;i<=t;i++){
    scanf("%llu %llu %llu",&a,&b,&c);
    calca=a;
    exps=a;
    for(j=0;j<b;j++){
      a=calca;
      calca=intpow(a,exps,c);
      exps=getexp(calca,a,exps,c);
      //printf("calcs=%llu,exps=%llu\n",calca,exps);
    }
    printf("Case #%llu: %llu\n",i,calca);
  }
  return 0;
}


ull_int intpow(ull_int a,ull_int b,ull_int c){
  ull_int res=1;
  while(b>0){
    if(b&1) res=res*a%c;
    a=a*a%c;
    b>>=1;
  }
  return res;
}


ull_int getexp(ull_int now,ull_int bef,ull_int befexp,ull_int c){
  ull_int val=now%c;
  ull_int i,ret,t;
  ull_int *ans;
  ans=(ull_int *)calloc(c,sizeof(ull_int));
  for(i=1;ans[val]==0;i++){
    ans[val]=i;
    val*=now;
    val%=c;
  }
  t=i-ans[val];
  //printf("val,ans[val],i=%llu,%llu,%llu\n",val,ans[val],i);
  ret=exppow(bef,befexp,t,ans[val]);
  free(ans);
  return ret;
}


ull_int exppow(ull_int a,ull_int b,ull_int c,ull_int min){
  ull_int tmp=1;
  ull_int i;
  for(i=1;i<=b;i++){
    tmp*=a;
    if(tmp>=min) break;
  }
  if(tmp<min) return tmp;
  return intpow(a,b,c)-min%c+min;
}