Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | capcana.in, capcana.out | Sursă | Junior Challenge 2021 |
| Autor | Alexandru Luchianov | Adăugată de |  Comisia •jc2021 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Capcana
Perry a ajuns la Doofenshmirtz pentru a-l impiedica din a distruge intreaga lume cu noul sau inator.
Totusi, odata ce intra pe usa are o surpriza: in loc de sala mare, obisnuita, se afla intr un hol cu N placute, numerotate de la 1 la N, el aflandu-se la intrare, nefiind momentan pe nicio placuta.
Robotul Norm, asistentul lui Doofenshmirtz ii zice apoi agentului P: "Te afli cea mai noua capcana anti-ornitorinci. Tot ce trebuie sa faci ca sa scapi este sa ajungi la finalul holului. Totusi, sub K dintre placute se afla bombe, am fi pus sub toate, dar nu ne-a permis bugetul, deci daca vei calca pe o placuta care are sub ea o bomba, vei muri pe loc. Bafta sa evadezi si de data asta!"
Ca intotdeauna, Perry este pregatit. Are un dispozitiv in care poate scrie, de mai multe ori, cate un triplet (c , a , b), iar dispozitivul ii va returna 1 daca in secventele de placute de lungime c care incep pe a, respeciv b sunt un numar egal de placute periculoase (cu bombe sub), sau 0 altfel.
Evident, Perry trebuie sa afle pozitiile placutelor periculoase. Voi trebuie sa il ajutati folosindu-va de dispozitivul lui, incercand sa introduceti in el cat mai putine triplete (nu putem pierde prea mult timp, pentru ca altfel nu il vom opri pe Doofenshmirtz inainte sa isi realizeze planurile malefice).
Interactiune
Initial se citesc din stdin numerele N si K.
Programul vostru are voie sa puna query-uri scriind in standard output:
- "? c a b" reprezentand introducerea unui triplet de numere in dispozitiv.
Dupa fiecare astfel de query, interactorul va va raspunde in stdin astfel:
- "0" : daca in secventele de lungime c care incep in a, respectiv b nu se gasesc acelasi numar de placute periculoase.
- "1" : daca in secventele de lungime c care incep in a, respectiv b se gasesc acelasi numar de placute periculoase.
- "-1" : dacă query-ul este invalid, trebuie să închideţi programul după ce primiţi acest verdict. Un query este considerat valid dacă intervalele (a , a + c - 1) si (b , b + c - 1) sunt disjuncte, daca 1 ≤ c ≤ N si daca 1 ≤ a , b , a + c - 1 , b + c - 1 ≤ N
Dupa ce ati aflat pozitiile placutelor care au bombe sub ele, afisati "! p1 p2 ... pk", unde pi = pozitia placutei periculoase cu numarul i, iar apoi terminati programul.
După fiecare query, inclusiv cel final trebuie să afişaţi '\n' şi să daţi flush la standard output. Pentru a da flush vă puteţi folosi de următorul 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 si precizari
- 1 ≤ N ≤ 109
- 1 ≤ K ≤ 50
- K * 2 + 1 ≤ N
Fie Q numarul de query-uri pe care le faceti la un test. Punctajele partiale se vor acorda in felul urmator:
- 20 de puncte: N, Q ≤ 102
- 30 de puncte Q ≤ 2K + 1 + log 2 N + (log 2 N + 2) * K * 2
- 50 de puncte Q ≤ 2K + 1 + log 2 N + (log 2 N + 2) * K
Exemplu
| stdin | stdout |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
