Xóa số (THTA Vòng Chung kết Toàn quốc 2023)
Xem PDF
Điểm:
1400 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Đây là trò chơi với dãy số quen thuộc của các bạn tiểu học.
Ban đầu cho dãy số tự nhiên từ \(1\) đến \(N\). Lần lượt xóa các số ở vị trí chẵn, từ trái sang phải, sau đó dồn lại và lặp lại thao tác xóa các số ở vị trí chẵn, từ trái sang phải.
Hỏi cứ lặp lại các thao tác như vậy thì số \(K\) được xóa ở lần thứ bao nhiêu?
Ví dụ \(N = 10, K = 5\).
Dãy ban đầu là \(1,2,3,4,5,6,7,8,9,10\).
Xóa các số ở vị trí chẵn từ dãy ban đầu, dãy số thu được là \(1,3,5,7,9\) (xóa \(5\) số \(2,4,6,8,10\)).
Tiếp tục xóa các số ở vị trí chẵn ta được dãy số \(1,5,9\) (xóa hai số \(3,7\)).
Tiếp theo xóa số \(5\). Vậy số \(5\) sẽ xóa ở lần xóa thứ \(8\).
Yêu cầu: Đưa ra thứ tự xóa số \(K\) của dãy ban đầu có các số từ \(1\) đến \(N\).
Input
- Nhập vào hai số tự nhiên \(N\) và \(K\) (\(2 \le K \le N \le 10^{15}\)) (mỗi số trên một dòng).
Output
- Đưa ra duy nhất một số tự nhiên theo yêu cầu của bài.
Scoring
- Subtask \(1\) (\(60\%\) số điểm): \(2 \le K \le N \le 1000\).
- Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.
Example
Test 1
Input
10
5
Output
8
Kỳ thi:
- Tin học trẻ A - Vòng Toàn quốc 2023 (3 Tháng 8., 2023)
Bình luận