Thử Nghiệm Thả Trứng Tối Ưu

Binary-search Buổi 63 — Interactive & Constructive Dynamic Programming
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved