---
title: Olas
---

Jums grozā ir $n$ olas, kuras gribat nomest no ēkas ar $k$ stāviem. Eksistē kāds nezināms $h$, ka olas nekad nesaplīst, ja tiek mestas no stāva $h$ vai zemāka. Ja tās tiek mestas no augstāka stāva, tās vienmēr saplīst.

Nosakiet $h$, metot olas pēc iespējas mazāku reižu skaitu. Olu, kas metiena laikā nesaplīst, var mest vēlreiz.

# Komunikācija

Šis ir interaktīvs uzdevums. Sākumā jāielasa divi veseli skaitļi $n$ un $k$: pieejamais olu skaits un stāvu skaits ēkā.

Lai nomestu olu, izvadiet "`?` $x$", kur $x$ ir ēkas stāvs, no kura olu mest $(1 \le x \le k)$. Interaktors atbild ar ziņu "`Intact`", ja ola nesaplīsa, vai arī ar "`Broken`", ja tā saplīsa. Saplēstās olas nevar izmantot vēlreiz.

Kad esat atraduši atbildi, izvadiet "`!` $h$", kur $h$ ir augstākais stāvs, no kura var nomest olu tā, ka tā nesaplīst.

Ir pieejams testēšanas skripts, kuru var lejupielādēt [šeit](files/eggs-test.py). Skripta sākumā ir tā lietošanas instrukcijas.

# Ierobežojumi

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

# Komunikācijas piemērs

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

# Vērtēšana

Olu skaitam $n$ un ēkas stāvu skaitam $k$ teiksim, ka _optimālā stratēģija_ nomet olas ne vairāk kā $d$ reizes (neskatoties uz $h$). Ja jūsu risinājums nomet olas vairāk par $d$ reizēm, tad testa vērtējums ir WRONG ANSWER.


| Apakšuzdevums | Ierobežojumi | Punkti    |
| :-----: | ----------- | :-------: |
| 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       | Bez papildu ierobežojumiem | [score=6] |
