Sticks(1)

同じ長さの棒を出来るだけたくさん作るには、

①まず入力値(input)の合計(sum)を求める。
②sumの約数で、かつinputの最大値(max)以上のもの(=length)を、小さい順から順番に調べていく。
③すべてのinputを使用して長さlengthの棒ができれば、lengthを出力して終了。

これだけでできることはすぐに分かる。

たとえば、前回の入力例

4 3 2 1

なら、合計値が10になる。約数は、1,2,5,10このうち入力の最大値4よりも大きいのは5,10だから、最初はたして5になるような組み合わせを見つければよい。
もし入力が

5 3 2 1

なら合計値が11(素数)なので11がそのまま答えになる。

実際にコードを書いてみると、

001 int input[64];

002 int length,n;

003 

004 main()

005 {

006   int a,b,sum;

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

008     if(n==0)break;

009     sum=0;

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

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

012       sum+=b;

013             if(max<b)max=b;

014             input[a]=b;

015     }

016 

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

018     {                   // sum/lengthは棒の本数

019       if(!sum%length)if(check(sum/length))break;

020     }         

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

022   }

023 }

024 

025 check(count){長さlengthの棒がcount本できるか調べる}

こんなかんじだろう。

答えの候補は簡単に絞れそうだ。では、stickがその長さになるような値の組み合わせはどのようにして求めればよいのだろうか。