Fişierul intrare/ieşire: | shop.in, shop.out | Sursă | preONI 2007, Runda 4 |
Autor | Mircea Bogdan Pasoi | Adăugată de | |
Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Shop
Zaharel face din nou cumparaturi in magazinul detinut de Nargy si Fumeanu. Dupa ce a cumparat produse in valoarea de L lei, Zaharel trebuie sa plateasca fix L lei la casa folosind monezile pe care le are. Se stie ca in tara lui Zaharel toate monezile sunt de forma CP unde C este o valoare fixata de guvern. Astfel, Zaharel are la dispozitie N tipuri de monezi, moneda de tipul i avand valorand CAi lei, iar Zaharel detine Bi astfel de monezi. Desigur, Zaharel doreste sa plateasca suma de L lei cu numar minim de monezi.
Date de intrare
Fisierul de intrare shop.in contine pe prima linie numerele naturale N, C, L separate prin spatii. Urmatoarele N linii contin perechi de numere Ai Bi cu semnificatia prezentata mai sus.
Date de iesire
In fisierul de isire shop.out se va scrie un singur numar natural, reprezentand numarul minim de monezi necesare pentru a plati suma de L lei. Urmatoarea linie va contine N numere naturale, al i-lea numar reprezentand de cate ori s-a folosit moneda de tip i.
Restrictii
- 1 ≤ N ≤ 30
- 1 ≤ C ≤ 10
- 0 ≤ L ≤ 1016
- 0 ≤ Ai ≤ 32
- 1 ≤ Bi ≤ 109
- Se garanteaza ca valoarea oricarei monezi este mai mica sau egala cu L
- Cele N tipuri de monezi sunt distincte ca valori
- Pentru 50% din teste L ≤ 1.000.000
- Se garanteaza existenta unei solutii; daca exista mai multe solutii se poate afisa oricare
Exemplu
shop.in | shop.out |
---|---|
4 2 47 0 5 3 2 2 4 4 1 | 9 3 2 3 1 |
Explicatie
47 = 20 + 20 + 20 + 23 + 23 + 22 + 22 + 22 + 24 = 1 + 1 + 1 + 8 + 8 + 4 + 4 + 4 + 16