---
title: Kiaušiniai
---

Turite $n$ kiaušinių, kuriuos jūs galite išmesti iš $k$ aukštų pastato. Kiaušiniai nesudūžta, jei būna išmetami iš mums nežinomo aukšto $h$ ar žemiau. Jei išmesite iš aukščiau – jie suduš.

Ar galite nustatyti $h$ atlikdami kuo mažiau metimų? Jei kiaušinis nesudūžta, jį vėl galima mesti.

# Bendravimas

Ši užduotis yra interaktyvi. Pradžioje nuskaitykite $n$ ir $k$ – kiaušinių skaičių ir pastato aukštų skaičių.

Norėdami išmesti kiaušinį, išspausdinkite "`?` $x$", kur $x$ yra aukštas, iš kurio norite išmesti kiaušinį $(1 \le x \le k)$. Vertintojas atsakys "`Intact`", jei kiaušinis nesudužo, arba "`Broken`", jei sudužo ir nebegali būti naudojamas.

Radę atsakymą išveskite "`!` $h$", kur $h$ – aukščiausias aukštas, iš kurio išmetus kiaušinį jis nesudužtų.

Testavimo programą galite parsisiųsti [čia](files/eggs-test.py). Skripto pradžioje yra instrukcijos, kaip juo naudotis.

# Ribojimai

- $1 \le n \le 20$
- $1 \le h \le k \le 10^5$

# Bendravimo pavyzdys

```
2 5
? 2
Intact
? 4
Broken
? 3
Intact
! 3
```

# Vertinimas

Kiekvienam kiaušinių skaičiui $n$ ir pastato aukščiui $k$ mūsų žinoma _optimali strategija_ leidžia rasti sprendinį per ne daugiau nei $d$ metimų, nepriklausomai nuo ieškomo aukščio $h$. Jei jūsų programa atliks daugiau metimų nei $d$, rezultatas bus neužskaitytas – WRONG ANSWER.

| Dalinė užduotis | Ribojimai | Taškai    |
| :-----: | ----------- | :-------: |
| 1       | $n=1$       | [score=1] |
| 2       | $n=2$       | [score=2] |
| 3       | $n=20$      | [score=3] |
| 4       | $k \le 50$  | [score=4] |
| 5       | $k \le 500$ | [score=5] |
| 6       | Papildomų ribojimų nėra | [score=6] |
