Digit Sum |
Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:65536KB |
Total submit users: 69, Accepted users: 61 |
Problem 12944 : No special judgement |
Problem description |
When Grace was in third grade, her elementary school teacher assigned her the following problem:
Grace figured out that the answer to this problem is 207 (for example, as 78 + 129), but when the teacher assigned four pages of similar problems as homework, Grace got bored. It turns out that Grace was a rather advanced third grader, so she decided that |
Input |
Input: Each problem is described on a single line. The line begins with an integer |
Output |
Output: For each case, output a line with the minimum sum |
Sample Input |
5 1 2 7 8 9 6 3 4 2 2 2 2 9 0 1 2 3 4 0 1 2 3 0 |
Sample Output |
207 447 11257 |
Problem Source |
ACM Mid-Central Programming Competition 2013
#include<stdio.h> #include<algorithm> using namespace std; #define mulit(i) (1<<(i)) __int64 a[15],sta[mulit(14)]; void init(int n) { __int64 sum; int h,i; sort(a,a+n); for(int s=1;s<mulit(n);s++) { h=-1; for( i=0;mulit(i)<=s;i++) if((mulit(i)&s)&&a[i]>0) { h=i; sum=a[i]; break; } if(mulit(i-1)==s) { sta[s]=a[i-1]; continue; } if(mulit(i)>s) { sta[s]=-1; continue; } for( i=0;mulit(i)<=s;i++) if((mulit(i)&s)&&h!=i) sum=sum*10+a[i]; sta[s]=sum; } } int main() { int n; __int64 minsum; while(scanf("%d",&n)>0&&n) { for(int i=0;i<n;i++) scanf("%I64d",&a[i]); init(n); minsum=-1; for(int s=1;s<mulit(n);s++) if(sta[s]!=-1&&sta[s^(mulit(n)-1)]!=-1) if(minsum==-1) minsum=sta[s]+sta[s^(mulit(n)-1)]; else if(minsum>sta[s]+sta[s^(mulit(n)-1)]) minsum=sta[s]+sta[s^(mulit(n)-1)]; printf("%I64d\n",minsum); } } |