POJ1011

Sticks Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 142927 Accepted: 33748

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0

Sample Output

6 5

若干根长度相同的木棍被随机分割，分割成最长不超过5的小木棍。现给出分割后的小木棍，问分割前木棍的长度是多少。

#include<cstdio> #include<cstring> #include<algorithm> int sti [70]; bool usd [70]; int n; bool cmp ( int x , int y ) { return x > y ; } /*******pos 记录上次搜索到的位置 这样可以保证选出的每组木棍都是从大到小的顺序选出，减少了很多重复 now 当前正在拼的木棍已有的长度 len 假定的原木棍的总长度 uus 还没用的小木棍的数量*******/ bool dfs ( int pos , int now , int len , int uus ) { if ( now==len ) now = 0 , pos = 0 ;//拼好了一根，初始化now和pos /*******千万别忘了初始化pos*******/ if ( uus==0 ) {//所有小木棍都用上了 if ( now==0 ) return 1 ;//此时当前木棍长度为0，表示木棍中没有多余，成功 else return 0 ;//否则失败 } for ( int i=pos ; i<n ; i++ ) {//从pos开始搜索 if ( usd[i] || now+sti[i]>len ) continue;//用过的 或 太长的 木棍不能用 if ( i>0 && sti[i]==sti[i-1] && !usd[i-1] ) continue;//长度相同的木棍，前一根没用上后一根也用不上 usd[i] = 1 , uus -- ;//小木棍可用，更新 标记 和 剩余木棍数 if ( dfs ( i+1 , now+sti[i] , len , uus ) ) return 1 ;//搜索成功直接返回 真 usd[i] = 0 , uus ++ ;//否则还原这根木棍 if( now==0 ) return 0 ;//now==0，说明这根小木棍是作为当前拼凑的第一根来使用的 //如果作为第一根都用不上，那就用不上了 } return 0 ;//搜索失败，返回 假 } int main () { while( scanf("%d",&n) && n!=0 ){ int sum = 0 ; for( int i=0 ; i<n ; i++ ){//输入小木棍的长度，同时计算总长度 scanf( "%d" , sti+i ) ; sum += sti[i] ; } std::sort ( sti , sti+n , cmp ) ;//按从大到小排序 memset ( usd , 0 , sizeof(usd) ) ;//初始化used标记数组 int i=sti[0] ;//长度从小棍中的最大长度开始试 for ( ; i<sum ; i++ ){//如果一直找不到合法的，则所有小木棍拼成一根大木棍 if ( sum % i != 0 ) continue ;//如果不能整除，肯定不合法 if( dfs( 0 , 0 , i , n ) ) break;//dfs返回真，跳出循环，输出i } printf( "%d\n" , i ) ; } return 0 ; }