В обороте участвуют монеты достоинством 1 рубль, 2 рубля, 5 рублей и 10 рублей. Сколькими...

Question

В обороте участвуют монеты достоинством 1 рубль, 2 рубля, 5 рублей и 10 рублей. Сколькими способами можно набрать сумму 64 рубля?

Answer 1

Ll - long long

dp[i] = dp[i-1] + dp[i-2] + dp[i-5] + dp[i-10];
ll dp[666];
dp[0] = 1;
for(int i=0;i<=64;i++)<br>{
dp[i+1]+=dp[i];
dp[i+2]+=dp[i];
dp[i+5]+=dp[i];
dp[i+10]+=dp[i];
cout << i << ": " << dp[i] << endl<span>;
}
это если порядок важен, то есть 2 + 1 != 1 + 2, тогда ответ
489475342266653, наверное
а иначе 644

ll ans=0;
for(int i=0;i<10;i++) <span>// 10
{
for(int j=0;j<20;j++) <span>// 5
{
for(int k=0;k<50;k++) <span>// 2
{
ll now = i*10 + j*5 + k*2;
if(now<=64) ans++<span>;
}
}
}
cout << ans<span>;