An toàn hay nguy hiểm

Nguồn: CLUE OJ Độ khó: Dễ Rẽ nhánh Đổi đơn vị

Đề bài

Nhà Tèo vừa được đào một hồ cá có mặt hồ là hình chữ nhật kích thước $a \times b$ (mét), thành hồ thẳng đứng và đủ sâu. Bố Tèo sợ Tèo còn nhỏ lỡ rơi xuống hồ nên chỉ muốn bơm vào hồ một lượng nước vừa đủ: nếu Tèo có rơi xuống thì mực nước không được cao quá cổ Tèo. Bố đã đo được chiều cao từ mặt đất tới cổ Tèo là $k$ (cm).

Khổ nỗi máy bơm không chọn được lượng nước, chỉ bật rồi tắt sau một khoảng thời gian. Máy bơm có công suất $3$ $m^3$/giờ và bố đã bơm trong $t$ (giờ).

Hãy cho biết với lượng nước đã bơm thì Tèo có an toàn hay không. Tèo an toàn nếu mực nước trong hồ không vượt quá $k$ cm.

Dữ liệu vào:

Một dòng gồm 4 số nguyên dương $a, b, k, t$.

Kết quả:

In ra YES nếu Tèo an toàn, ngược lại in ra WARNING.

Giới hạn:

• $1 \le a, b, k, t < 10^4$

Subtask:

• Subtask 1 (40% số điểm): $a, b, k, t < 104$.
• 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

7 6 82 9

Ví dụ 1 – output

YES

Ví dụ 2 – input

7 7 93 38

Ví dụ 2 – output

WARNING

• Ví dụ 1: bơm được $3 \cdot 9 = 27$ $m^3$ nước, mặt hồ rộng $7 \cdot 6 = 42$ $m^2$ nên mực nước cao $27 / 42 \approx 0{,}643$ m $\approx 64{,}3$ cm $\le 82$ cm → an toàn.
• Ví dụ 2: $3 \cdot 38 = 114$ $m^3$ nước trên mặt hồ $49$ $m^2$, mực nước $\approx 232{,}7$ cm $> 93$ cm → nguy hiểm.

Nguồn: phỏng theo bài "An toàn hay nguy hiểm" – vinhdinhcoder.net (chủ đề Rẽ nhánh).

Lời mở đầu

Bài toán "vật lý" nhỏ: tính mực nước rồi so với chiều cao cổ Tèo. Khó ở chỗ đơn vị (mét và cm) và sai số số thực: khi mực nước vừa đúng bằng cổ Tèo thì phép chia số thực có thể lệch một chút xíu, biến "an toàn" thành "nguy hiểm". Ghi chú: đề gốc ghi giới hạn "< 104", mình hiểu là $< 10^4$; subtask 1 giữ đúng giới hạn < 104.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

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ưởngđổi đơn vị, nhân chéoLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–8 thuộc subtask 1 (mọi số $< 104$), test 9–20 có số tới $9999$.

Test	Nội dung kiểm tra
1–8	Ví dụ đề, mực nước bằng đúng cổ Tèo, thấp hơn / cao hơn 1 cm
9–11	Mực nước bằng đúng $k$ nhưng phép chia số thực bị lệch lên trên $k$ (bẫy sai số)
12–15	$k \cdot a \cdot b$ tới gần $10^{12}$ – tràn int
16–20	Các trường hợp nguy hiểm với hồ nhỏ, bơm lâu

Ý tưởngĐổi về cm rồi nhân chéo

Bơm $t$ giờ, mỗi giờ $3\ m^3$ → thể tích nước $V = 3t\ (m^3)$. Mặt hồ rộng $S = a \cdot b\ (m^2)$, thành hồ thẳng đứng nên mực nước là

$$h = \frac{V}{S} = \frac{3t}{ab}\ (m) = \frac{300t}{ab}\ (cm).$$

Tèo an toàn khi $h \le k$, tức là $\dfrac{300t}{ab} \le k$. Vì $ab > 0$, nhân hai vế với $ab$:

Kết luận

An toàn ⇔ $300 \cdot t \le k \cdot a \cdot b$ – so sánh hai số nguyên, không có phép chia, không có sai số. $k \cdot a \cdot b$ tới gần $10^{12}$ nên dùng long long.

Em nhập kích thước hồ, chiều cao cổ Tèo, số giờ bơm rồi bấm Tiếp:

a (m) = b (m) = k (cm) = t (giờ) =

Ví dụ nhanh:

Lời giảiSo sánh hai số nguyên

Đọc 4 số vào biến long long và so sánh $300t$ với $kab$.

C++▶ Chạy tay từng dòng codeSo sánh 300·t với k·a·b – không chia, không sai số.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Dấu <=: mực nước bằng đúng cổ Tèo vẫn là an toàn ("không vượt quá").
2. Kỹ thuật nhân chéo (chuyển phép chia thành phép nhân) giúp so sánh phân số bằng số nguyên – rất hay dùng khi muốn tránh sai số.

Không gian$O(1)$

Thời gian$O(1)$

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

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Tính mực nước bằng số thực h = 3*t/(a*b)*100 rồi so với $k$	17/20	sai test 9, 10, 11
Dùng dấu < thay vì <=	16/20	sai test 3, 9, 10, 11
Dùng int (tích $k \cdot a \cdot b$ tràn)	16/20	sai test 12, 13, 14, 15
Quên đổi mét sang cm	12/20	sai test 2, 4, 5, 6, 8, 18, 19, 20

Sai số số thực ở đâu ra?

Ví dụ test 9: $a = 5, b = 75, k = 112, t = 140$. Đúng ra $h = 300 \cdot 140 / 375 = 112$ cm, bằng đúng $k$. Nhưng máy tính tính 3*140/375 được $1{,}12$ (lưu xấp xỉ), nhân 100 ra 112.00000000000001 > 112 → báo nhầm WARNING.

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ú
Lời giải chuẩn	C++	20/20	0.003s	Full điểm
	Python	20/20	0.022s	Full điểm
Số thực	C++	17/20	–	Mất 3 test
Dấu <	C++	16/20	–	Mất 4 test
Dùng int	C++	16/20	–	Mất 4 test
Quên đổi đơn vị	C++	12/20	–	Mất 8 test

Ghi chú của mình: gặp phép so sánh có phép chia, hãy thử nhân chéo để đưa về số nguyên. Vừa nhanh, vừa không bao giờ bị sai số.

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 😇