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 împiedica din a distruge întreaga lume cu noul său inator.
Totuşi, odata ce intră pe uşă are o surpriză: în loc de sala mare, obişnuită, se află într-un hol cu podeaua acoperită cu N plăcuţe aşezate în linie, numerotate de la 1 la N, el aflându-se la intrare, fix în spatele plăcuţei 1.

Robotul Norm, asistentul lui Doofenshmirtz îi zice apoi agentului P: "Te afli în cea mai noua capcană anti-ornitorinci. Tot ce trebuie să faci ca să scapi este să ajungi la finalul holului, să treci de plăcuţa N. Totuşi, sub K dintre plăcuţe se află bombe. Am fi pus sub toate, dar nu ne-a permis bugetul, deci dacă vei călca pe o plăcuţă care are sub ea o bombă, vei muri pe loc. Baftă să evadezi şi de data asta!"

Ca întotdeauna, Perry este pregătit. Are un dispozitiv în care poate scrie, de mai multe ori, câte un triplet (c, a, b), iar dispozitivul îi va returna 1 dacă in secvenţele de plăcuţe de lungime c care încep pe a, respectiv b sunt un număr egal de plăcuţe periculoase (cu bombe sub), sau 0 altfel.

Evident, Perry trebuie să afle poziţiile plăcuţelor periculoase. Voi trebuie să îl ajutaţi folosindu-vă de dispozitivul lui, încercând să introduceţi în el cât mai puţine triplete (nu putem pierde prea mult timp, pentru că altfel nu îl vom opri pe Doofenshmirtz înainte să işi realizeze planurile malefice).

Interacţiune

Iniţial se citesc din stdin numerele N şi K.
Programul vostru are voie să pună query-uri scriind în standard output:

• "? c a b" reprezentând introducerea unui triplet de numere in dispozitiv.

După fiecare astfel de query, interactorul vă va răspunde in stdin astfel:

• "0" : dacă in secvenţele de lungime c care încep in a, respectiv b nu se găsesc acelaşi număr de plăcuţe periculoase.

• "1" : dacă in secvenţele de lungime c care încep in a, respectiv b se găsesc acelaşi număr de plăcuţe 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, dacă 1 ≤ c ≤ N şi dacă 1 ≤ a, b, a + c - 1, b + c - 1 ≤ N

După ce aţi aflat poziţiile plăcuţelor care au bombe sub ele, afişati "! p ₁ p ₂ ... p _K ", unde p _i = poziţia plăcuţei periculoase cu numărul i, iar apoi terminaţi 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:

Restricţii si precizări

• 1 ≤ N ≤ 10⁹
• 1 ≤ K ≤ 250
• K * 2 + 1 ≤ N
• Pentru 20% din teste, 1 ≤ N ≤ 2000
• Pentru încă 20% din teste, K = 1
• Placuţele capcană sunt fixate de dinainte. (Graderul nu este adaptiv)

Punctare

Dacă setul poziţiilor plăcuţelor periculoase găsit de voi este diferit de cel corect, punctajul obţinut pe acel test va fi 0 puncte.
Altfel, punctajul vostru va fi decis în funcţie de Q numărul de query-uri făcute:

• 50% din punctajul pe test pentru Q ≤ 2 * (K + 1) * ( log ₂ N + 4 )
• 100% din punctajul pe test pentru Q ≤ (K + 1) * ( log ₂ N + 4 )
• In plus pentru 1 ≤ N ≤ 2000, punctajul pe test va fi acordat în totalitate dacă răspunsul este cel corect, atata timp cat Q ≤ 10^4

Exemplu

Explicaţie

Din cele 3 plăcuţe, doar una este periculoasă. Când aflăm ca plăcuţa 1 si plăcuţa 3 sunt identice, devine clar faptul că niciuna dintre cele două nu pot avea o bombă sub, deoarece K = 1. Astfel putem trage concluzia că plăcuţa 2 este cea periculoasă.

Cum se trimit solutii?