Tính lượng nước cho hồ cá
Đề bài
Nhà Tèo vừa đào một hồ nuôi cá có dạng hình hộp chữ nhật: mặt hồ là hình chữ nhật kích thước $a \times b$ mét và hồ sâu $h$ mét.
Tèo muốn bơm nước cho đầy hồ. Hãy giúp Tèo tính xem cần bơm bao nhiêu lít nước. Biết $1$ m³ $= 1000$ lít.
Dữ liệu vào: Một dòng gồm ba số nguyên dương $a, b, h$ cách nhau bởi dấu cách.
Kết quả: In ra số lít nước cần bơm.
Giới hạn: $1 \le a, b, h \le 10^4$.
Subtask:
- Subtask 1 (40% số điểm): $a, b, h \le 10$.
- 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.
4 8 51600001 1 11000Giải thích: Ví dụ 1: thể tích hồ là $4 \cdot 8 \cdot 5 = 160$ m³, tức $160 \cdot 1000 = 160\,000$ lít.
Nguồn: phỏng theo bài "TÍNH TOÁN LƯỢNG NƯỚC" – vinhdinhcoder.net.
Lời mở đầu
Một bài hình học lớp 5: thể tích hình hộp chữ nhật bằng dài × rộng × cao, rồi đổi m³ ra lít. Nhưng nhân bốn số với nhau thì kết quả lớn rất nhanh: $10^4 \cdot 10^4 \cdot 10^4 \cdot 1000 = 10^{15}$ lít – gấp gần nửa triệu lần giới hạn của int. Bài này là dịp để các bạn nhớ mãi chuyện tràn số, với kết quả chạy thật trên bộ test.
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 là một dòng 3 số. Mình đã kiểm tra: test 1–8 thoả $a, b, h \le 10$ (subtask 1), test 9–20 là subtask 2.
| Nhóm | Test | $a, b, h$ lớn nhất | Đáp án nhỏ nhất | Đáp án lớn nhất | Số test đáp án vượt quá int |
|---|---|---|---|---|---|
| Subtask 1 | 1–8 | 10 | 1.000 | 1.000.000 | 0 |
| Subtask 2 | 9–20 | 10.000 | 10.000.000 | 1.000.000.000.000.000 | 10 |
- Subtask 1 có đáp án lớn nhất $10 \cdot 10 \cdot 10 \cdot 1000 = 10^6$ lít,
intchứa thoải mái. - Subtask 2 có 10 test đáp án vượt $2^{31} - 1 = 2\,147\,483\,647$. Hai test còn lại (test 11 và 13) có đáp án vẫn vừa
int– trong đó có test đáp án sát nút giới hạnint(thấp hơn chưa tới 1%) – loại test "lọt khe" này cho thấy có đúng vài test lớn cũng chưa chắc code đã an toàn.
Kết quả chạy thật của các cách viết bên dưới theo từng subtask:
| Subtask | Test | Bẫy 1int | Bẫy 2long long V = biểu thức int | Lời giảilong long |
|---|---|---|---|---|
| Subtask 1 (40%) | 1–8 | 8/8 | 8/8 | 8/8 |
| Subtask 2 (60%) | 9–20 | 2/12 | 2/12 | 12/12 |
Ý tưởngThể tích hình hộp, đổi ra lít
Thể tích hồ (hình hộp chữ nhật) là $V = a \cdot b \cdot h$ (m³). Mỗi m³ là 1000 lít, nên số lít cần bơm là
$$\text{số lít} = a \cdot b \cdot h \cdot 1000.$$
Có thể hình dung bơm nước theo từng "lớp" dày 1 m: mỗi lớp là một tấm nước $a \times b \times 1$ chứa $a \cdot b$ m³ $= 1000ab$ lít, có $h$ lớp như vậy. Em nhập kích thước hồ rồi bấm Tiếp để xem nước dâng lên từng lớp – và để ý dòng cuối: nếu lưu số lít bằng int thì tới lúc nào bị tràn:
Bẫy 1Dùng int cho tất cả
Với subtask 1 thì code này đúng. Nhưng với $a = b = h = 10^4$, ngay $a \cdot b \cdot h = 10^{12}$ đã vượt int, nhân tiếp với 1000 càng sai. Máy không báo lỗi gì, chỉ lặng lẽ "quay vòng" – em bấm dữ liệu mẫu 10000 10000 10000 trong khung chạy tay để xem.
Kết quả chạy thật: bản C++ đúng 10/20 test, sai ở test 9, 10, 12, 14–20; test đúng chạy lâu nhất 0.004s. Với hồ lớn nhất $a = b = h = 10^4$, chương trình in -1530494976 (số âm!) trong khi đáp án là 1000000000000000. Code vẫn "may mắn" đúng test 11 và 13 vì đáp án hai test đó vừa lọt int – nhưng vẫn mất trọn 60% của subtask 2.
Bẫy 2Gán vào long long vẫn tràn
Sửa "nửa vời": chỉ đổi biến kết quả sang long long:
int a, b, h;
cin >> a >> b >> h;
long long V = a * b * h * 1000; // BẪY: vế phải vẫn tính bằng int, tràn TRƯỚC khi gán
cout << V;C++ tính vế phải trước: a * b * h * 1000 toàn là int nên được tính bằng int và tràn ngay trong lúc nhân, gán vào long long lúc đó đã muộn.
Kết quả chạy thật: bản C++ đúng 10/20 test, sai ở test 9, 10, 12, 14–20; test đúng chạy lâu nhất 0.003s – y hệt bẫy 1.
long long a, b, h (cách mình dùng), hoặc đưa một toán hạng long long lên đầu phép nhân: 1000LL * a * b * h hay 1LL * a * b * h * 1000. Chú ý viết a * b * h * 1000LL là chưa đủ: phép nhân tính từ trái sang phải, a * b * h vẫn tính bằng int và đã có thể tràn trước khi gặp 1000LL.Lời giảiDùng long long ngay từ đầu
long longchứa được tới khoảng $9{,}2 \cdot 10^{18}$, dư sức cho $10^{15}$.- Vì
a, b, hđều làlong longnêna * b * hvàV * 1000đều được tính bằnglong long. - Python không có giới hạn số nguyên nên viết thẳng công thức là được.
Kết quả chạy thật: Bản C++ đúng 20/20 test; test đúng chạy lâu nhất 0.003s. Bản Python đúng 20/20 test; test đúng chạy lâu nhất 0.019s. Full điểm.
Tổng kếtKết quả chạy thật trên bộ test
| Cách viết | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
Bẫy 1: toàn bộ là int | C++ | 10/20 | 0.004s | Sai test 9, 10, 12, 14–20 → mất subtask 2 |
Bẫy 2: long long V nhưng a, b, h là int | C++ | 10/20 | 0.003s | Sai test 9, 10, 12, 14–20 → mất subtask 2 |
Lời giải: long long | C++ | 20/20 | 0.003s | Full điểm |
| Python | 20/20 | 0.019s | Full điểm |
long long, và nhớ rằng kiểu của phép tính do các toán hạng quyết định, không phải do biến được gán.
Nhận xét
Đăng nhận xét