FOJ有奖月赛-2011年11月 参戦記

初めてこのコンテストを知りましたので、ほんの少しだけ参加しました。

挑戦したのは３問。中国語の問題はよくわかりません。

1:コンピュータによる翻訳と自分のわかる範囲の中国語、サンプルケースから推測して提出しました。ごく簡単な問題です。

5:ソートした後探索すれば間にあうのでは？と思ったのですが、TLE.複数ある場合があるので、二分探索でどうのこうのとやるのはどうなのでしょうか。何か良いアルゴリズムを探してみたいところです。

9:一番最後にある割には一番簡単な問題に思えました。2進法を考えればよいだけです。

問題はこちら。
Standings=120,Accept=2,Penalty=71でした。

[A.Ac]

#include<stdio.h>

int main(void){
  int t,a[3],b[3],awin,i,j;
  scanf("%d",&t);
  while(t--){
    scanf("%d %d %d %d %d %d",&a[0],&a[1],&a[2],&b[0],&b[1],&b[2]);
    for(i=0,j=0;i<3 && j<3;(a[i]>b[j]?j++:i++));
    if(j==3) puts("1");
    else puts("2");
  }
  return 0;
}

[E.TLE]

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

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

int main(void){
  int n,m,*array,i,j,k,count;
  while(fscanf(stdin,"%d %d",&n,&m)!=EOF){
    array=(int *)calloc(n,sizeof(int));
    for(i=0;i<n;i++) scanf("%d",array+i);
    qsort(array,n,sizeof(int),comp);
    count=0;
    for(i=0,j=n-1;i<j;i++){
      k=-1;
      while('_'){
if(i>=j){
 if(k!=-1) j=k;
 break;
}
if(*(array+i)+*(array+j)==m){
 count++;
 if(k==-1) k=j;
}else if(*(array+i)+*(array+j)<m){
 if(k!=-1) j=k;
 break;
}
j--;
      }
    }
    printf("%d\n",count);
    free(array);
  }
  return 0;
}

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


[I.Ac]

#include<stdio.h>

int main(void){
  unsigned int n;
  unsigned int i,j,k;
  while(fscanf(stdin,"%u",&n)!=EOF){
    for(i=0;i<33;i++){
      if((1<<i)>n){
printf("%u\n",i);
break;
      }
    }
  }
  return 0;
}