Fişierul intrare/ieşire:shop.in, shop.outSursăpreONI 2007, Runda 4
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inshop.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content