Diện tích tam giác vuông
Đề bài
Cho tam giác vuông có hai cạnh góc vuông dài $a$ và $b$. Hãy tính diện tích của tam giác.
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 tam giác vuông, làm tròn đến 2 chữ số thập phân.
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.
Bài được chấm với sai số tuyệt đối không quá $10^{-2}$.
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 615.001 10.50Giải thích: Ví dụ 1: $S = \dfrac{5 \cdot 6}{2} = 15$, in ra 15.00.
Ví dụ 2: $S = \dfrac{1 \cdot 1}{2} = 0{,}5$, in ra 0.50.
Nguồn: phỏng theo bài "DIỆN TÍCH TAM GIÁC VUÔNG" – vinhdinhcoder.net.
Lời mở đầu
Diện tích tam giác vuông bằng nửa tích hai cạnh góc vuông – kiến thức lớp 5. Nhưng khi "dịch" sang C++ thì phép chia đôi và phép nhân lại giấu 2 cái bẫy rất kinh điển: chia nguyên làm mất 0,5 và tích hai số int bị tràn. Bài này chấm với sai số tuyệt đối $10^{-2}$, tức là kết quả chỉ được lệch đáp án tối đa $0{,}01$ – thiếu $0{,}5$ hay lệch vài nghìn đều bị bắt. Mình sẽ chạy thật hết để các bạn thấy rõ mỗi bẫy mất bao nhiêu điểm.
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ả subtask 1 ($a, b \le 1000$), test 9–20 là subtask 2.
| Nhóm | Test | $a, b$ lớn nhất | $a \cdot b$ lớn nhất | Số test $a \cdot b$ lẻ (đáp án .50) | Số test $a \cdot b > 2^{31}-1$ |
|---|---|---|---|---|---|
| Subtask 1 | 1–8 | 1.000 | 1.000.000 | 5 | 0 |
| Subtask 2 | 9–20 | 1.000.000 | 1.000.000.000.000 | 4 | 10 |
- Có 9 test mà $a \cdot b$ lẻ (test 2, 3, 5, 6, 8, 10, 12, 14, 17), khi đó diện tích có đuôi
.50– các test này "bắt" lỗi chia nguyên. - Có 10 test mà $a \cdot b$ vượt $2^{31} - 1 = 2\,147\,483\,647$ (test 9, 10, 12, 13, 15–20), lớn nhất $10^{12}$ – các test này "bắt" lỗi tràn
int. Đáng chú ý test 13 là $65536 \cdot 65537$, chỉ vừa vượt $2^{32}$ một chút.
Kết quả chạy thật của các code trong bài theo từng subtask (chấm sai số tuyệt đối $10^{-2}$ như đề; dòng cuối: nếu so khớp từng ký tự):
| Subtask | Test | Bẫy 1/ 2 nguyên | Bẫy 2int a, b | Bẫy 3cout trơn | Cách 1double | Cách 2 số nguyên |
|---|---|---|---|---|---|---|
| Subtask 1 (40%) $a, b \le 1000$ | 1–8 | 3/8 | 8/8 | 8/8 | 8/8 | 8/8 |
| Subtask 2 (60%) đầy đủ: $a, b \le 10^6$ | 9–20 | 8/12 | 2/12 | 2/12 | 12/12 | 12/12 |
| Điểm | 0% | 40% | 40% | 100% | 100% | |
| Nếu so khớp từng ký tự | 11/20 | 10/20 | 0/20 | 20/20 | 20/20 |
Ý tưởngNửa hình chữ nhật
Hai tam giác vuông bằng nhau ghép lại thành hình chữ nhật $a \times b$, nên $S = \dfrac{a \cdot b}{2}$. Vì $a \cdot b$ là số nguyên nên diện tích chỉ có hai khả năng:
- $a \cdot b$ chẵn → $S$ là số nguyên, in ra đuôi
.00; - $a \cdot b$ lẻ → $S$ có phần lẻ đúng bằng $0{,}5$, in ra đuôi
.50.
Em nhập $a$, $b$ rồi bấm Tiếp để xem:
Bẫy 1Chia nguyên làm mất 0,5
Viết double S = a * b / 2; và nghĩ rằng "S là double thì sẽ ra số thực". Sai! a * b và 2 đều là số nguyên nên a * b / 2 là phép chia nguyên, tính xong (mất phần lẻ) rồi mới gán vào S: $1 \cdot 1 / 2 = 0$, $3 \cdot 7 / 2 = 10$.
Kết quả chạy thật: code đúng đúng 11/20 test, sai test 2, 3, 5, 6, 8, 10, 12, 14, 17, chạy lâu nhất 0.003s – sai đúng 9 test có tích lẻ, kể cả 5/8 test của subtask 1 → 0 điểm. Thiếu $0{,}5$ lớn hơn nhiều so với sai số cho phép $0{,}01$ nên test nào có đuôi .50 cũng bị bắt, dù đáp án lớn hay nhỏ.
Chuyện bên lề: lúc đầu bài này chấm với sai số tương đối $10^{-2}$ (lệch tối đa 1% giá trị đáp án). Khi đó thiếu $0{,}5$ ở đáp án $499{,}5$ chỉ là lệch $0{,}1\%$, nên code chia nguyên này lọt tới 17/20 test – sai mà vẫn được gần hết điểm từng test. Vì vậy đề đã đổi sang sai số tuyệt đối.
Cách sửa: chia cho số thực 2.0 (hoặc nhân 1.0 * vào trước). Bản Python cũng có lỗi y hệt nếu dùng //: đúng đúng 11/20 test, sai test 2, 3, 5, 6, 8, 10, 12, 14, 17, chạy lâu nhất 0.022s.
Bẫy 2Tích a * b tràn int
Lần này đã chia 2.0 rồi, nhưng khai báo int a, b;. Phép nhân a * b vẫn được tính bằng int trước khi chia – mà $10^6 \cdot 10^6 = 10^{12}$ vượt xa giới hạn $2\,147\,483\,647$.
Kết quả chạy thật: code đúng đúng 10/20 test, sai test 9, 10, 12, 13, 15–20, chạy lâu nhất 0.002s – đúng y 10 test có tích vượt int. Subtask 1 không sao (tích tối đa $10^6$) nhưng mất trọn 60% của subtask 2. Ví dụ test 13 ($65536 \cdot 65537$ $= 4\,295\,032\,832$) bị tràn thành $65536$, code in ra 32768.00.
Cách sửa: khai báo long long a, b;, hoặc ép một thừa số lên: (long long)a * b hay 1.0 * a * b. Nếu dính cả hai bẫy (int và cout << a * b / 2) thì chỉ còn đúng đúng 4/20 test, sai test 2, 3, 5, 6, 8–10, 12–20, chạy lâu nhất 0.003s.
Bẫy 3cout << S không định dạng
Tính đúng rồi nhưng in bằng cout << S; thì ví dụ 1 ra 15 chứ không phải 15.00, và số lớn ra dạng 5e+11.
Kết quả chạy thật: code đúng đúng 10/20 test, sai test 10, 12–20, chạy lâu nhất 0.002s. Subtask 1 vẫn đúng hết vì máy chấm so giá trị: 15 bằng $15{,}00$, và với số nhỏ thì 6 chữ số có nghĩa là đủ. Nhưng ở subtask 2, 4.99999e+11 lệch đáp án $499\,999\,000\,000{,}50$ tới khoảng một triệu – sai số tuyệt đối $0{,}01$ không tha → mất 60%. Còn nếu so khớp từng ký tự thì code này đúng 0/20. Luôn in đúng định dạng đề yêu cầu.
Cách 1long long + chia 2.0 + setprecision(2)
long long a, b: tícha * btối đa $10^{12}$, nằm gọn tronglong long(tối đa $\approx 9{,}2 \cdot 10^{18}$)./ 2.0: chia số thực, giữ được phần $0{,}5$.doublebiểu diễn chính xác mọi số dạng $k/2$ với $k \le 10^{12}$, nên kết quả đúng tuyệt đối.fixed << setprecision(2): in đúng 2 chữ số sau dấu chấm (hoặcprintf("%.2f", S)). Python:f"{S:.2f}".
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.014s. So khớp từng ký tự cũng đúng 20/20.
Dùng float S thay double thì sao? float chỉ có khoảng 7 chữ số chính xác: test 9 in ra 499999997952.00 thay vì 500000000000.00, lệch hơn 2000 đơn vị. Kết quả: đúng đúng 11/20 test, sai test 9, 10, 12, 15–20, chạy lâu nhất 0.003s – mất trọn subtask 2. Cứ dùng double.
Cách 2Không cần số thực
Vì đáp án chỉ có đuôi .00 hoặc .50, ta có thể làm hoàn toàn bằng số nguyên: phần nguyên là p / 2 (chia nguyên), đuôi là .00 nếu p chẵn, .50 nếu p lẻ. Không có sai số làm tròn nào, dù số có lớn đến đâu.
Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.002s. Đây là một mẹo hay dùng: khi kết quả số thực có dạng đặc biệt (chia 2, chia 4, chia 100...), tách phần nguyên và phần lẻ ra in riêng sẽ tránh được hoàn toàn chuyện sai số.
Tổng kếtKết quả chạy thật trên bộ test
| Code | Ngôn ngữ | Đúng (sai số tuyệt đối $10^{-2}$) | Điểm | So khớp từng ký tự | Ghi chú |
|---|---|---|---|---|---|
Bẫy 1: a * b / 2 (chia nguyên) | C++ | 11/20 | 0% | 11/20 | sai test 2, 3, 5, 6, 8, 10, 12, 14, 17 – đúng y các test có tích lẻ, mất .5 |
Bẫy 2: int a, b | C++ | 10/20 | 40% | 10/20 | sai test 9, 10, 12, 13, 15–20 – a * b tràn |
int + cout << a * b / 2 | C++ | 4/20 | 0% | 0/20 | sai test 2, 3, 5, 6, 8–10, 12–20 – dính cả hai bẫy trên |
Bẫy 3: cout << S | C++ | 10/20 | 40% | 0/20 | sai test 10, 12–20 – số lớn in dạng 4.99999e+11, lệch cả triệu |
float S | C++ | 11/20 | 40% | 11/20 | sai test 9, 10, 12, 15–20 – vd in 499999997952.00 thay vì 500000000000.00 |
Cách 1: long long, / 2.0, setprecision(2) | C++ | 20/20 | 100% | 20/20 | Full điểm, chạy lâu nhất 0.003s |
| Cách 2: chỉ dùng số nguyên | C++ | 20/20 | 100% | 20/20 | Full điểm, chạy lâu nhất 0.002s |
Code chuẩn: f"{a * b / 2:.2f}" | Python | 20/20 | 100% | 20/20 | Full điểm, chạy lâu nhất 0.014s |
print(a * b // 2) | Python | 11/20 | 0% | 0/20 | sai test 2, 3, 5, 6, 8, 10, 12, 14, 17 – // là chia nguyên |
print(a * b / 2) | Python | 20/20 | 100% | 0/20 | vẫn "lọt": giá trị đúng nhưng in 15.0, sai định dạng |
print(a * b / 2) (in 15.0) là "lọt" vì giá trị in ra vẫn đúng tuyệt đối – nhưng sai định dạng đề yêu cầu. Thời gian đều cỡ vài phần nghìn giây. Hai bài học lớn: kiểu của phép tính do toán hạng quyết định (a * b / 2 là chia nguyên, int * int tràn trước khi gán), và in đúng định dạng đề yêu cầu.
Nhận xét
Đăng nhận xét