---
title: Kananmunat
---

Sinulla on $n$ kananmunaa, joita voit pudottaa $k$-kerroksisesta rakennuksesta. Kananmuna säilyy ehjänä putoamisesta, jos se pudotetaan kerroksesta $h$ (tuntematon arvo) tai alempaa. Jos kananmuna pudotetaan korkeammalta, se rikkoontuu.

Pystytkö määrittämään arvon $h$ pudottamalla kananmunia mahdollisimman vähän kertoja? Jos kananmuna säilyy ehjänä, se voidaan pudottaa uudestaan.

# Interaktio

Tämä on interaktiivinen tehtävä. Sinun tulee lukea ensin kaksi kokonaislukua $n$ ja $k$: saatavilla olevien kananmunien määrä sekä rakennuksen korkeus.

Kun haluat pudottaa kananmunan, tulosta "`?` $x$", missä $x$ on kerros, josta haluat pudottaa sen $(1 \le x \le k)$. Arvostelija vastaa "`Intact`", jos kananmuna säilyi ehjänä, tai "`Broken`", jos se rikkoontui eikä sitä voida käyttää uudestaan.

Kun olet selvittänyt vastauksen, tulosta "`!` $h$", missä $h$ on korkein kerros, josta kananmuna voidaan pudottaa rikkomatta sitä.

Voit ladata testausskriptin [tästä](files/eggs-test.py). Skriptin alussa on sen käyttöohjeet.

# Rajat

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

# Esimerkki-interaktio

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

# Pisteytys

Kun kananmunien määrä on $n$ ja kerrosten määrä on $k$, on olemassa _optimistrategia_, jossa pudotusten määrä on enintään $d$ riippumatta $h$:sta. Jos pudotat kananmunan yli $d$ kertaa, saat tuloksen WRONG ANSWER.

| Osatehtävä | Rajoitukset | Pisteet    |
| :-----: | ----------- | :-------: |
| 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       | Ei lisärajoituksia | [score=6] |
