Trò Chơi Đoán Số Tối Ưu
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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
Community Discussion