Diện tích hình chữ nhật
Đề bài
Cho hình chữ nhật có hai cạnh dài $a$ và $b$. Hãy tính diện tích hình chữ nhật.
Dữ liệu vào: Một dòng gồm hai số nguyên dương $a$ và $b$ cách nhau bởi dấu cách.
Kết quả: In ra diện tích hình chữ nhật.
Giới hạn: $1 \le a, b \le 10^6$.
Subtask:
- Subtask 1 (40% số điểm): $a, b \le 1000$.
- 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.
5 8401 11Giải thích: Ví dụ 1: hình chữ nhật $5 \times 8$ có diện tích $5 \cdot 8 = 40$. Ví dụ 2: hình vuông cạnh 1 có diện tích $1$.
Nguồn: phỏng theo bài "DIỆN TÍCH HCN" – vinhdinhcoder.net.
Lời mở đầu
Diện tích hình chữ nhật = dài × rộng, học sinh tiểu học cũng biết 😄. Nhưng với lập trình C++, bài này lại giấu một cái bẫy mà rất nhiều bạn đã "biết dùng long long" vẫn bị dính: khai báo kết quả là long long nhưng phép nhân vẫn bị tràn. Mình sẽ chấm thật 3 cách viết để các bạn thấy rõ.
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 2 số. Mình đã kiểm tra: test 1–8 thoả điều kiện subtask 1 ($a, b \le 1000$), test 9–20 là subtask 2.
| Nhóm | Test | Cạnh nhỏ nhất | Cạnh lớn nhất | Diện tích lớn nhất | Số test hình vuông | Số test diện tích vượt INT_MAX |
|---|---|---|---|---|---|---|
| Subtask 1 | 1–8 | 1 | 1.000 | 1.000.000 | 3 | 0 |
| Subtask 2 | 9–20 | 1 | 1.000.000 | 1.000.000.000.000 | 3 | 10 |
- Subtask 1: diện tích tối đa $1000 \cdot 1000 = 10^6$, kiểu
intthoải mái. - Subtask 2: diện tích lên tới $10^6 \cdot 10^6 = 10^{12}$; có 10/12 test diện tích vượt
INT_MAX$= 2\,147\,483\,647$.
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 S | Cách 2long long S = a * b | Cách 31LL * a * b |
|---|---|---|---|---|---|
| Subtask 1 (40%) | $a, b \le 1000$ | 1–8 | 8/8 | 8/8 | 8/8 |
| Subtask 2 (60%) | đầy đủ: $a, b \le 10^6$ | 9–20 | 2/12 | 2/12 | 12/12 |
Ý tưởngDiện tích = số ô vuông đơn vị
Hình chữ nhật cạnh $a$ (ngang) và $b$ (dọc) được lát bởi $b$ hàng, mỗi hàng $a$ ô vuông cạnh 1, nên diện tích là $S = a \cdot b$. Phần khó là $S$ có thể rất lớn: kiểu int chỉ chứa tới $\approx 2{,}1 \cdot 10^9$, tức là chỉ "đủ chỗ" cho những hình chữ nhật mà $a \cdot b \le 2\,147\,483\,647$.
Em nhập $a$, $b$ rồi bấm Tiếp: với hình nhỏ, widget đếm từng hàng ô vuông; bước cuối đặt hình chữ nhật lên bản đồ (hai trục chia theo thang log) – vùng đỏ là những cặp $(a, b)$ làm int bị tràn:
Để ý đường biên đỏ: hình vuông lớn nhất mà int còn chứa được diện tích là cạnh $46\,340$ (vì $46\,340^2 = 2\,147\,395\,600$), còn cạnh $46\,341$ là đã tràn.
Cách 1Dùng int – đúng subtask 1
Khi $a \cdot b$ vượt INT_MAX, phép nhân int * int bị tràn: máy chỉ giữ 32 bit thấp của kết quả (bit cao nhất là bit dấu), nên có thể in ra số âm hoặc số "nhỏ xíu". Ví dụ 46341 46342 (diện tích $2\,147\,534\,622$) in ra $-2\,147\,432\,674$, còn 131072 32768 (diện tích đúng bằng $2^{32}$) in ra $0$.
Kết quả chạy thật: Bản C++ đúng 10/20 test, sai test 9–10, 12–14, 16–20, chạy lâu nhất 0.003s. Đúng toàn bộ subtask 1 và 2 test của subtask 2 có diện tích nhỏ (test 11 và 15) → mất 60% điểm.
Cách 2long long S = a * b – vẫn sai!
Biết là kết quả lớn, nhiều bạn sửa ngay biến S thành long long và yên tâm nộp bài:
a * b trước: cả a và b đều là int nên đây là phép nhân int * int, kết quả là int – tràn ngay ở bước này. Sau đó giá trị (đã sai) mới được đổi sang long long để gán vào S. Biến S rộng 64 bit cũng không cứu được.Kết quả chạy thật: Bản C++ đúng 10/20 test, sai test 9–10, 12–14, 16–20, chạy lâu nhất 0.003s – giống hệt cách 1, sai đúng các test như cách 1.
Cách 31LL * a * b – full điểm
Ta phải làm cho phép nhân được tính bằng long long ngay từ đầu. Mẹo quen thuộc: nhân thêm 1LL (số 1 kiểu long long) ở đầu biểu thức. Phép nhân tính từ trái sang phải: 1LL * a là long long, rồi (1LL * a) * b cũng là long long.
- Phải đặt
1LLở đầu: viếta * b * 1LLthìa * bvẫn tính bằnginttrước → vẫn tràn. - Các cách tương đương:
(long long)a * b, hoặc đơn giản nhất là khai báo luônlong long a, b;.
long long S = (long long)a * b; // ép kiểu a trước khi nhân: cũng đúng
long long S = a * b * 1LL; // SAI: a * b đã tràn trước khi gặp 1LLKế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.020s. 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 S = a * b | C++ | 10/20 | 0.003s | Tràn số ở 10 test có diện tích vượt INT_MAX |
2. long long S = a * b | C++ | 10/20 | 0.003s | Sai y hệt cách 1: a * b vẫn tính bằng int |
3. long long S = 1LL * a * b | C++ | 20/20 | 0.003s | Full điểm |
| Python | 20/20 | 0.020s | Full điểm |
long long S = a * b; với a, b kiểu int không hề an toàn. Hãy nhớ quy tắc "kiểu của phép tính do toán hạng quyết định" – muốn nhân không tràn thì một trong hai thừa số phải là long long trước khi nhân.
Nhận xét
Đăng nhận xét