Zadanie

Démon dedukcie

Počet bodov: 30

Ako agent Slovakistanskej tajnej služby ste dostali úlohu uniesť Macedónskeho prezidenta. Z dôvodu podfinancovania agentúry sa však nepodarilo zistiť jeho vzhľad ani meno. A tak ste do Macedónska prileteli tak trochu naslepo…

Viete však, že každý Macedónec pozná prezidenta a naopak prezident žiadneho z tých plebov nepozná. (ak A pozná B, nie nutne musí B poznať A) Preto teraz beháte medzi občanmi, chaoticky sa každého pýtate koho pozná a snažíte sa z toho niečo zlepiť. Ale nešlo by to rozumnejšie?

Úloha

V Macedónsku žije \(n\) ľudí. Nanajvýš \(l\)-krát sa môžete niektorého z nich spýtať, či nepozná nejakého iného.

Viete, že Macedónsky prezident nepozná nikoho a jeho poznajú všetci. Nájdite ho, alebo určite, že neexistuje.

Vstup a Výstup

Na prvom riadku vstupu sa nachádza jedno kladné číslo \(n\) (\(n = 100\)). Na druhom riadku sa nachádza \(l\) - maximálny počet otázok, ktoré môžete položiť.

Následne sa môžete pýtať otázky vypísaním riadku formátu ? a b (\(1 \leq a,b \leq n; a \neq b\)). Testovač vám ako odpoveď vypíše jediný riadok s jednotkou ak \(a\) pozná \(b\) alebo nulou inak.

Keď ste si istý odpoveďou, vypíšte riadok tvaru ! x, kde \(x\) je číslo prezidenta, alebo \(-1\) ak neexistuje.

Keďže táto úloha je interaktívna, po vypísaní každej otázky je nutné flushovať. V pythone sa to robí parametrom print-u flush : print(…, flush = True), v C++ pomocou cout.flush(). Ak tak neurobíte, váš program môže skončiť verdiktom TLE.

Po vypísaní odpovede odpovede musí váš program skončiť. Taktiež musí skončiť, ak na niektorú otázku dostane odpoveď -1 , čo indikuje neplatnú otázku (napríklad nedodržaný formát či prekročený počet otázok). Ak tak neurobí, môžete dostať nesprávny verdikt.

Testovač je adaptívny, teda jeho odpovede na otázky sa môžu meniť vzhľadom na vaše otázky.

Obmedzenia

Úloha má 3 sady vstupov, v ktorých platia nasledovné obmedzenia:

Príklad komunikácie

(Z pochopiteľných dôvodov tu neplatí obmedzenie \(n=100\))

3
9900
? 1 2
1
? 3 2
1
? 2 1
0
? 2 3
0
! 2

Z prvej otázky sme zistili, že z dvojice 1,2 môže iba 2 byť prezidentom. Tak sme ho overili a zistili, že ním skutočne je

3
9900
? 1 2
1
? 2 3
1
? 3 1
1
! -1

V tomto prípade každý niekoho pozná, teda prezident neexistuje