Tính số viên gạch

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

Đề bài

Mỗi hộ dân trong một khu làng sinh thái được hỗ trợ vật liệu để xây một ngôi nhà cấp 4. Sàn nhà là hình chữ nhật $x \times y$ mét, tường cao $z$ mét. Mái nhà dốc hai bên nên hai bức tường đầu hồi (cạnh $y$) có thêm phần tam giác cân phía trên, đỉnh cao $t$ mét tính từ sàn.

Như vậy ngôi nhà có 4 bức tường:

• 2 bức tường mặt trước/mặt sau: hình chữ nhật $x \times z$.
• 2 bức tường mặt bên: hình chữ nhật $y \times z$ ghép với tam giác đáy $y$, chiều cao $t - z$.

Theo định mức, mỗi mét vuông tường cần đúng $39$ viên gạch. Bỏ qua phần cửa ra vào và cửa sổ. Hãy tính số viên gạch cần cung cấp để xây đủ 4 bức tường.

Dữ liệu vào: Một dòng gồm bốn số nguyên dương $x, y, z, t$ cách nhau bởi dấu cách.

Kết quả: In ra số viên gạch cần dùng (dữ liệu bảo đảm kết quả là số nguyên).

Giới hạn:

• $1 \le x, y, z, t \le 10^4$, $z \le t$

Subtask:

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

1 1 1 1

Ví dụ 1 – output

156

Ví dụ 2 – input

4 3 3 5

Ví dụ 2 – output

1872

Giải thích: Ví dụ 2: diện tích tường là $2 \cdot (4 \cdot 3) + 2 \cdot (3 \cdot 3)$ $+ 2 \cdot \dfrac{3 \cdot (5-3)}{2}$ $= 24 + 18 + 6$ $= 48$ m², cần $48 \cdot 39 = 1872$ viên gạch.

Nguồn: phỏng theo bài "TÍNH GẠCH" – vinhdinhcoder.net.

Lời mở đầu

Một bài "tính diện tích" lớp 5, nhưng lại là bài rất hay để luyện kiểu dữ liệu. Công thức thì ai cũng ra, còn chương trình được 100 điểm hay chỉ 55, 70 điểm là nằm ở hai chi tiết nhỏ: tràn số int và phép chia nguyên. Mình sẽ dựng công thức, rồi cố tình viết lại đúng các lỗi mà học sinh hay mắc, chạy thật trên bộ test để các em thấy mỗi lỗi "đắt" cỡ nào.

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ưởngcông thứcBẫy 1tràn intBẫy 2chia nguyênLời giảilong 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 dòng 4 số. Mình đã kiểm tra: test 1–8 đúng là có $x, y, z, t \le 20$ (subtask 1), test 9–20 là subtask 2; mọi test đều có $z \le t$.

Nhóm	Test	Số lớn nhất trong $x, y, z, t$	Diện tích lớn nhất (m²)	Đáp án lớn nhất	Đáp án > $2^{31}-1$	$y(t-z)$ lẻ	$t = z$ (không có tam giác)
Subtask 1	1–8	20	1.600	62.400	0 test	2 test	2 test
Subtask 2	9–20	10.000	400.000.000	15.600.000.000	9 test	4 test	1 test

• Diện tích tường lớn nhất chỉ khoảng $4 \cdot 10^8$ m² – vẫn vừa kiểu int. Nhưng nhân thêm 39 thì đáp án lên tới 15.600.000.000, vượt xa $2^{31} - 1 = 2\,147\,483\,647$. Có 9 test như vậy (test 9–12, 14–16, 18–19).
• Có 6 test (test 7–8, 13, 16, 19–20) mà $y \cdot (t - z)$ là số lẻ, tức mỗi tam giác có diện tích "lẻ nửa mét vuông" (dạng $k{,}5$). Chú ý trong đó có cả test 7, 8 của subtask 1.

Kết quả chạy thật của các code bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Bẫy 1 int	Bẫy 2 chia nguyên	Bẫy 2 (Python) phép /	Lời giải đúng
Subtask 1 (40%)	$x, y, z, t \le 20$	1–8	8/8	6/8	0/8	8/8
Subtask 2 (60%)	$x, y, z, t \le 10^4$	9–20	3/12	8/12	0/12	12/12

Ý tưởngCộng diện tích từng mảnh tường

Cắt 4 bức tường thành các mảnh đơn giản:

• 2 mảnh chữ nhật trước/sau: $2 \cdot x z$.
• 2 mảnh chữ nhật ở tường bên: $2 \cdot y z$.
• 2 tam giác đầu hồi, mỗi tam giác đáy $y$, cao $t - z$: $2 \cdot \dfrac{y (t - z)}{2} = y (t - z)$.

Công thức

$S = 2xz + 2yz + y(t - z)$ (m²), số viên gạch $= 39 \cdot S$.

Điểm hay: hai tam giác ghép lại có diện tích $y(t-z)$ là số nguyên, nên ta không cần đụng tới số thực hay phép chia nào cả. Em nhập 4 số rồi bấm Tiếp để xem từng mảnh tường được cộng vào:

x = y = z = t =

Ví dụ nhanh:

Bẫy 1Tràn số int khi nhân 39

Bạn A thấy diện tích $S \le 4 \cdot 10^8$ vừa kiểu int nên khai báo hết bằng int, chỉ "cẩn thận" để kết quả là long long:

C++▶ Chạy tay từng dòng codeBẫy 1: S và 39 đều là int nên S * 39 tràn số trước khi gán vào long long.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. S là int, 39 là int → phép nhân S * 39 được tính trong kiểu int. Kết quả vượt $2^{31}-1$ thì bị tràn (máy chỉ giữ 32 bit cuối) trước khi gán vào ans. Khai báo ans là long long không cứu được gì.
2. Ví dụ $x = y = z = t = 10^4$: $S = 4 \cdot 10^8$, đáp án đúng $15\,600\,000\,000$ nhưng chương trình in ra một số âm.

Kết quả chạy thật: bản C++ này đúng 11/20 test, sai ở test 9–12, 14–16, 18–19; test đúng chạy lâu nhất 0.00s – đúng trọn subtask 1, nhưng sai đúng 9 test có đáp án vượt $2^{31}-1$. Cách sửa: khai báo long long cho các biến, hoặc viết 39LL * S.

Bẫy 2Chia đôi từng tam giác

Bạn B đã dùng long long, nhưng tính diện tích một tam giác theo đúng công thức "đáy nhân cao chia 2" rồi nhân 2:

C++▶ Chạy tay từng dòng codeBẫy 2: chia đôi từng tam giác bằng phép chia nguyên, mất 0,5 m² khi y·(t − z) lẻ.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. y * (t - z) / 2 là phép chia nguyên (hai số nguyên chia nhau): nếu $y(t - z)$ lẻ, phần $0{,}5$ bị bỏ đi. Hai tam giác mất tổng cộng $1$ m² → thiếu đúng $39$ viên gạch.
2. Ví dụ $x = 7, y = 5, z = 2, t = 9$: mỗi tam giác $5 \cdot 7 / 2 = 17{,}5$ m² nhưng code tính ra $17$, đáp án in ra $3198$ thay vì $3237$ (đúng chênh $39$).
3. Bản Python ở tab thứ hai mắc lỗi "ngược lại": phép / trong Python luôn cho số thực, nên in ra 1872.0 thay vì 1872 – trình chấm so từng ký tự nên sai cả, kể cả các test mà giá trị đúng!

Kết quả chạy thật: bản C++ này đúng 14/20 test, sai ở test 7–8, 13, 16, 19–20; test đúng chạy lâu nhất 0.00s – sai đúng các test có $y(t-z)$ lẻ, mất luôn subtask 1 vì test 7, 8. Bản Python dùng phép / đúng 0/20 test, sai ở test 1–20; test đúng chạy lâu nhất 0.00s.

Lời giảiGộp 2 tam giác + long long

Gộp hai tam giác thành $y(t-z)$ để không phải chia, và dùng long long cho mọi biến. Đáp án lớn nhất $\approx 1{,}56 \cdot 10^{10}$, kiểu long long (tới khoảng $9{,}2 \cdot 10^{18}$) chứa dư sức.

C++▶ Chạy tay từng dòng codeLời giải đúng: gộp 2 tam giác thành y·(t − z), mọi biến long long.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Đọc thẳng vào biến long long nên mọi phép nhân 2 * x * z, y * (t - z), S * 39 đều tính bằng 64 bit.
2. Trường hợp $t = z$ (nhà không có phần tam giác, như ví dụ 1) công thức vẫn đúng: $y(t - z) = 0$.
3. Python không bị tràn số, chỉ cần tránh phép /: dùng toàn phép nhân/cộng số nguyên là in ra số nguyên.

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. Full điểm.

Tổng kếtKết quả chạy thật trên bộ test

Code	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Bẫy 1: int S, S * 39	C++	11/20	0.00s	Sai test 9–12, 14–16, 18–19 (tràn số)
Bẫy 2: chia nguyên từng tam giác	C++	14/20	0.00s	Sai test 7–8, 13, 16, 19–20 (mất 0,5 m²)
Bẫy 2: phép / ra số thực	Python	0/20	0.00s	Sai test 1–20 (in ra dạng 156.0)
Lời giải đúng	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 code đều chạy tức thì, khác biệt chỉ nằm ở tính đúng. Hai bài học: (1) trước khi chọn kiểu dữ liệu, ước lượng giá trị lớn nhất của đáp án (ở đây $\approx 1{,}56 \cdot 10^{10} > 2^{31}$ → long long), và nhớ phép nhân hai số int vẫn cho ra int; (2) gặp "chia 2" thì xem có gộp lại để khử phép chia được không, nếu không thì phải cẩn thận chia nguyên/chia thực.

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 😇