Fişierul intrare/ieşire:joc7.in, joc7.outSursăONI 2008, clasa a 7-a
AutorAdrian PinteaAdăugată deraduzerRadu Zernoveanu raduzer
Timp execuţie pe test0.1 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/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.injoc7.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content