| Fişierul intrare/ieşire: | joc7.in, joc7.out | Sursă | ONI 2008, clasa a 7-a |
| Autor | Adrian Pintea | Adăugată de |  Radu Zernoveanu •raduzer |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Joc7
Viorel a primit de la parinti un joc de strategie. Eroul jocului are la inceput un nivel initial n si trebuie sa indeplinesca anumite misiuni. Eroului i se permite accesul la o misiune numai daca nivelul sau este cel putin egal cu nivelul minim cerut de aceasta, iar dupa fiecare misiune indeplinita nivelul sau creste la o anumita valoare, specifica misiunii respective.
Dupa finalizarea unei misiuni Viorel alege alta misiune pentru eroul sau, in conditiile amintite.
Pentru ca parintii nu il lasa sa se joace prea mult, Viorel trebuie sa aleaga un numar minim de misiuni, iar visul lui este sa ajunga la un nivel cel putin egal cu m.
Cerinta
Determinati nivelul atins de erou dupa parcurgerea misiunilor alese si numarul acestora
Date de intrare
Fisierul de intrare joc7.in contine:
- pe prima linie trei numere naturale: n (nivelul initial al eroului), k (numarul de misiuni disponibile) si m (nivelul minim cerut pentru a termina jocul) separate prin cate un spatiu;
- fiecare din urmatoarele k linii corespunde cate unei misiuni si contine doua valori pozitive, separate printr-un spatiu, reprezentand nivelul minim necesar inceperii misiunii, respectiv nivelul dobandit de erou la finalizarea misiunii respective.
Date de iesire
Fisierul de iesire joc7.out contine pe o singura linie nivelul eroului si numarul minim de misiuni alese, separate printr-un spatiu.
Restrictii
- 1 ≤ n, m ≤ 2.000.000.000
- 3 ≤ k ≤ 5.000
- Se considera ca cel putin un nivel este accesibil eroului!
- In cazul in care nu se poate ajunge la un nivel mai mare sau egal cu m se va afisa nivelul maxim la care se poate ajunge (si numarul de mutari necesar pentru a atinge acest nivel)
- In cazul in care sunt mai multe solutii cu numar minim de mutari, se cere cea in care eroul ajunge la nivel maxim.
Exemplu
| joc7.in | joc7.out |
|---|---|
| 6 10 25 1 3 2 3 1 2 2 6 3 9 2 10 5 8 10 17 15 27 17 24 | 27 3 |
| 3 5 100 1 2 2 9 7 19 29 80 77 190 | 19 2 |
| 5 4 20 1 3 9 20 2 10 19 44 | 20 2 |
Explicatie
Exemplul 1:
Viorel alege pentru eroul lui de nivel 6 urmatoarele misiuni: (2,10), (10,17) si (15,27) deci la sfarsit eroul lui are nivelul 27, minim cerut pentru a castiga jocul.
Exemplul 2:
Viorel alege pentru eroul lui 2 misiuni si ajunge la nivelul 19. Misiunile alese sunt: (2,9) si (7,19).
Exemplul 3:
Viorel alege pentru eroul lui 2 misiuni si ajunge la nivelul 20. Misiunile alese sunt: (2,10) si (9,20).
