|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #define ll long long /* 9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 38 2 6 6 8 7 4 1 8 4 1 4 4 3 3 2 3 3 4 6 8 8 7 2 4 1 1 5 8 4 7 6 5 1 3 3 3 1 6 */ using namespace std; int sz[101]; ll sum; bool f; int total_piece; int stick_size; bool visit[101]; int n; bool cmp(int a,int b) { return a>b; } bool backtrack(int present_size,int index,int piece_count)//gainedlength,sticksize,piece count { if(piece_count*stick_size==sum) return true; for(int i=index;i<n;i++) { if(visit[i]) continue; if(i>0 && !visit[i-1] && sz[i]==sz[i-1]) continue; if(sz[i]+present_size<stick_size) { visit[i] = 1; f = backtrack(sz[i]+present_size,i+1,piece_count); if(f) return 1; visit[i] = 0; if(present_size==0) return 0; } else if(sz[i]+present_size == stick_size) { visit[i] = 1; f = backtrack(0,0,piece_count+1); if(f) return 1; visit[i] = 0; return 0; } } return 0; } int main() { int max_sz; while(cin>>n) { if(n==0) break; sum = 0; max_sz = 0; for(int i=0;i<n;i++) { cin>>sz[i]; sum+=sz[i]; if(sz[i]>max_sz) max_sz = sz[i]; } sort(sz,sz+n,cmp); bool found = false; for(int stk= max_sz;stk<=sum;stk++) { if(sum%stk) continue; memset(visit,0,sizeof(visit)); total_piece = sum/stk; stick_size = stk; if(backtrack(0,0,0)) { cout<<stk<<"\n"; found = 1; break; } } } return 0; } |