La un concurs de tir, ţinta este alcătuită din n cercuri concentrice, numerotate din exterior către interior de la 1 la n. Cercurile delimitează pe ţintă n zone circulare (o zonă între cercul 1 şi cercul 2, a doua zonă între cercul 2 şi cercul 3, ş.a.m.d, o zonă între cercul n-1 şi cercul n şi a n-a zonă interiorul cercului n).
Fiecare zonă are ataşată o valoare strict pozitivă, reprezentând numărul de puncte pe care le poate primi un concurent în cazul în care va lovi această zonă.
Cerinţă
Să se determine numărul minim de lovituri pe care trebuie să le execute un concurent pentru a obţine exact k puncte.
Date de intrare
Fişierul de intrare este tir1.in are următoarea structură:
– pe prima linie este scris numărul de cercuri (valoarea n);
– pe a doua linie este scris numărul de puncte ce urmează a fi obţinute de concurent (valoarea k);
– pe a treia linie sunt scrise cele n valori ataşate zonelor, despărţite prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire este tir1.out va conţine pe prima linie numărul minim de lovituri necesar pentru a obţine k puncte, dacă problema are soluţie sau cifra 0 dacă problema nu are soluţie. Dacă problema are soluţie, pe a doua linie sunt scrise valorile asociate zonelor în care a lovit trăgătorul, pentru a obţine cele k puncte, despărţite prin câte un spaţiu.
Restricţii
5 <= n <= 50
k <= 1000
Numerele care reprezintă punctajele zonelor circulare au valori întregi cuprinse între 1 şi 1000 şi nu sunt neapărat în ordine crescătoare.
Soluţia nu este în mod necesar unică.
Exemple
tir1.in
tir1.out
Explicaţii
5
23
2 3 5 6 8
4
2 5 8 8
Ţinta este formată din 5 cercuri concentrice, care determină 5 zone având valorile 2, 3, 5, 6 şi 8.
Pentru a obţine 23 de puncte, numărul minim de lovituri necesar este 4. Loviturile pot fi efectuate în mai multe moduri. O soluţie este de a trage un foc în zona de valoare 2, un foc în zona de valoare 5 şi 2 focuri în zona de valoare 8.
