Đoán Số Nhị Phân

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