Fişierul intrare/ieşire:joc8.in, joc8.outSursăGrigore Moisil 2008, clasele 5-6
AutorClara IonescuAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.1 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Joc8

Gigel si Alina se joaca de-a ghicitoarea. Gigel se gandeste la un numar natural mai mare sau egal decat un anumit numar x si mai mic sau egal decat un alt numar y. Alina ii promite lui Gigel ca va ghici la ce numar s-a gandit Gigel punandu-i un numar surprinzator de mic de intrebari de urmatoarele forme:

  • Te-ai gandit la numarul z?
  • Numarul tau este mai mic decat z?

Urmeaza ca Gigel sa-i raspunda numai cu Da sau Nu dupa caz. Gigel este neincrezator deoarece nu stie cum va proceda Alina. Noi in schimb va spunem secretul Alinei. Ea va calcula numarul natural z aflat la mijlocul intervalului [x, y] si va intreba: "Te-ai gandit la z?". Daca raspunsul lui Gigel este Da, jocul s-a terminat, deoarece Alina a ghicit numarul la care s-a gandit Gigel. Daca raspunsul este Nu, Alina va intreba "Numarul tau este mai mic decat z?".

  • Daca acum raspunsul este Da, Alina va calcula numarul natural aflat la mijlocul intervalului [x, z-1] si va pune din nou intrebarea 1.
  • Daca raspunsul este Nu, Alina va calcula numarul natural aflat la mijlocul intervalului [z + 1, y] si va pune din nou intrebarea 1.

Intrebarile Alinei vor continua in mod similar, pana cand ghiceste numarul la care s-a gandit Gigel. Numai ca Gigel este smecher si este posibil ca el sa incerce s-o pacaleasca pe Alina si sa dea cel putin un raspuns gresit. In cazul acesta Alina isi va da seama ca a fost pacalita in momentul in care marginea din stanga a intervalului curent devine mai mare decat marginea din dreapta.

Cerinta

Scrieti un program care simuleaza jocul descris.

Date de intrare

Pe prima linie a fisierului de intrare joc8.in se afla doua numere naturale x si y reprezentand limitele intre care a ales Gigel un numar. Pe urmatoarele linii sunt scrise raspunsurile lui Gigel. Daca raspunsul este Da, in fisier este scrisa cifra 1. Daca raspunsul este Nu, in fisier este scrisa cifra 0. Intotdeauna sunt atatea raspunsuri cate intrebari a pus Alina.

Date de iesire

Pe prima linie a fisierului de iesire joc8.out se va scrie numarul natural la care s-a gandit Gigel. In cazul in care Gigel triseaza, pe prima linie se va scrie numarul 0.

Restrictii

  • 1 ≤ x, y ≤ 10 000

Exemple

joc8.injoc8.out
100 300
0
0
0
1
0
0
1
237
25 30
0
0
0
0
0
0
0

Explicatie

Pentru primul exemplu, Alina face urmatoarele presupuneri (mai jos prin [expresie] am notat partea intreaga a expresiei):

  • [(100 + 300)/2] = 200 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2 si raspuns Nu)
  • [(201 + 300)/2] = 250 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2 si raspuns Da)
  • [(201 + 249)/2] = 225 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2 si raspuns Nu)
  • [(226 + 249)/2] = 237 (intrebare de tip 1, raspuns Da)

Pentru al doilea exemplu, Alina face presupunerile:

  • [(25 + 30)/2] = 27 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2, si raspuns Nu)
  • [(28 + 30)/2] = 29 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2, si raspuns Nu)
  • [(30 + 30)/2] = 30 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2, si raspuns Nu)
  • [(31 + 30)/2] = nu se mai calculeaza, deoarece x a devenit mai mic decat y. Rezulta ca Gigel a trisat.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content