http://acm.pku.edu.cn/JudgeOnline/problem?id=1010
Код:
#include <stdio.h> #include <string.h> #define MAXN 110 int stamp[MAXN]; int take[MAXN]; int way[5],tmp[5]; int maxt,mins,maxd,tie; int aim; int n; void search(int step,int kind,int max,int sum,int pos) { int i,k; if (sum > aim) return; if (sum == aim) { if (kind < maxt) return; if (kind > maxt) { maxt = kind; maxd = max; mins = step; tie = 0; memcpy(way,tmp,sizeof(way)); return; } if (step > mins) return; if (step < mins) { mins = step; maxd = max; memcpy(way,tmp,sizeof(way)); tie = 0; return; } if (max < maxd) return; if (max > maxd) { maxd = max; tie = 0; memcpy(way,tmp,sizeof(way)); return; } tie = 1; return; } if (step == 4) return; for (i = pos; i < n; i++) { tmp[step] = stamp[i]; if (!take[i]) { take[i] = 1; if (stamp[i] > max) k = stamp[i]; else k = max; search(step+1,kind+1,k,sum+stamp[i],i); take[i] = 0; } else { if (stamp[i] > max) k = stamp[i]; else k = max; search(step+1,kind,k,sum+stamp[i],i); } } } int main(){ int i,k; while (scanf("%d",&k) != EOF) { n = 0; while (k) { stamp[n++] = k; scanf("%d",&k); } scanf("%d",&aim); while (aim) { maxt = -1; mins = 5; maxd = -1; tie = -1; memset(take,0,sizeof(take)); search(0,0,0,0,0); if (tie == -1) printf("%d ---- none\n",aim); else { printf("%d (%d):",aim,maxt); if (tie) printf(" tie"); else for (i = 0; i < mins; i++) printf(" %d",way[i]); printf("\n"); } scanf("%d",&aim); } } return 0; }