Hai chú chuột túi
Đề bài
Trong một tiết mục xiếc, người huấn luyện cho hai chú chuột túi cùng đứng trên một đường thẳng (trục số) và cùng nhảy về một hướng (chiều tăng của trục số). Hai chú nhảy cùng lúc, mỗi lượt nhảy một lần:
- Chú thứ nhất xuất phát tại vị trí $x_1$, mỗi lần nhảy tiến thêm $v_1$ mét.
- Chú thứ hai xuất phát tại vị trí $x_2$, mỗi lần nhảy tiến thêm $v_2$ mét.
Như vậy sau $t$ lần nhảy ($t = 0, 1, 2, \dots$), chú thứ nhất ở vị trí $x_1 + t \cdot v_1$ và chú thứ hai ở vị trí $x_2 + t \cdot v_2$.
Hãy cho biết có tồn tại một thời điểm nào đó mà sau cùng một số lần nhảy, hai chú chuột túi đứng đúng tại cùng một vị trí hay không. Nếu có in ra YES, ngược lại in ra NO.
Dữ liệu vào: Một dòng gồm 4 số nguyên $x_1, v_1, x_2, v_2$ cách nhau bởi dấu cách.
Kết quả: In ra YES hoặc NO.
Giới hạn:
- $0 \le x_1 < x_2 \le 10\,000$
- $1 \le v_1, v_2 \le 10\,000$
Subtask:
- Subtask 1 (40% số điểm): $x_2 \le 100$ và $v_1, v_2 \le 100$.
- Subtask 2 (60% số điểm): không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.
0 3 4 2YES0 2 5 3NOGiải thích: Ví dụ 1: vị trí của hai chú sau từng lần nhảy là:
| Lần nhảy | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Chú 1 (bắt đầu 0, nhảy 3) | 0 | 3 | 6 | 9 | 12 |
| Chú 2 (bắt đầu 4, nhảy 2) | 4 | 6 | 8 | 10 | 12 |
Sau 4 lần nhảy, cả hai cùng đứng ở vị trí 12 nên đáp án là YES.
Ví dụ 2: chú thứ hai vừa đứng phía trước vừa nhảy xa hơn nên khoảng cách giữa hai chú ngày càng tăng, không bao giờ gặp nhau, đáp án là NO.
Nguồn: phỏng theo bài "Hai chú chuột túi" – vinhdinhcoder.net (bài gốc Kangaroo – HackerRank).
Lời mở đầu
Một bài "khởi động" rất dễ thương nhưng chứa một bài học quan trọng: mô phỏng thì phải biết khi nào dừng. Nếu cứ cho hai chú nhảy "đến khi nào gặp nhau thì thôi" thì với ví dụ 2 chương trình sẽ chạy mãi không dừng. Mình sẽ đi từ cách mô phỏng từng lần nhảy (đủ cho subtask 1, và đủ cho cả bài nếu chọn giới hạn vòng lặp khéo), rồi tới cách dùng toán trả lời ngay bằng một phép chia hết.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 30 test, mỗi test chỉ là một dòng 4 số. Mình đã kiểm tra: test 1–12 đúng là thoả điều kiện subtask 1 ($x_2 \le 100$, $v_1, v_2 \le 100$), test 13–30 là subtask 2.
| Nhóm | Test | $x_2$ lớn nhất | $v$ lớn nhất | YES / NO | Số test $v_1 \le v_2$ | Số lần nhảy tới lúc gặp (lớn nhất) |
|---|---|---|---|---|---|---|
| Subtask 1 | 1–12 | 100 | 100 | 6 / 6 | 4 | 99 (test 8) |
| Subtask 2 | 13–30 | 10.000 | 10.000 | 8 / 10 | 4 | 10.000 (test 15) |
- Cột cuối là số lần nhảy $t$ tới lúc hai chú gặp nhau (chỉ tính các test
YES). Ở subtask 2 có test phải nhảy tới 10.000 lần mới gặp – đây chính là "cái bẫy" cho cách mô phỏng với giới hạn vòng lặp quá nhỏ. - Có khá nhiều test $v_1 \le v_2$ (chú 1 nhảy không xa hơn chú 2) – các test này đáp án luôn là
NO, và cũng là các test làm vòng lặp "chạy mãi" nếu không có điểm dừng.
Kết quả chạy thật của các cách bên dưới theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 LIM = 100 | Cách 1 LIM = $10^4$ | Cách 2 $O(1)$ |
|---|---|---|---|---|---|
| Subtask 1 (40%) | $x_2 \le 100$, $v_1, v_2 \le 100$ | 1–12 | 12/12 | 12/12 | 12/12 |
| Subtask 2 (60%) | đầy đủ: $x_2, v_1, v_2 \le 10\,000$ | 13–30 | 16/18 | 18/18 | 18/18 |
Ý tưởngTheo dõi khoảng cách giữa hai chú
Vì $x_1 < x_2$ nên lúc đầu chú 1 đứng phía sau. Sau mỗi lần nhảy, khoảng cách $b - a$ (chú 2 trừ chú 1) thay đổi đúng một lượng $v_2 - v_1$:
- Nếu $v_1 \le v_2$: khoảng cách không giảm → chú 1 không bao giờ đuổi kịp →
NO. - Nếu $v_1 > v_2$: mỗi lần nhảy khoảng cách giảm đi $v_1 - v_2$. Khoảng cách sẽ chạm đúng 0 (gặp nhau) hoặc "nhảy qua" 0 thành số âm (chú 1 vượt lên trước mà không đứng chung chỗ nào) → từ đó chú 1 luôn ở trước, không gặp nữa.
Em nhập 4 số rồi bấm Tiếp để xem hai chú nhảy từng lượt trên trục số:
Cách 1Mô phỏng từng lần nhảy
Cách tự nhiên nhất: dùng hai biến a, b là vị trí hiện tại của hai chú, mỗi vòng lặp kiểm tra a == b, nếu chưa thì cho cả hai nhảy thêm một lần.
while(a != b) { a += v1; b += v2; } thì với ví dụ 2 ($v_1 < v_2$), hoặc khi chú 1 nhảy vượt qua chú 2 mà không đứng chung chỗ nào, điều kiện a != b đúng mãi → chương trình chạy mãi không dừng (bị quá thời gian). Ta cần 2 điểm dừng:
- Chú 1 đã vượt chú 2 (
a > b): từ lúc này chú 1 luôn ở phía trước (vì muốn vượt được thì $v_1 > v_2$), không thể gặp nữa → dừng, inNO. - Giới hạn số lần nhảy
LIM: dùng cho trường hợp $v_1 \le v_2$ – chú 1 không bao giờ vượt được, nên điểm dừng 1 không bao giờ xảy ra.
Vậy chọn LIM bằng bao nhiêu? Nếu hai chú gặp nhau ở lần nhảy thứ $t$ thì mỗi lần khoảng cách giảm ít nhất 1, nên $t \le x_2 - x_1$:
- Với subtask 1: $t \le x_2 - x_1 \le 100$, nên
LIM = 100là đủ. - Với cả bài: $t \le x_2 - x_1 \le 10\,000$, nên phải dùng
LIM = 10000. Chỉ $10^4$ vòng lặp, chạy trong nháy mắt.
- Thứ tự trong vòng lặp: kiểm tra
a == btrước rồi mới nhảy – nhờ vậy trường hợp gặp nhau ở đúng lần nhảy thứLIMvẫn được xét (vòng lặp chạy vớit = 0..LIM). - Dòng
if(a > b) break;không bắt buộc cho đúng (đã cóLIM), nhưng giúp dừng sớm khi chú 1 đã vượt. - Vị trí lớn nhất là $10\,000 + 10\,000 \cdot 10\,000$ $\approx 10^8$, vẫn vừa kiểu
int; mình dùnglong longcho chắc.
Kết quả chạy thật:
- Với
LIM = 100: bản C++ đúng 28/30 test, sai test 15, 29, chạy lâu nhất 0.003s. Bản Python đúng 28/30 test, sai test 15, 29, chạy lâu nhất 0.017s. Subtask 1 đúng hết, nhưng 2 test của subtask 2 cần hơn 100 lần nhảy mới gặp nhau (test 15 và 29) nên in nhầmNO→ mất trọn 60% của subtask 2. - Với
LIM = 10000: bản C++ đúng 30/30 test, chạy lâu nhất 0.003s. Bản Python đúng 30/30 test, chạy lâu nhất 0.022s. Full điểm.
Cách 2Giải phương trình – $O(1)$
Thay vì cho hai chú nhảy thật, ta hỏi thẳng: có số nguyên $t \ge 0$ nào để hai vị trí bằng nhau không?
$$x_1 + t \cdot v_1 = x_2 + t \cdot v_2 \iff t \cdot (v_1 - v_2) = x_2 - x_1.$$
- Vế phải $x_2 - x_1 > 0$ (vì $x_1 < x_2$).
- Nếu $v_1 = v_2$: vế trái bằng 0 ≠ vế phải → vô nghiệm. Nếu $v_1 < v_2$: vế trái $\le 0$ → vô nghiệm. Vậy bắt buộc $v_1 > v_2$.
- Khi $v_1 > v_2$: $t = \dfrac{x_2 - x_1}{v_1 - v_2}$ là số dương, cần thêm $t$ nguyên ⇔ $(x_2 - x_1)$ chia hết cho $(v_1 - v_2)$.
YES khi và chỉ khi $v_1 > v_2$ và $(x_2 - x_1) \bmod (v_1 - v_2) = 0$.Thử với ví dụ 1: $v_1 - v_2 = 3 - 2 = 1 > 0$, $x_2 - x_1 = 4$ chia hết cho 1 → YES, gặp nhau ở $t = 4$. Ví dụ 2: $v_1 = 2 < v_2 = 3$ → NO.
- Điều kiện
v1 > v2phải đứng trước phép%: nhờ toán tử&&"ngắt mạch", khi $v_1 = v_2$ máy không tính% 0(chia cho 0 làm chương trình bị lỗi). - Điều kiện $v_1 > v_2$ còn đảm bảo $t > 0$; nếu bỏ nó đi, ví dụ
0 2 5 3có $(5 - 0) \bmod (2 - 3) = 0$ trong C++ và sẽ in nhầmYES(ứng với $t = -5$, tức là "quá khứ").
Kết quả chạy thật: Bản C++ đúng 30/30 test, chạy lâu nhất 0.003s. Bản Python đúng 30/30 test, chạy lâu nhất 0.016s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Mô phỏng, LIM = 100 | C++ | 28/30 | 0.003s | Sai test 15, 29 → mất subtask 2 |
| Python | 28/30 | 0.017s | Sai test 15, 29 → mất subtask 2 | |
| 1. Mô phỏng, LIM = $10^4$ | C++ | 30/30 | 0.003s | Full điểm |
| Python | 30/30 | 0.022s | Full điểm | |
| 2. Công thức $O(1)$ | C++ | 30/30 | 0.003s | Full điểm |
| Python | 30/30 | 0.016s | Full điểm |
LIM = 100) sai 2 test có số lần nhảy lớn. Bài học: khi mô phỏng, hãy tự hỏi "trường hợp xấu nhất phải lặp bao nhiêu lần?" – ở bài này là $x_2 - x_1 \le 10^4$. Còn nếu biến đổi được thành phương trình như cách 2 thì chẳng cần lặp lần nào.
Nhận xét
Đăng nhận xét