Thử Nghiệm Thả Trứng Tối Ưu
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Bạn có $K$ quả trứng giống hệt nhau và một tòa nhà có $N$ tầng (đánh số từ $1$ đến $N$). Tồn tại một tầng tới hạn bí mật $F \in [0, N]$ sao cho nếu thả trứng từ tầng $\le F$ thì trứng không vỡ, còn từ tầng $> F$ thì trứng vỡ. Nếu trứng không vỡ, bạn có thể dùng lại nó cho các lần thử tiếp theo.
Với chiến lược thích nghi tối ưu nhất, hãy tìm số lần thả ít nhất trong trường hợp xấu nhất để chắc chắn xác định được giá trị chính xác của $F$.
Dữ liệu vào
- Một dòng chứa hai số nguyên $K$ và $N$ ($1 \le K \le 30$, $1 \le N \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là số lần thả tối thiểu trong trường hợp xấu nhất.
Ví dụ
| Input | Output |
|---|---|
| 2 10 | 4 |
Giới hạn
- $1 \le K \le 30$
- $1 \le N \le 10^9$
Community Discussion