Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | cbinteractiv.in, cbinteractiv.out | Sursă | ad-hoc |
Autor | Arhiva Educationala | Adăugată de | Alex Luchianov •AlexandruLuchianov1 |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 131072 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cbinteractiv
Se da un numar N si interactorul are un numar ascuns, K de la 1 la N pe care voi trebuie sa il gasiti.
Puteti intreba de un numar X iar interactorul va va spune daca acesta este mai mare sau egal decat K.
Interactiune
Initial se citeste din stdin numarul N.
Programul vostru are voie sa puna query-uri scriind in standard output:
- "" reprezentand intrebarea.
Dupa fiecare astfel de query interactorul va raspunde in stdin cu un numar din multimea :
- "0" daca K > X
- "1" daca K ≤ X
- "-1" daca query-ul este invalid, trebuie sa inchideti programul dupa ce primiti acest verdict. Un query este considerat valid daca 1 ≤ X ≤ N
Dupa ce ati aflat numarul K afisati "" si terminati programul.
Dupa fiecare query, inclusiv cel final trebuie sa afisati '\n' si sa dati flush la standard output. Pentru a da flush va puteti folosi de urmatorul tabel.
Limbaj | C/C++ | Pascal | Python | Java | Rust |
---|---|---|---|---|---|
Header necesar | | | import sys | | use std::io::{self,Write}; |
Functie | fflush(stdout) sau cout.flush() | flush(output) | sys.stdout.flush() | System.out.flush() | io::stdout().flush().unwrap(); |
Restricţii
- 1 ≤ N ≤ 10^9
- Pentru 30% din teste N ≤ 500
Punctare
Daca numarul gasit de voi este diferit de K, punctajul pe acel test va fi 0.
Altfel, punctajul vostru va fi decis in functie de Q numarul de queryuri facute de programul vostru:
- Q ≤ 32, 100% din punctajul pe acel test.
- Q ≤ 500, 30% din punctajul pe acel test.
- Q > 500, 0% din punctajul pe acel test.
Exemplu
stdin | stdout | Explicatie |
---|---|---|
10 | | Se citeste N |
| ? 5 | Query cu X = 5 |
1 | | Se raspunde ca K <= X |
| ? 4 | Query cu X = 4 |
0 | | Se raspunde ca K > X |
| ! 5 | Programul a descoperit valoarea lui K si raspunde. |
Explicatie
Problemele interactive devin din ce in ce mai comune, inclusiv pe infoarena. La astfel de probleme inputul si outputul sunt speciale, in acest sens exista un interactor cu care puteti comunica, adica outputul sau este inputul vostru si vice-versa. Aceasta este o reprezentare interactiva a problemei cautarii binare . Problemele interactive pot fi abordate in toate limbajele suportate de infoarena: C, C++, Pascal, Rust, Java
Atunci cand rezolvam probleme interactive trebuie sa fim atenti la faptul ca inainte ca outputul sa ajunga la interactor acesta este tinut intr-un buffer intern. O cauza comuna a greselilor la problemele interactive este faptul ca outputul nu iese din buffer, de aceea noi fortam transferul de informatii de la buffer la interactor prin instructiunea de flush.