Sticks(6)

とりあえず変数を減らしていく

inputの値は最大64個、それにあわせてlabelも64個。さらにinputはソートしなければならないとなれば、最短コードを目指すには無駄が多すぎる。簡単な方法はlabelを使わないことだが、inputを0で潰す方法は再帰コードで書くとbacktrackし辛い(一つ余分に変数が必要になる)。
この問題のテストケースは、inputの値が最大でも50と問題に書かれている。ということは、inputの値を配列番号にしてその数のカウントをデータにしてしまえばスッキリする。たとえばこれまでの例で使用したinput

15 11 8 8 8 4 3 2 1

は、新しい配列(in[51])を使えば

in[15]=1, in[11]=1, in[8]=3,
in[4]=1, in[3]=1, in[2]=1, in[1]=1
それ以外のin[n]はすべて0

再帰する場合1引いて、backtrackする場合は1足せば良い。これはlabelを使った場合と全く同じ方法で実装できる。

これで約800byte。本格的に圧縮するにはもうちょっと縮めておきたい。

001 int in[51];

002 int length,finish;

003 

004 void check(count, len, max, plen)

005 {

006  if(count==0)finish=1;

007  if(!finish){

008   if(len!=0){

009    int j;

010    for(j=len<plen?len:plen; j>0; --j){

011     if(in[j]) {

012      --in[j];

013      check(count, len-j, max,j);

014      ++in[j];

015     }

016    }

017   } else {

018    while(in[max]==0)--max;

019    --in[max];

020    check(count-1, length-max, max, max);

021    ++in[max];

022   }

023  }

024 }

025 

026 main()

027 {

028  int a,b,sum,max;

029  while(~scanf("%d",&in[0])){

030   if(in[0]==0)break;

031   sum=0;max=0;finish=0;

032   for(a=0;a<in[0];++a){

033    scanf("%d",&b);

034    ++in[b];

035    sum+=b;

036    if(max<b)max=b;

037   }

038   for(length=max; length<=sum ; length++)

039   {

040    if(sum%length==0)check(sum/length,length,max,max);

041    if(finish)break;

042   }         

043   printf("%d\n",length);memset(in, 0, sizeof in); 

044  }

045 }