Trò Chơi Đoán Số Tối Ưu

Binary-search Buổi 64 — Contest Chặng 7
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có một trò chơi đoán số: Giám khảo chọn một số bí mật X trong đoạn [1, N]. Bạn được hỏi tối đa K câu hỏi dạng "X có lớn hơn V không?", giám khảo trả lời "Có" hoặc "Không".

Bạn biết trước rằng giám khảo chọn số X và chiến lược trả lời (giám khảo luôn trả lời trung thực). Cho trước X, hãy đưa ra dãy câu hỏi tối ưu (binary search) để xác định X, và in ra dãy các giá trị V bạn hỏi.

Nếu không cần đủ K câu hỏi, chỉ in số câu hỏi thực sự cần.

Dữ liệu vào

Dòng 1: Ba số nguyên N, K, X (1 ≤ X ≤ N ≤ 10^18, 1 ≤ K ≤ 60)

Dữ liệu ra

Dòng 1: Số câu hỏi Q bạn cần hỏi Dòng 2: Q số nguyên — dãy giá trị V bạn hỏi theo thứ tự

Ví dụ
Input Output
10 4 7 4\n5 8 7 6
Giới hạn
  • 1 ≤ X ≤ N ≤ 10^18
  • 1 ≤ K ≤ 60
  • Đảm bảo ceil(log2(N)) ≤ K
Draft saved