---
title: Munad
---

Sul on $n$ muna, mida sa saad alla kukutada $k$-korruselisest majast. Munad jäävad alati terveks, kui need kukuvad mingilt tundmatult korruselt $h$ või sellest madalamalt. Kõrgematelt korrustelt kukkudes lähevad munad katki.

Kas suudad leida $h$, kukutades selleks mune võimalikult vähe kordi? Muna, mis jääb terveks, saab uuesti kukutada.

# Suhtlus

See on interaktiivne ülesanne. Esiteks loe kaks täisarvu $n$ ja $k$: vastavalt saadaval olevate munade arv ja maja korruste arv.

Muna alla kukutamiseks väljasta "`?` $x$", kus $x$ on korrus, kust soovid muna kukutada $(1 \le x \le k)$. Hindamisprogramm vastab sõnega "`Intact`", kui muna jäi terveks, või sõnega "`Broken`", kui muna läks katki ja seda ei saa enam uuesti kasutada.

Kui oled leidnud õige vastuse, väljasta "`!` $h$", kus $h$ on kõige kõrgem korrus, kust muna võib alla kukkuda ilma katki minemata.

Saadaval on ka [testimisskript](files/eggs-test.py). Skripti alguses on toodud kasutusjuhised.

# Piirangud

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

# Näidissuhtlus

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

# Hindamine

Fikseeritud munade arvu $n$ ja maja kõrguse $k$ jaoks ütleme, et _optimaalne strateegia_ kukutab mune ülimalt $d$ korda, sõltumata $h$ väärtusest. Kui kukutad rohkem kui $d$ muna, siis saab lahendus tulemuseks WRONG ANSWER.

| Alamülesanne | Piirangud | Punkte    |
| :-----: | ----------- | :-------: |
| 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       | No additional constraints | [score=6] |
