Đoán Số Nhị Phân
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — toàn bộ dữ liệu được cho trước).
Trong trò chơi đoán số, máy chấm chọn trước một số nguyên bí mật $X$ nằm trong đoạn $[1, N]$. Người chơi sử dụng chiến lược tìm kiếm nhị phân chuẩn trên đoạn $[L, R]$ (ban đầu $L = 1, R = N$):
- Ở mỗi bước, người chơi hỏi giá trị $mid = \lfloor (L + R) / 2 \rfloor$.
- Nếu $mid = X$, trò chơi kết thúc.
- Nếu $mid < X$, máy chấm trả lời
LON_HON, người chơi cập nhật $L = mid + 1$. - Nếu $mid > X$, máy chấm trả lời
NHO_HON, người chơi cập nhật $R = mid - 1$.
Hãy mô phỏng quá trình trên và in ra dãy các giá trị $mid$ mà người chơi đã hỏi cho đến khi tìm được $X$.
Dữ liệu vào
- Một dòng duy nhất chứa hai số nguyên $N$ và $X$ ($1 \le X \le N \le 10^9$).
Dữ liệu ra
- Dòng đầu tiên ghi số nguyên $K$ là số lần hỏi.
- Dòng thứ hai ghi $K$ số nguyên là các giá trị $mid$ theo đúng thứ tự đã hỏi, cách nhau bởi dấu cách.
Ví dụ
| Input | Output |
|---|---|
| 10 7 | 4 5 8 6 7 |
Giới hạn
- $1 \le X \le N \le 10^9$
Community Discussion