Bài 3: Robot nhảy (THT A Thừa Thiên Huế 2026)
Xem PDFMột con robot đứng trên một tia số. Tia số này bắt đầu từ vạch số \(0\) và kéo dài mãi về phía bên phải. Ban đầu, robot đang đứng ở vạch số \(N\) (\(N > 0\)).
Robot được lập trình để nhảy liên tục theo hai bước luân phiên nhau: đầu tiên nhảy tiến về phía bên phải \(A\) bước, sau đó nhảy lùi về phía bên trái \(B\) bước, rồi lại nhảy sang phải \(A\) bước, nhảy sang trái \(B\) bước... Cứ như thế tạo thành một chuỗi di chuyển liên tục. (Mỗi lần nhảy sang phải hoặc sang trái đều tính là một lần nhảy).
Yêu cầu: Hãy tính xem sau ít nhất bao nhiêu lần nhảy thì robot sẽ lùi chạm đúng vào vạch số \(0\), hoặc nhảy lùi vượt qua cả vạch số \(0\) (rơi ra khỏi tia số). Nếu robot cứ nhảy tiến xa mãi mà không bao giờ lùi về tới vạch số \(0\), hãy in ra \(0\).
Input
- Gồm ba số tự nhiên \(N, A, B\) (\(1 \le N, A, B \le 10^{12}\)). Mỗi số trên một dòng.
Output
- In ra một số tự nhiên duy nhất là số lần nhảy ít nhất để robot chạm hoặc vượt qua vạch số \(0\) về phía bên trái. Nếu không bao giờ tới được, in ra \(0\).
Example
Test 1
Input
10
1
3Output
10Note
Ban đầu robot ở vạch số \(10\). Quá trình nhảy diễn ra như sau:
- Lần 1 (sang phải 1): \(10 + 1 = 11\)
- Lần 2 (sang trái 3): \(11 - 3 = 8\)
- Lần 3 (sang phải 1): \(8 + 1 = 9\)
- Lần 4 (sang trái 3): \(9 - 3 = 6\)
- Lần 5 (sang phải 1): \(6 + 1 = 7\)
- Lần 6 (sang trái 3): \(7 - 3 = 4\)
- Lần 7 (sang phải 1): \(4 + 1 = 5\)
- Lần 8 (sang trái 3): \(5 - 3 = 2\)
- Lần 9 (sang phải 1): \(2 + 1 = 3\)
- Lần 10 (sang trái 3): \(3 - 3 = 0\) (Vừa chạm vạch \(0\)).
Vậy robot cần tổng cộng \(10\) lần nhảy.
Test 2
Input
4
1
4Output
4Note
Ban đầu robot ở vạch số \(4\).
- Lần 1 (sang phải 1): \(4 + 1 = 5\)
- Lần 2 (sang trái 4): \(5 - 4 = 1\)
- Lần 3 (sang phải 1): \(1 + 1 = 2\)
- Lần 4 (sang trái 4): Từ vạch số \(2\) mà lùi lại \(4\) bước thì robot sẽ vượt qua cả vạch số \(0\) (rơi khỏi tia số).
Vậy ở lần nhảy thứ \(4\) robot đã thỏa mãn điều kiện. Cần in ra \(4\).
Test 3
Input
5
4
2Output
0Note
Ban đầu robot ở vạch số \(5\).
- Lần 1 (sang phải 4): \(5 + 4 = 9\)
- Lần 2 (sang trái 2): \(9 - 2 = 7\)
- Lần 3 (sang phải 4): \(7 + 4 = 11\)
...
Nhận thấy robot sẽ không bao giờ quay lại chạm tới vạch số \(0\). In ra \(0\).
Scoring
- Subtask \(1\) (\(60\%\) số điểm): \(1 \le N, A, B \le 10^3\).
- Subtask \(2\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.
Bình luận