---
title: Яйця
---

У вас є $n$ яєць, які можна кидати з будівлі висотою $k$ поверхів. Яйця завжди витримують падіння з деякого невідомого поверху $h$ або нижче. Якщо кинути з вищого поверху — вони розбиваються.

Чи можете ви визначити $h$, використовуючи якомога менше кидків яєць? Яйце, яке не розбилося, можна використовувати повторно.

# Формат взаємодії

Це інтерактивна задача. Спочатку зчитайте два цілі числа $n$ та $k$: кількість доступних яєць і висоту будівлі.

Щоб кинути яйце, виведіть "`?` $x$", де $x$ — поверх, з якого ви хочете кинути яйце $(1 \le x \le k)$. Система відповість "`Intact`", якщо яйце не розбилося, або "`Broken`", якщо воно розбилося і більше не може бути використане.

Коли ви визначите відповідь, виведіть "`!` $h$", де $h$ — найвищий поверх, з якого яйця можна кидати без того, щоб вони розбивалися.

Скрипт для тестування можна завантажити [тут](files/eggs-test.py). На початку скрипта наведено інструкції щодо його використання.

# Обмеження

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

# Приклад взаємодії

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

# Оцінювання

Для заданої кількості яєць $n$ і максимальної висоти $k$ кажуть, що _оптимальна стратегія_ виконує не більше ніж $d$ кидків незалежно від значення $h$. Якщо ви робите більше ніж $d$ кидків, результатом буде WRONG ANSWER.

| Підзадача | Обмеження | Бали    |
| :-----: | ----------- | :-------: |
| 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       | Без додаткових обмежень | [score=6] |
