Zadanie
Táto úloha je mierne ťažšou verziou úlohy číslo 1, “Toľko možností”
Po úspechu s pokusmi doma sa rozhodol Luxusko preskúmať, ako sa správa delenie vesmíru na inom mieste. Vycestoval do ďalekých Spojených štátov amerických a pokus zopakoval. V USA však majú mince s inými hodnotami, namiesto 20 centoviek musel použiť 25 centovky.
Úloha
Máte danú cenu \(n\). Zistite, koľkými spôsobmi sa dá táto cena zaplatiť mincami s hodnotami 1, 5, 10 a 25. Dva spôsoby platenia sú rôzne, pokiaľ použijú iný počet kusov nejakej mince.
Formát vstupu
Na vstupe je jeden riadok s celým číslom \(n\) (\(1\leq n\leq 10^{18}\)).
Formát výstupu
Vypíšte počet spôsobov, ktorými sa dá zaplatiť suma \(n\) pomocou mincí s hodnotami 1, 5, 10 a 25 modulo \(10^9+7\).
Príklady
Input:
14
Output:
4
Input:
30
Output:
18
Input:
7
Output:
2
Úloha sa rieši veľmi podobne, ako predošlá úloha Toľko možností, preto sa najprv uistite, že rozumiete riešeniu tej úlohy.
V predošlej úlohe sme využili, že hodnota každej mince je deliteľná všetkými hodnotami menších mincí. Napríklad každé použitie 20-centovej mince nám akoby ubralo možnosť použiť dve 10-centové mince alebo 4 päťcentové alebo 20 1-centových. V tejto úlohe však máme 25-centovú mincu, ktorá nie je deliteľná 10-centovou.
Dajú sa vymyslieť komplikované finty, ako sa s tým vysporiadať ale lepšia cesta je využiť nasledujúci trik. Buď pri platení použijeme párny počet alebo nepárny počet 25-centových mincí. Tým pádom si môžeme preformulovať zadanie tak, že pri platení môžeme používať nové 50-centové mince a najviac jednu 25-centovú.
Vlastne len sčítame počet možností ako zaplatiť sumu \(n\) pomocou mincí \(1,5,10,50\) a sumu \(n-25\) pomocou rovnakej sady mincí. Tieto podúlohy vyriešime veľmi podobne ako predošlú úlohu.
Nasledujúci program obsahuje kostru riešenia s chýbajúcim vzorcom. Je na vás, aby ste daný vzorec doplnili.
#include <iostream>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define idva 500000004LL
#define itri 333333336LL
inline ll mod(ll x) { return x%MOD; }
ll solve(ll n) {
ll n5 = mod(n/5);
ll n10 = mod(n/10);
ll n50 = mod(n/50);
// Tuto spočítame výsledok, ale sami musíte vymyslieť, ako.
ll vysledok = 0;
return mod(mod(vysledok) + MOD);
}
int main() {
ll n;
cin >> n;
cout << mod(solve(n) + (n>=25)*solve(n-25)) << endl;
}
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.