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;
}

Download