Tiền điện thoại
Đề bài
Hoa gọi điện cho Huệ để hỏi bài. Mỗi phút gọi điện tốn $x$ đồng và cuộc gọi kéo dài $t$ phút. Hỏi Hoa phải trả bao nhiêu tiền cho cuộc gọi này?
Dữ liệu vào: Một dòng gồm hai số nguyên dương $x$ và $t$ cách nhau bởi dấu cách.
Kết quả: In ra số tiền Hoa phải trả.
Giới hạn: $1 \le x, t \le 10^6$.
Subtask:
- Subtask 1 (40% số điểm): $x, t \le 10^4$.
- 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.
3711 5085188704351 11Giải thích: Ví dụ 1: mỗi phút tốn 3711 đồng, gọi 5085 phút nên phải trả $3711 \cdot 5085 = 18\,870\,435$ đồng. Ví dụ 2: $1 \cdot 1 = 1$ đồng.
Nguồn: phỏng theo bài "TIỀN ĐIỆN THOẠI" – vinhdinhcoder.net.
Lời mở đầu
Đọc đề xong chắc em nào cũng cười: "nhân hai số với nhau thôi mà!". Đúng là vậy, nhưng đây lại là bài "bẫy" kinh điển cho các bạn mới học C++: chỉ cần chọn sai kiểu dữ liệu là mất ngay 60% số điểm, hoặc tệ hơn là sai luôn cả test ví dụ. Trong bài này mình sẽ thử lần lượt 3 cách khai báo – int, double, long long – chấm thật trên bộ test để các bạn thấy tận mắt chuyện gì xảy ra với từng cách.
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ó 20 test, mỗi test chỉ là một dòng 2 số. Mình đã kiểm tra: test 1–8 đúng là thoả điều kiện subtask 1 ($x, t \le 10^4$), test 9–20 là subtask 2.
| Nhóm | Test | $x$ lớn nhất | $t$ lớn nhất | Đáp án lớn nhất | Số test đáp án vượt INT_MAX |
|---|---|---|---|---|---|
| Subtask 1 | 1–8 | 10.000 | 10.000 | 100.000.000 | 0 |
| Subtask 2 | 9–20 | 1.000.000 | 1.000.000 | 1.000.000.000.000 | 11 |
- Ở subtask 1 đáp án lớn nhất là $10^4 \cdot 10^4 = 10^8$ – vẫn nằm gọn trong kiểu
int. - Ở subtask 2 đáp án lên tới $10^6 \cdot 10^6 = 10^{12}$, và có tới 11/12 test có đáp án vượt quá
INT_MAX$= 2\,147\,483\,647$. Đây chính là chỗ "bắt lỗi" kiểuint.
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 1int | Cách 2double | Cách 3long long |
|---|---|---|---|---|---|
| Subtask 1 (40%) | $x, t \le 10^4$ | 1–8 | 8/8 | 4/8 | 8/8 |
| Subtask 2 (60%) | đầy đủ: $x, t \le 10^6$ | 9–20 | 1/12 | 0/12 | 12/12 |
Ý tưởngSố tiền thì dễ, chọn kiểu dữ liệu mới khó
Số tiền phải trả đơn giản là $x \cdot t$. Câu hỏi thật sự là: biến nào chứa nổi số đó? Mỗi kiểu số nguyên trong C++ là một "ô nhớ" có số bit cố định:
| Kiểu | Số bit | Giá trị lớn nhất | Khoảng |
|---|---|---|---|
int | 32 | $2^{31} - 1 = 2\,147\,483\,647$ | $\approx 2{,}1 \cdot 10^9$ |
long long | 64 | $2^{63} - 1$ $= 9\,223\,372\,036\,854\,775\,807$ | $\approx 9{,}2 \cdot 10^{18}$ |
Đáp án lớn nhất của bài là $10^{12}$: lớn hơn int gần 500 lần nhưng rất nhỏ so với long long. Khi kết quả phép nhân int * int vượt quá 32 bit, máy không báo lỗi mà lặng lẽ vứt bỏ các bit thừa ở phía trên, chỉ giữ 32 bit thấp; bit cao nhất (bit 31) lại là bit dấu, nên kết quả có thể thành một số âm "trời ơi đất hỡi". Hiện tượng này gọi là tràn số (overflow).
Em nhập $x$, $t$ rồi bấm Tiếp để xem từng bit của số tiền bị "cắt" như thế nào khi cất vào ô nhớ int:
Cách 1Dùng int – đúng subtask 1
Cách viết "tự nhiên" nhất của các bạn mới học: khai báo int, nhân rồi in.
Với subtask 1, $x \cdot t \le 10^8 < 2\,147\,483\,647$ nên mọi thứ đều ổn. Nhưng khi $x, t$ lên tới $10^6$, tích x * t (kiểu int) bị tràn. Ví dụ (em có thể thử ngay trong khung chạy tay ở trên):
131072 32768: đáp án đúng $2^{17} \cdot 2^{15}$ $= 2^{32}$ $= 4\,294\,967\,296$, nhưng 32 bit thấp của nó toàn là 0 → chương trình in ra 0.46341 46342: đáp án đúng $2\,147\,534\,622$, chỉ hơnINT_MAXmột chút, bit dấu bật lên → in ra số âm −2147432674.1000000 999999: đáp án đúng $999\,999\,000\,000$ nhưng in ra −728379968.
Kết quả chạy thật: Bản C++ đúng 9/20 test, sai test 9–10, 12–20, chạy lâu nhất 0.003s. Các test đúng là test 1–8, 11: toàn bộ subtask 1, cộng thêm 1 test của subtask 2 "may mắn" có đáp án chỉ $10^6$ (vẫn vừa int). Mất trọn 60% điểm của subtask 2.
Cách 2"Dùng double cho chắc" – sai cả ví dụ!
Có bạn nghĩ: double chứa được tới $10^{308}$, vậy dùng double là hết lo tràn số. Về giá trị thì đúng là $10^{12}$ vẫn được lưu chính xác trong double. Nhưng lỗi lại nằm ở chỗ in ra:
cout << (double) làm tròn còn 6 chữ số có nghĩa, và nếu số có từ 7 chữ số phần nguyên trở lên thì chuyển sang dạng khoa học. Với ví dụ 1, máy in ra 1.88704e+07 thay vì 18870435 → sai ngay test đầu tiên!Muốn cứu cách này thì phải viết cout << fixed << setprecision(0) << x * t; – nhưng đó là "chữa cháy". Đáp án là số nguyên thì nên dùng kiểu số nguyên: vừa chính xác tuyệt đối, vừa không phải lo định dạng.
Kết quả chạy thật: Bản C++ đúng 4/20 test, sai test 1, 3, 7–20, chạy lâu nhất 0.003s. Chỉ đúng 4 test có đáp án nhỏ hơn 1 triệu (test 2, 4–6) – còn tệ hơn cả cách 1, mất điểm cả subtask 1.
Cách 3Dùng long long – full điểm
Chỉ cần đổi kiểu của $x$, $t$ thành long long (64 bit). Khi đó x * t là phép nhân long long * long long, kết quả tối đa $10^{12}$ – còn cách giới hạn $9{,}2 \cdot 10^{18}$ cả triệu lần.
- Phải khai báo chính
x,tlàlong long(hoặc ép kiểu một thừa số:1LL * x * t). Nếu vẫn đểint x, trồi viếtlong long ans = x * t;thì phép nhân vẫn tính bằngint, tràn xong mới gán vàoans→ sai y như cách 1. - Với Python thì không cần lo: số nguyên Python tự mở rộng, không bao giờ tràn.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.015s. Full đ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. int x, t | C++ | 9/20 | 0.003s | Tràn số ở 11 test có đáp án vượt INT_MAX |
2. double x, t | C++ | 4/20 | 0.003s | cout in dạng 1.88704e+07 khi kết quả từ 1 triệu trở lên |
3. long long x, t | C++ | 20/20 | 0.003s | Full điểm |
| Python | 20/20 | 0.015s | Full điểm |
int ($\approx 2 \cdot 10^9$): vượt thì dùng long long; đáp án là số nguyên thì đừng dùng double.
Nhận xét
Đăng nhận xét