Khoảng cách hai xe

Nguồn: CLUE OJ Độ khó: Dễ Nhập xuất Số học Long long

Đề bài

Một người đi xe đạp với vận tốc $10$ km/h và một người đi xe máy với vận tốc $30$ km/h. Hai người xuất phát cùng lúc, cùng một chỗ và đi cùng một hướng.

Hỏi sau $t$ giờ, hai người cách nhau bao nhiêu ki-lô-mét?

Dữ liệu vào: Một dòng chứa số nguyên dương $t$.

Kết quả: In ra khoảng cách giữa hai người (đơn vị km).

Giới hạn:

• $1 \le t \le 10^9$

Subtask:

• Subtask 1 (40% số điểm): $t \le 15$.
• 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.

Ví dụ 1 – input

7

Ví dụ 1 – output

140

Ví dụ 2 – input

1

Ví dụ 2 – output

20

Giải thích: Ví dụ 1: mỗi giờ xe máy đi xa hơn xe đạp $30 - 10 = 20$ km, sau $7$ giờ hai xe cách nhau $20 \cdot 7 = 140$ km.

Nguồn: phỏng theo bài "KHOẢNG CÁCH HAI XE" – vinhdinhcoder.net.

Lời mở đầu

Một bài toán chuyển động lớp 5 – đáp án chỉ là một phép nhân. Nhưng chính vì "dễ quá" nên rất nhiều bạn nộp code dùng int và chỉ nhận được 40 điểm. Bài viết này sẽ giải thích vì sao, kèm kết quả chạy thật trên bộ test của từng phiên bản code (cả các phiên bản bị bẫy).

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ộ test20 testÝ tưởngd = 20tCách 1int – 40 điểmCách 2long longTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test là một số $t$. Mình đã kiểm tra: test 1–8 đúng là thoả điều kiện subtask 1 ($t \le 15$), test 9–20 là subtask 2 (trong đó có 2 test $t$ vẫn nhỏ).

Nhóm	Test	$t$ nhỏ nhất	$t$ lớn nhất	Số test $20t$ vượt $2^{31} - 1$
Subtask 1	1–8	1	15	0
Subtask 2	9–20	3	1.000.000.000	7

Kiểu int chứa được tối đa $2^{31} - 1 = 2\,147\,483\,647$, nên $20t$ bị tràn ngay khi $t \ge 107\,374\,183$ (vì $20 \cdot 107\,374\,182$ $= 2\,147\,483\,640$ vẫn vừa, còn cộng thêm 20 là vượt). Với $t = 10^9$ đáp án là $2 \cdot 10^{10}$, gấp gần 10 lần sức chứa của int.

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 int	Cách 2 long long
Subtask 1 (40%)	$t \le 15$	1–8	8/8	8/8
Subtask 2 (60%)	$t \le 10^9$	9–20	5/12	12/12

Ý tưởngVận tốc tương đối: mỗi giờ bỏ xa thêm 20 km

Sau $t$ giờ, xe đạp đi được $10t$ km, xe máy đi được $30t$ km. Vì đi cùng hướng từ cùng một chỗ, khoảng cách là hiệu hai quãng đường:

$$d = 30t - 10t = (30 - 10) \cdot t = 20t \text{ (km)}.$$

Em nhập $t$ rồi bấm Tiếp để xem hai xe chạy từng giờ; bước cuối so sánh kết quả với sức chứa của int:

t =

Ví dụ nhanh:

Cách 1Dùng int – chỉ được 40 điểm

C++▶ Chạy tay từng dòng codeCách 1: tính bằng int – thử t = 150000000 để thấy tràn số.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. (30 - 10) * t: 30 - 10 là hằng int, t cũng là int nên phép nhân thực hiện trên 32 bit.
2. Khi kết quả thật vượt $2^{31} - 1$, máy chỉ giữ lại 32 bit thấp → ra một số "vô nghĩa", thường là số âm.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 13/20 test, sai ở test 9–13, 15, 19; test đúng chạy lâu nhất 0.00s. Subtask 1 đúng 8/8; ở subtask 2 có 7 test có $t \ge 107\,374\,183$ nên bị tràn số – ví dụ test 9 in ra -1474836480 trong khi đáp án là 20000000000. Mất trọn 60% của subtask 2 → chỉ được 40 điểm.

Bẫy 1: long long d = 20 * t; với t vẫn là int

int t;
    cin >> t;
    long long d = 20 * t;      // 20 * t vẫn tính bằng int rồi mới gán!
    cout << d;

Biến d là long long nhưng vế phải 20 * t là int * int, được tính (và tràn) trước rồi mới gán. Chạy thật: code này đúng 13/20 test, sai ở test 9–13, 15, 19; test đúng chạy lâu nhất 0.00s – y hệt cách 1. Sửa: khai báo t là long long, hoặc viết 20LL * t.

Bẫy 2: cộng vận tốc

long long t;
    cin >> t;
    cout << (30 + 10) * t;     // SAI: cộng vận tốc là công thức của hai xe đi NGƯỢC chiều

Cộng hai vận tốc ($10 + 30 = 40$) là công thức khi hai xe đi ngược chiều (xa nhau dần theo hai hướng). Đề nói cùng một hướng nên phải trừ. Chạy thật: code này đúng 0/20 test, sai ở test 1–20 – ngay test 1 đã in 280 thay vì 140.

Cách 2Dùng long long – full điểm

Khai báo t là long long (64 bit, chứa tới khoảng $9{,}2 \cdot 10^{18}$). Khi đó (30 - 10) * t là int * long long, máy tự đổi 20 lên long long rồi mới nhân, không còn tràn.

C++▶ Chạy tay từng dòng codeCách 2: t là long long nên 20 · t tính bằng 64 bit.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Chỉ khác cách 1 ở kiểu của t và d.
2. Python: số nguyên không bao giờ tràn nên viết thẳng công thức.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: Bản C++ đúng 20/20 test; test đúng chạy lâu nhất 0.00s. Bản Python đúng 20/20 test; test đúng chạy lâu nhất 0.02s.

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. Dùng int	C++	13/20	0.00s	Tràn số ở test 9–13, 15, 19 → mất subtask 2, được 40 điểm
Bẫy: long long d = 20 * t với t là int	C++	13/20	0.00s	Vẫn tràn ở test 9–13, 15, 19
Bẫy: cộng vận tốc	C++	0/20	0.00s	Sai công thức, sai cả test ví dụ
2. Dùng long long	C++	20/20	0.00s	Full điểm
	Python	20/20	0.02s	Full điểm

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 – mọi cách đều chạy tức thì. Thói quen tốt: trước khi code, nhân thử giới hạn lớn nhất ($20 \cdot 10^9 = 2 \cdot 10^{10}$) và so với $2{,}1 \cdot 10^9$ của int. Vượt thì dùng long long ngay từ lúc khai báo biến đọc vào.

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 😇