Google Code Jam Japan 2011

Google Gode JamJapan 2011  の練習問題を解いてみました。
http://code.google.com/codejam/japan/

A.数珠繋ぎ
B.数の集合
C.遊園地

と三つ問題があります。
僕が思うにBだけ異常に難しい。 しかもBのlargeだけgoogleの解答と僕の解答が合わない。
いろいろチェックしたんだけどなぁ。本当にGoogleあってんの？



A.数珠繋ぎ
------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



main(){
    FILE *fi=NULL,*fo=NULL;
    char buf[256];
    int t=0,n=0,k=0;
    int i,j,l;

    int syuki=0;
    int no=0;


    //fi=fopen("test.in","rt");
    fi=fopen("A-small-practice.in","rt");
    //fi=fopen("A-large-practice.in","rt");

    //fo=fopen("result.txt","wt");
    fo=fopen("small-result.txt","wt");
    //fo=fopen("larget-result.txt","wt");

    if(fi==NULL || fo==NULL)goto end;


    buf[0]=0;
    fgets(buf,256,fi);
    sscanf(buf,"%d",&t);

   
    for(i=0;i<t;i++){
        fgets(buf,256,fi);
        sscanf(buf,"%d%d",&n,&k);

        no=1<<n;
       
        printf("i=%d n=%d,k=%d\n",i,n,k);
        printf("Case #%d: %s\n",i+1,(k%no)==no-1?"ON":"OFF");
        fprintf(fo,"Case #%d: %s\n",i+1,(k%no)==no-1?"ON":"OFF");
    }

end:
    if(fi)fclose(fi);
    if(fo)fclose(fo);
}
------------------------------


B.数の集合
------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if defined(_MSC_VER) && _MSC_VER<1300
#define longlong _int64
#define PLLD "%I64d"
#else
#define longlong long long
#define PLLD "%lld"
#endif

#define PLD "%ld"
#define PD "%d"


char sosu[1000010];
int sosu_list[1000010];
//char sosu_flag[1000010];

int onaji_list[1000010];
int onaji_ct;

struct st_kazu{
    int sosu[16];
    int ct;
};

struct st_kazu kazu[1000010];


void clear_onaji(){
    onaji_ct=0;
}

void add_onaji(int n){
    int i;
    for(i=0;i<onaji_ct;i++){
        if(onaji_list[i]==n)return;
    }
    onaji_list[i]=n;
    onaji_ct++;
}

main(){
    FILE *fi=NULL,*fo=NULL;

    char buf[256];
    longlong a,b,p;
   
    int i,j,k,l,m,n;
    int sct,c,kaisu,kotae;

    //sosou wo motomeru
    sosu[0]=1;
    sosu[1]=1;
    for(i=2;i<1000003;i++){
        if(sosu[i]==0){
            for(j=i*2;j<1000010;j+=i)sosu[j]=1;
        }
    }

    for(sct=0,i=0;i<1000003;i++)if(sosu[i]==0){
        sosu_list[sct++]=(int)i;
    }

    printf("sosu=%d\n",sct);
    //fi=fopen("test.txt","rt");
    //fi=fopen("B-small-practice.in","rt");
    fi=fopen("B-large-practice.in","rt");

    //fo=fopen("result.txt","wt");
    //fo=fopen("result-small.txt","wt");
    fo=fopen("result-large.txt","wt");

    if(fi==NULL || fo==NULL)goto end;


    fgets(buf,sizeof(buf),fi);
    sscanf(buf,PD,&c);



    for(i=0;i<c;i++){
        fgets(buf,sizeof(buf),fi);
        sscanf(buf,PLLD PLLD PLLD ,&a,&b,&p);

        kaisu=(int)(b-a+1);
        kotae=0;
        memset(kazu,0,sizeof(kazu));

        // kousoku soinnsuu bunkai
        printf("bunkai\n");
        for(k=0;k<sct;k++){
            longlong t;
            if((longlong)(sosu_list[k])<p)continue;
            if((longlong)(sosu_list[k])>b)break;

            //printf("sosu=%d\n" ,sosu_list[k]);

            t=a+sosu_list[k]-1;
            t/=sosu_list[k];
            t*=sosu_list[k];
            //printf(PLLD"\n" ,t);
            while(t<=b){
                int pos=t-a;
                kazu[pos].sosu[kazu[pos].ct++]=sosu_list[k];
                t+=sosu_list[k];
            }

        }

        printf("check1\n");
        for(j=0;j<kaisu;j++){
            longlong t;
            t=a+j;
           
            //printf(PLLD ": ",t);
            //for(k=0;k<kazu[j].ct;k++){
            //    printf("%d ",kazu[j].sosu[k]);
            //}
            //printf("\n");

            if(kazu[j].ct==0)kotae++;
        }

        printf("check2\n");

        for(j=0;j<sct;j++){
            longlong t;

            if((longlong)(sosu_list[j])<p)continue;
            if((longlong)(sosu_list[j])>b)continue;

            t=a+sosu_list[j]-1;
            t/=sosu_list[j];
            t*=sosu_list[j];


            clear_onaji();
            while(t<=b){
                int k=t-a;
                for(l=0;l<kazu[k].ct;l++){
                    add_onaji(kazu[k].sosu[l]);
                }
                t+=sosu_list[j];
            }

            //printf("sosu %d to onazi \n",sosu_list[j]);
            //for(k=0;k<onaji_ct;k++){
            //    printf("%d ",onaji_list[k]);
            //}
            //printf("\n");

            if(onaji_ct==1)kotae++;
            if(onaji_ct>1){
                int mmiinn;

                mmiinn=onaji_list[0];
                for(k=1;k<onaji_ct;k++){
                    if(mmiinn>onaji_list[k])mmiinn=onaji_list[k];
                }
                if(mmiinn==sosu_list[j]){
                    kotae++;
                }

            }
        }
        printf("Case #%d: %d\n",i+1,kotae);
        fprintf(fo,"Case #%d: %d\n",i+1,kotae);
        //break;
    }


end:
    if(fi)fclose(fi);
    if(fo)fclose(fo);

}


------------------------------


C.遊園地
------------------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#if defined(_MSC_VER) && _MSC_VER<1300
#define longlong _int64
#define PLLD "%I64d"
#else
#define longlong long long
#define PLLD "%lld"
#endif

#define PD "%d"
#define PLD "%ld"


int g[1000];
longlong nn[1000];
int nx[1000];

main(){
    FILE *fi,*fo;
    int t,n,r,k;
    int i,j,l,cc;
    longlong m,c;
    char buf[1000*100];
    char*p;

    //fi=fopen("test.in","rt");
    //fi=fopen("C-small-practice.in","rt");
    fi=fopen("C-large-practice.in","rt");

    //fo=fopen("result.txt","wt");
    //fo=fopen("result-c-small.txt","wt");
    fo=fopen("result-c-large.txt","wt");

    if(fi==NULL || fo==NULL)goto end;

    fgets(buf,sizeof(buf),fi);
    sscanf(buf,"%d",&t);
    for(i=0;i<t;i++){

        m=0;

        fgets(buf,sizeof(buf),fi);
        sscanf(buf,"%d%d%d",&r,&k,&n);
        fgets(buf,sizeof(buf),fi);

        p=buf;
        for(j=0;j<n;j++){
            sscanf(p,"%d",&(g[j]));
            p=strchr(p,' ');
            p++;
        }
   
        for(j=0;j<n;j++){
            c=0;
            for(cc=0;cc<n;cc++){
                if(c+g[(j+cc)%n]>k)break;
                c+=g[(j+cc)%n];
            }
            nn[j]=c;
            nx[j]=(j+cc)%n;
        }
        j=0;
        for(l=0;l<r;l++){
            m+=nn[j];
            j=nx[j];
        }
        printf("Case #" PD ": " PLLD "\n",i+1,m);
        fprintf(fo,"Case #" PD ": " PLLD "\n",i+1,m);
    }


end:
    if(fi)fclose(fi);
    if(fo)fclose(fo);
}


------------------------------