Sticks(5)

サンプルコード

とりあえず、今まで書いたことを元にそのままコードを書いてみることにする。それなりに読める形で1100byte強。これを最終的に250byteほどに短縮するわけだが、このままではどう考えても不可能だ。基本的なアルゴリズムは変えずに、まずデータ構造をシンプルにしなければならない。

以下はソースコードベタ貼りなので、興味ない人はスルー

001 int input[64],label[64],length;

002 int n;//inputの個数

003 

004 int check(int count)

005 {

006  int i=0;

007  if(count!=0)

008  {

009    while(label[i])i++;label[i]=1;

010    if(!search(length-input[i],i+1,count))label[i]=0;

011  }

012  return count?label[i]:1;//1がtrue

013 }

014 

015 int search(int len,int i,int count)

016 {

017  int result=1;//1がtrue、0がfalse

018  int k;

019 

020  if(!len)return check(count-1);

021 

022  if(i==n) result=0;

023  else if(!label[i] && input[i]<=len){

024   label[i]=1;

025   result=search(len-input[i],i+1,count);

026   if(!result)

027   {

028    label[i]=0;

029    k=i+1;while(input[k]==input[i]) k++;

030    result=n-k?search(len,k,count):0;

031   }

032  }

033  else{

034   k=i+1;while(label[k]) k++;

035   result=n-k?search(len,k,count):0;

036  }

037  return result;

038 }

039 

040 int cmp(int *a,int *b){return(*b-*a);}

041 

042 main()

043 {

044  int a,b,t=0,sum;

045  while(~scanf("%d",&n)){

046   if(n==0)break;

047   sum=0;

048   memset(label, 0, sizeof label); 

049   for(a=0;a<n;++a){

050    scanf("%d",&input[a]);

051    sum+=input[a];

052   }

053     qsort(input,n,4,cmp);

054   for(length=input[0]; length<=sum ; length++)

055   {

056    if(sum%length==0 && check(sum/length))break;

057   }         

058   printf("%d\n",length);

059  }

060 }