Bóng nảy (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng C1, C2)

Nguồn: Tin học trẻ 2025 – Vòng loại QG đợt 1 – Bảng C1, C2 Độ khó: Trung bình Mô phỏng Trải phẳng (phản xạ)

Đề bài

Trên mặt phẳng toạ độ có một hình chữ nhật với 4 đỉnh $(0, 0)$, $(M, 0)$, $(0, N)$, $(M, N)$ (rộng $M$, cao $N$). Tại thời điểm $0$, một quả bóng được ném đi từ góc $(0, 0)$ theo hướng vector $d = (d_x, d_y)$. Bóng bay với vận tốc không đổi: mỗi giây bóng đi từ điểm $(x, y)$ tới điểm $(x + d_x, y + d_y)$.

Khi chạm vào cạnh hay góc của hình chữ nhật, bóng nảy lại và đổi hướng:

chạm cạnh $y = 0$ hoặc $y = N$: hướng $(d_x, d_y)$ đổi thành $(d_x, -d_y)$;
chạm cạnh $x = 0$ hoặc $x = M$: hướng $(d_x, d_y)$ đổi thành $(-d_x, d_y)$;
chạm một trong 4 góc: hướng $(d_x, d_y)$ đổi thành $(-d_x, -d_y)$.

Coi bóng là một điểm và không bao giờ mất năng lượng. Hãy đếm xem từ thời điểm $0$ tới thời điểm $T$ quả bóng đã chạm cạnh bao nhiêu lần, biết rằng chạm góc được tính là 2 lần chạm cạnh và vị trí xuất phát $(0, 0)$ không được tính là một lần chạm.

Ví dụ $N = 3$, $M = 5$, $d = (2, 1)$: quỹ đạo của bóng trong 9 giây đầu, mỗi chấm đỏ là một lần chạm cạnh (tổng cộng $\lfloor 18/5 \rfloor$ $+ \lfloor 9/3 \rfloor$ $= 6$ lần), chấm xanh là vị trí lúc $t = 9$.

Dữ liệu vào: một dòng gồm 5 số nguyên $N, M, T, d_x, d_y$ $(0 < N, M, T \le 10^9;\ 0 \le d_x, d_y \le 10^9)$.

Kết quả: một số nguyên là số lần bóng chạm cạnh.

Subtask: mỗi subtask 20% số điểm.

Subtask 1: $T \le 10^5$.
Subtask 2: $N, M \le 10^3$.
Subtask 3: $d_x = d_y = 1$.
Subtask 4: $d_x = 0$ hoặc $d_y = 0$.
Subtask 5: không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 1 GB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng C1, C2. Đề được mình viết lại cho dễ đọc (đề gốc có chỗ ghi nhầm "cạnh của hình vuông", thực ra là hình chữ nhật).

Ví dụ – input

5 5 100 1 1

Ví dụ – output

Giải thích: hình vuông $5 \times 5$, bóng đi theo đường chéo $(1, 1)$: sau 5 giây chạm góc $(5, 5)$, nảy ngược về, sau 5 giây nữa chạm góc $(0, 0)$, ... Cứ 5 giây lại chạm một góc (tính 2 lần), trong 100 giây có $20$ lần chạm góc, tức là $40$ lần chạm cạnh.

Hai chi tiết cần hiểu đúng:

Chạm cạnh đúng tại thời điểm $T$ vẫn được tính (như ví dụ: lần chạm góc thứ 20 xảy ra đúng lúc $t = 100$).
Khi $d_x = 0$ (hoặc $d_y = 0$) bóng chạy dọc theo cạnh $x = 0$ (hoặc $y = 0$): việc "trượt dọc" này không tính là chạm; chỉ tính các lần bóng đập vào cạnh đối diện hướng đi. Cách hiểu này khớp với bộ chấm chính thức (lời giải bên dưới được 100 điểm).

Lời mở đầu

Bài này nhìn thì có vẻ là bài mô phỏng hình học rắc rối: bóng nảy qua nảy lại, đổi hướng, lại còn chạm góc tính 2 lần... Nhưng với $T$, $d_x$, $d_y$ tới $10^9$ thì số lần chạm có thể lên tới $2 \cdot 10^{18}$ – không thể mô phỏng từng lần chạm. Mình sẽ đi từ cách mô phỏng từng giây (ăn subtask 1) tới một mẹo rất đẹp hay dùng trong các bài phản xạ: trải phẳng hình chữ nhật – khi đó đáp án chỉ còn là 2 phép chia.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test25 test Ý tưởngtrải phẳng Cách 1mô phỏng O(T)Cách 2công thức O(1)Tổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE gồm 25 test (mình tự sinh theo đúng ràng buộc của đề, mỗi subtask 5 test). Mình đã kiểm tra từng test thoả đúng điều kiện subtask của nó. Lời giải cuối (cách 2) mình đã nộp thử trên bộ chấm chính thức tinhoctre.vn và được 100 điểm.

Nhóm	Test	$T$ lớn nhất	$N, M$ lớn nhất	$d_x, d_y$ lớn nhất	Đáp án lớn nhất	Số test có chạm góc
Subtask 1	1–5	100.000	$4{,}8 \cdot 10^{8}$	$10^{9}$	$2{,}0 \cdot 10^{9}$	3
Subtask 2	6–10	$10^{9}$	1.000	$10^{9}$	$2{,}4 \cdot 10^{16}$	5
Subtask 3	11–15	$10^{9}$	$10^{9}$	1	$10^{9}$	4
Subtask 4	16–20	$10^{9}$	$10^{9}$	$10^{9}$	$1{,}7 \cdot 10^{16}$	0
Subtask 5	21–25	$10^{9}$	$10^{9}$	$10^{9}$	$2{,}0 \cdot 10^{18}$	1

Đáp án lớn nhất tới $2 \cdot 10^{18}$ (test 21: hình vuông $1 \times 1$, $d = (10^9, 10^9)$, $T = 10^9$) – vẫn vừa long long (tối đa khoảng $9{,}2 \cdot 10^{18}$) nhưng phải cẩn thận khi nhân.
Nhiều test có chạm góc (cột cuối), kể cả test 2: chỉ trong 1 giây bóng đã chạm góc $10^9$ lần!
Subtask 4 có test $d_x = 0$, $d_y = 1$, $T = N = 10^9$: bóng chạm đúng góc $(0, N)$ tại thời điểm $T$ – theo cách hiểu ở trên chỉ tính 1 lần (đáp án là 1).

Kết quả chạy thật của 2 cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 $O(T)$	Cách 2 $O(1)$
Subtask 1 (20%)	$T \le 10^5$	1–5	5/5	5/5
Subtask 2 (20%)	$N, M \le 10^3$	6–10	0/5	5/5
Subtask 3 (20%)	$d_x = d_y = 1$	11–15	0/5	5/5
Subtask 4 (20%)	$d_x = 0$ hoặc $d_y = 0$	16–20	1/5	5/5
Subtask 5 (20%)	không ràng buộc thêm	21–25	1/5	5/5

Ý tưởngHai trục độc lập và mẹo trải phẳng

Nhận xét 1 – hai trục độc lập. Chạm cạnh dọc ($x = 0$ hoặc $x = M$) chỉ đổi dấu $d_x$, chạm cạnh ngang chỉ đổi dấu $d_y$; còn chạm góc thì đổi cả hai – đúng bằng "chạm cạnh dọc và chạm cạnh ngang cùng lúc". Vậy chuyển động theo phương $x$ hoàn toàn không phụ thuộc phương $y$ và ngược lại:

toạ độ $x$ chạy qua lại trên đoạn $[0, M]$ với tốc độ $d_x$, mỗi lần đụng đầu mút là một lần chạm cạnh dọc;
toạ độ $y$ chạy qua lại trên đoạn $[0, N]$ với tốc độ $d_y$, mỗi lần đụng đầu mút là một lần chạm cạnh ngang;
chạm góc = hai trục đụng đầu mút cùng lúc → tự động được đếm 2 lần. Đúng như đề yêu cầu!

Nhận xét 2 – trải phẳng. Thay vì cho bóng nảy ngược lại, hãy tưởng tượng ta "lật" hình chữ nhật qua cạnh vừa chạm (như soi gương) và cho bóng đi thẳng sang hình chữ nhật mới. Lặp lại, ta được cả một lưới các bản sao, còn bóng đi trên một đường thẳng từ $(0, 0)$ tới $(d_x T, d_y T)$. Mỗi lần bóng thật chạm cạnh dọc ⇔ đường thẳng cắt một vạch $x = kM$; chạm cạnh ngang ⇔ cắt một vạch $y = kN$.

Em nhập dữ liệu rồi bấm Tiếp để xem từng giây: bên trái là bóng nảy thật, bên phải là đường thẳng trên hình trải phẳng – số chấm đỏ hai bên luôn bằng nhau:

N = M = T = dx = dy =

Ví dụ nhanh:

Cách 1Mô phỏng từng giây – O(T)

Dùng nhận xét 1, ta mô phỏng riêng từng trục. Mỗi giây, trên một trục (vị trí $p \in [0, M]$, hướng $s = \pm 1$) bóng đi thêm quãng đường $d$:

Khoảng cách tới bức tường phía trước là $w = M - p$ (nếu $s = +1$) hoặc $w = p$ (nếu $s = -1$). Nếu $d < w$: chưa chạm, chỉ cần $p \mathrel{+}= s \cdot d$.
Ngược lại bóng chạm tường lần đầu (đếm 1), đứng ở tường, đổi hướng, còn lại $d - w$.
Quãng còn lại cứ mỗi $M$ đơn vị lại chạm thêm 1 tường: có $k = \lfloor (d - w) / M \rfloor$ lần chạm nữa; nếu $k$ lẻ thì bóng sang tường đối diện và đổi hướng thêm 1 lần. Cuối cùng đi nốt $(d - w) \bmod M$.

Vì dùng phép chia nên dù $d_x = 10^9$ và $M = 1$ (một giây chạm $10^9$ lần), mỗi giây vẫn chỉ tốn $O(1)$. Tổng độ phức tạp $O(T)$.

C++▶ Chạy tay từng dòng codeCách 1: mỗi giây mô phỏng riêng trục x và trục y, đếm số lần chạm bằng phép chia.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Khi T > 12 (như test đề T = 100), khung chạy tay tua nhanh các giây ở giữa (vẫn chạy đúng code, chỉ không hiện từng bước).

Hàm moveAxis nhận p, s theo tham chiếu (&) để cập nhật vị trí và hướng sau mỗi giây.
Điều kiện if(d < w) dùng dấu < chứ không phải <=: nếu $d = w$ thì bóng chạm tường đúng cuối giây – vẫn phải đếm.
Nếu $d = 0$ (ví dụ $d_x = 0$) thì trục đó đứng yên, không bao giờ "chạm" – đúng với cách hiểu bóng trượt dọc cạnh.
Ở góc, hai lời gọi moveAxis (trục $x$ và trục $y$) mỗi lời gọi đếm 1 → góc được tính 2 lần, không cần xử lý riêng.

Không gian$O(1)$

Thời gian$O(T)$

Kết quả chạy thật: bản C++ đúng 7/25 test, quá thời gian test 6–17, 19–21, 23–25 (các test đúng chạy lâu nhất 0.016s). Qua trọn subtask 1 ($T \le 10^5$) và thêm test 18, 22 (có $T$ nhỏ); các test còn lại có $T$ cỡ $10^8$–$10^9$ giây nên bị quá thời gian. Bản Python đúng 7/25 test, quá thời gian test 6–17, 19–21, 23–25 (các test đúng chạy lâu nhất 0.972s).

Cách 2Trải phẳng – O(1)

Theo nhận xét 2, trên hình trải phẳng toạ độ $x$ của bóng tại thời điểm $t$ đơn giản là $d_x \cdot t$ (không còn nảy nữa). Bóng chạm cạnh dọc mỗi khi $d_x \cdot t$ đi qua một bội dương của $M$: $M, 2M, 3M, \dots$ Trong khoảng $(0, T]$, $d_x \cdot t$ tăng từ $0$ tới $d_x T$ nên số bội của $M$ đi qua là

$$\text{số lần chạm cạnh dọc} = \left\lfloor \frac{d_x \cdot T}{M} \right\rfloor, \qquad \text{số lần chạm cạnh ngang} = \left\lfloor \frac{d_y \cdot T}{N} \right\rfloor.$$

Đáp án

$$\left\lfloor \frac{d_x T}{M} \right\rfloor + \left\lfloor \frac{d_y T}{N} \right\rfloor$$ Chạm góc tự động được đếm 2 lần (cả hai phân số cùng "qua vạch" một lúc), mốc $(0, 0)$ không bị đếm (chỉ đếm bội dương), chạm đúng lúc $T$ được đếm (dùng phần nguyên của $\le$).

Thử ví dụ: $\lfloor 1 \cdot 100 / 5 \rfloor$ $+ \lfloor 1 \cdot 100 / 5 \rfloor$ $= 20 + 20$ $= 40$ ✔. Với hình minh hoạ trong đề: $\lfloor 2 \cdot 9 / 5 \rfloor$ $+ \lfloor 1 \cdot 9 / 3 \rfloor$ $= 3 + 3$ $= 6$ ✔.

C++▶ Chạy tay từng dòng codeCách 2: trải phẳng – đáp án là ⌊dx·T/M⌋ + ⌊dy·T/N⌋.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

$d_x \cdot T \le 10^9 \cdot 10^9 = 10^{18}$ vẫn vừa long long; tổng hai phần tối đa $2 \cdot 10^{18}$ cũng vừa. Nhớ khai báo cả 5 biến là long long để phép nhân không bị tràn int.
Không cần xử lý riêng $d_x = 0$ hay $d_y = 0$: phép chia cho ra 0 lần chạm ở trục đó.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 25/25 test, chạy lâu nhất 0.003s. Bản Python đúng 25/25 test, chạy lâu nhất 0.018s (Python có số nguyên lớn nên càng không lo tràn số). Full điểm – đây cũng là cách mình đã nộp trên tinhoctre.vn được 100 điểm.

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 từng giây	C++	7/25	0.016s	quá giờ 6–17, 19–21, 23–25 – ăn subtask 1
	Python	7/25	0.972s	quá giờ 6–17, 19–21, 23–25
2. Trải phẳng – $O(1)$	C++	25/25	0.003s	Đúng hết
	Python	25/25	0.018s	Đúng hết

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây). Cách mô phỏng từng giây chỉ ăn được subtask 1 vì $T$ lên tới $10^9$; cách trải phẳng cho đáp án bằng 2 phép chia. Mẹo "trải phẳng / soi gương" còn dùng được trong rất nhiều bài: tia sáng phản xạ trong hộp gương, bi-a, robot dội tường... – hễ thấy "nảy lại" thì hãy thử biến nó thành "đi thẳng".

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán