| Fișierul intrare/ieșire | riddles.in, riddles.out | Sursă | Concurs Shumen juniori 2009 |
|---|---|---|---|
| Autor | Alexander Georgiev | Adăugată de |
Spatarel Dan-Constantin
•
spatarel
|
| Timp de execuție pe test | 1 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate | N/A |
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Riddles
Bunica Elleonorei, Sercha, adoră să își provoace nepoții cu tot felul de ghicitori bazate pe matematică.
În timpul celei mai recente reuniuni ale familiei, le-a dat următoarea ghicitoare: “În magazinul din cartier se afla K produse cu prețuri diferite de la 1 la K. Eu am N monede în următoarea ordine : A1, A2, ..., An. Doresc să merg la magazin și să pot plăti pentru fiecare produs exact prețul produsului respectiv. În același timp sunt o femeie în varstă și nu îmi place să iau cum mine toate monedele, deci doresc să iau doar primele monede. Câte monede ar trebui să iau pentru a putea plăti fiecare preț de la 1 la K?”
Elly nu a stat mai mult de câteva secunde pe gânduri înainte de a răspunde: “Ah, bunică Sercha,
nu din nou acești algoritmi standard!”
Puteți să concurați cu Elleonora scriind un program care rezolvă cerința?
Date de intrare
Fișierul de intrare riddles.in conține pe prima linie o să fie un întreg T care reprezintă numărul de teste. Fiecare test conține două linii. Pe prima linie se află întregii N și K. Pe a doua linie se află N întregi reprezentând valoarea monedelor.
Date de ieșire
În fișierul de ieșire riddles.out, pentru fiecare test se va afișa un singur întreg reprezentând numărul primelor monede pe care ar trebui să le ia bunica lui Elly pentru a putea plăti fiecare preț de la 1 la K. Dacă nu este posibil nici măcar dacă ia toate cele N monede, se va afișa -1.
Restricții
- 1 ≤ T ≤ 16
- 1 ≤ N ≤ 100 000
- 1 ≤ K ≤ 1 000 000
- 1 ≤ Аi ≤ 100 000
Exemplu
| riddles.in | riddles.out |
|---|---|
| 3 7 10 1 2 3 4 5 6 7 3 3 2 4 1 3 6 3 1 4 |
4 3 -1 |
Explicație
În primul test putem să luam toate monedele și să plătim oricare dintre prețurile de la 1 la 28 dar ni se cere să putem plăti oricare dintre prețurile de la 1 la 10, deci primele 4 monede ne sunt suficiente.
În al doilea test trebuie să putem plătim oricare dintre prețurile 1, 2 și 3 dar trebuie să luăm toate monedele pentru a avea un 1.
Al treilea test este imposibil deoarece chiar dacă luăm toate monedele nu putem plăti prețurile 2 și 6.
