COIN34 - 34 đồng xu
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
using namespace std;
int xu[35], total[35];
int n;
int res;
void collect(int i, int v, int s) {
if(i==0) {
if(v==0) res >?= s;
return;
}
if(res >= s + i) return;
if(v>total[i]) return;
if(xu[i]<=v) {
collect( i-1, v-xu[i], s+1);
}
collect( i-1, v, s);
}
int main() {
xu[1] = 2;
xu[2] = 3;
xu[3] = 5;
for(int i=4;i<=34;++i) xu[i] = xu[i-1] + xu[i-2] + xu[i-3];
for(int i=1;i<=34;++i) total[i] = xu[i] + total[i-1];
//cout << total[34] << endl;
//cout << xu[34] << endl;
int st, t;
scanf("%d", &st);
for(t=1;t<=st;++t) {
scanf("%d", &n);
res = -1;
collect( 34, n, 0);
printf("Case #%d: %d\n", t, res);
}
//system("pause");
return 0;
}