Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | shop.in, shop.out | Sursă | preONI 2007, Runda 4 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
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. Daca nu se poate plati aceasta suma se va afisa "Fara solutie". In caz ca exista solutie, 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 ≤ 20
- 0 ≤ L ≤ 1016
- 0 ≤ Ai ≤ 60
- 1 ≤ Bi ≤ 1.000
- Se garanteaza ca valoarea oricarei monezi este mai mica decat L
- Pentru 50% din teste L ≤ 1.000.000
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$
