Trồng cây tử đằng

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

Đề bài

Con đường từ trường về nhà bạn Huy dài $X$ ki-lô-mét. Huy muốn trồng một hàng cây hoa tử đằng dọc theo con đường này với quy tắc:

Mỗi hố trồng cây chiếm một đoạn dài $Y$ mét.
Giữa hai hố cây liên tiếp phải chừa một khoảng trống đúng $Z$ mét; giữa đầu đường và hố đầu tiên, cũng như giữa hố cuối cùng và cuối đường, cũng phải chừa ít nhất $Z$ mét.

Hỏi Huy trồng được nhiều nhất bao nhiêu cây? (Nếu con đường quá ngắn thì đáp án là $0$.)

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

Kết quả: In ra số cây nhiều nhất có thể trồng.

Giới hạn: $1 \le X, Y, Z \le 2 \cdot 10^9$.

Subtask:

Subtask 1 (40% số điểm): $X, Y, Z \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.

Ví dụ 1 – input

2 500 500

Ví dụ 1 – output

Ví dụ 2 – input

1 3 2

Ví dụ 2 – output

Giải thích: Ví dụ 1: đường dài $2$ km $= 2000$ m. Trồng 1 cây: $500$ m trống + $500$ m hố + $500$ m trống $= 1500$ m $\le 2000$ m. Trồng 2 cây cần $500 \cdot 2 + 500 \cdot 3 = 2500$ m $> 2000$ m nên chỉ trồng được $1$ cây.

Ví dụ 1: chừa 500 m, đào 1 hố 500 m, còn 1000 m. Muốn trồng cây thứ 2 phải chừa 500 m, đào hố 500 m rồi chừa thêm 500 m tới cuối đường – cần 1500 m > 1000 m.

Nguồn: phỏng theo bài "TRỒNG CÂY TỬ ĐẰNG" – vinhdinhcoder.net.

Lời mở đầu

Bài này gom đủ ba "cái hố" kinh điển của bài nhập môn: đổi đơn vị (ki-lô-mét và mét), dựng công thức từ mô tả bằng lời, và tràn số (đường dài tới $2 \cdot 10^9$ km $= 2 \cdot 10^{12}$ m). Mình sẽ đi từ cách mô phỏng "trồng từng cây một" (đủ cho subtask 1) tới công thức $O(1)$, và chỉ ra ba cách viết công thức trông rất đúng nhưng vẫn mất điểm vì tràn số – tất cả đều có kết quả chạy thật trên bộ test.

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ưởngkm → m, công thức Cách 1mô phỏng Bẫytràn số Cách 2công thức O(1)Tổ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 3 số. Mình đã kiểm tra: test 1–8 thoả $X, Y, Z \le 1000$ (subtask 1), test 9–20 là subtask 2.

Nhóm	Test	$L = 1000X$ lớn nhất (m)	Đáp án lớn nhất	Số test đáp án 0	Số test $1000X$ vượt `int`	Số test $Y + Z$ vượt `int`
Subtask 1	1–8	1.000.000	1.499	2	0	0
Subtask 2	9–20	2.000.000.000.000	999.999.999.999	1	11	1

Có 3 test đáp án bằng 0 (test 3, 4, 11), trong đó có test mà độ dài đường vừa đúng bằng $Z$ (chỉ đủ cho một khoảng trống, không có chỗ cho hố nào). Bộ test không có test nào $1000X < Z$, nhưng lời giải vẫn phải xử lý trường hợp đó (xem phần lời giải).
Ở subtask 2, đáp án có thể lên tới gần $10^{12}$ cây (2 test có đáp án vượt $10^9$) – đây là các test làm cách mô phỏng bị quá thời gian.
Chỉ 1 test của subtask 2 có $1000X$ còn vừa int; và có test $Y + Z$ cũng vượt int.

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

Subtask	Test	Cách 1 mô phỏng	Bẫy công thức + `int`	Bẫy sửa nửa vời	Lời giải công thức + `long long`
Subtask 1 (40%)	1–8	8/8	8/8	8/8	8/8
Subtask 2 (60%)	9–20	10/12	1/12	11/12	12/12

Ý tưởngĐổi ra mét và dựng công thức

Bước 1 – đổi đơn vị: $X$ tính bằng ki-lô-mét, còn $Y, Z$ tính bằng mét. Độ dài con đường là $L = 1000 \cdot X$ mét. Quên bước này thì sai ngay ví dụ 1.

Bước 2 – dựng công thức: trồng $k$ cây thì trên đường có $k$ hố (mỗi hố $Y$ m) và $k + 1$ khoảng trống (một khoảng ở đầu đường, $k - 1$ khoảng giữa các hố, một khoảng ở cuối đường), mỗi khoảng ít nhất $Z$ m. Vậy trồng được $k$ cây khi và chỉ khi

$$k \cdot Y + (k + 1) \cdot Z \le L \iff k \cdot (Y + Z) \le L - Z \iff k \le \frac{L - Z}{Y + Z}.$$

Số cây nhiều nhất là $k = \left\lfloor \dfrac{L - Z}{Y + Z} \right\rfloor$ (phép chia lấy phần nguyên). Nếu $L < Z$ (đường còn không đủ cho một khoảng trống) thì đáp án là $0$.

Thử với ví dụ 2: $L = 1000$, $k = \lfloor (1000 - 2) / (3 + 2) \rfloor$ $= \lfloor 998 / 5 \rfloor$ $= 199$. Đúng bằng đáp án.

Em nhập $X, Y, Z$ rồi bấm Tiếp để xem Huy trồng từng cây (mỗi lần trồng cần thêm $Y + Z$ mét: một hố và một khoảng trống phía sau nó):

X = Y = Z =

Ví dụ nhanh:

Cách 1Mô phỏng trồng từng cây

Cách tự nhiên nhất: biến used là phần đường đã dùng, ban đầu bằng $Z$ (khoảng trống đầu đường). Mỗi lần còn đủ chỗ cho một hố và một khoảng trống phía sau ($Y + Z$ mét) thì trồng thêm một cây.

C++▶ Chạy tay từng dòng codeCách 1: mô phỏng trồng từng cây – mỗi cây dùng thêm Y + Z mét.

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

Dữ liệu mẫu:

Khi phải lặp nhiều vòng giống nhau (như test đề 2: 199 cây), khung chạy tay tua nhanh các vòng ở giữa.

Điều kiện used + Y + Z <= L đảm bảo sau hố mới vẫn còn khoảng trống $Z$ tới cuối đường (hoặc tới hố sau).
Mình đã dùng long long ở đây để cách này chỉ "thua" vì chậm chứ không vì tràn số.
Số vòng lặp đúng bằng đáp án $k$. Subtask 1 có $L \le 10^6$ nên $k < 10^6$ – chạy tức thì. Subtask 2 có đáp án gần $10^{12}$, máy chỉ chạy được khoảng $10^8$–$10^9$ phép tính mỗi giây.

Không gian$O(1)$

Thời gian$O(k)$ – $k$ là đáp án

Kết quả chạy thật: bản C++ đúng 18/20 test, quá thời gian ở test 9, 14; test đúng chạy lâu nhất 0.719s. Bản Python đúng 17/20 test, quá thời gian ở test 9, 13, 14; test đúng chạy lâu nhất 0.148s (Python chậm hơn nên quá thời gian cả test có đáp án cỡ $10^9$). Subtask 1 đúng hết, subtask 2 mất vì quá thời gian.

BẫyCông thức đúng nhưng tràn số

Có công thức rồi, nhiều bạn viết ngay với int – vì $X, Y, Z \le 2 \cdot 10^9$ vẫn vừa int (tối đa $2\,147\,483\,647$):

C++▶ Chạy tay từng dòng codeBẫy: công thức đúng nhưng X * 1000 tràn int.

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

Dữ liệu mẫu:

Nhưng $L = 1000X$ lên tới $2 \cdot 10^{12}$ – vượt xa int. Em bấm dữ liệu mẫu 3000000 1 1 trong khung chạy tay: $L = 3 \cdot 10^9$ bị tràn thành số âm, nên L < Z đúng và chương trình in 0 – trong khi đáp án thật là $1\,499\,999\,999$ (con số này vẫn vừa int, chỉ có $L$ bị tràn!).

Kết quả chạy thật: bản C++ đúng 9/20 test, sai ở test 9, 10, 12–20; test đúng chạy lâu nhất 0.004s → mất subtask 2.

Hai cách "sửa" sau đây vẫn chưa đủ:

Sửa lần 1 – đổi L và mẫu số sang long long, còn X, Y, Z vẫn là int:

int X, Y, Z;
cin >> X >> Y >> Z;
long long L = X * 1000;         // BẪY: X * 1000 tính bằng int, tràn TRƯỚC khi gán!
long long d = Y + Z;            // tương tự: Y + Z tràn trước khi gán

Kết quả chạy thật: bản C++ đúng 9/20 test, sai ở test 9, 10, 12–20; test đúng chạy lâu nhất 0.003s. Lý do: X * 1000 có cả hai toán hạng là int nên được tính bằng int và tràn trước khi gán vào long long.

Sửa lần 2 – nhân với 1LL trước để L được tính bằng long long, nhưng quên mẫu số:

long long L = 1LL * X * 1000;   // đã sửa: nhân với 1LL trước nên tính bằng long long
if(L < Z) cout << 0;
else cout << (L - Z) / (Y + Z); // nhưng Y + Z vẫn tính bằng int -> vẫn có thể tràn

Kết quả chạy thật: bản C++ đúng 19/20 test, sai ở test 10; test đúng chạy lâu nhất 0.004s. Đã sửa đúng $L$ nhưng Y + Z (tới $4 \cdot 10^9$) vẫn tính bằng int; ở test 10 nó tràn thành số âm và chương trình in ra số cây âm. Chỉ sai đúng 1 test nhưng vẫn mất trọn 60% của subtask 2!

Cách 2Công thức $O(1)$ với `long long`

Khai báo $X, Y, Z$ là long long ngay từ lúc đọc thì mọi phép tính (X * 1000, L - Z, Y + Z, phép chia) đều tính bằng long long – không còn gì để tràn:

C++▶ Chạy tay từng dòng codeCách 2: công thức k = (L − Z) / (Y + Z), tính hoàn toàn bằng long long.

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

Dữ liệu mẫu:

Vì sao cần if(L < Z)? Khi $L < Z$ thì $L - Z$ âm. Phép chia nguyên trong C++ làm tròn về 0: ví dụ $(-5) / 3 = -1$ – sẽ in ra số cây âm. Nên phải xử lý riêng, in 0. (Khi $L - Z < Y + Z$ thì phép chia đã ra 0 đúng như mong muốn.)
Python dùng // là phép chia làm tròn xuống, $(-5) // 3 = -2$, nên mình bọc thêm max(0, ...) cho trường hợp đường quá ngắn. Số nguyên Python không bị trà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.004s. Bản Python đúng 20/20 test; test đúng chạy lâu nhất 0.022s. Full điểm.

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

Cách	Ngôn ngữ	Đúng	Test đúng lâu nhất	Ghi chú
1. Mô phỏng trồng từng cây	C++	18/20	0.719s	quá thời gian test 9, 14 → mất subtask 2
	Python	17/20	0.148s	quá thời gian test 9, 13, 14 → mất subtask 2
Bẫy: công thức, toàn `int`	C++	9/20	0.004s	sai test 9, 10, 12–20 → mất subtask 2
Bẫy: `long long L = X * 1000` (X là `int`)	C++	9/20	0.003s	sai test 9, 10, 12–20 → mất subtask 2
Bẫy: sửa `L` nhưng quên `Y + Z`	C++	19/20	0.004s	sai test 10 → mất subtask 2
2. Công thức, `long long`	C++	20/20	0.004s	Full điểm
	Python	20/20	0.022s	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 (test quá thời gian bị dừng ở khoảng 4 giây). Mô phỏng từng cây ăn trọn subtask 1 nhưng quá thời gian ở các test có đáp án khổng lồ; công thức $k = \lfloor (1000X - Z) / (Y + Z) \rfloor$ chạy tức thì nhưng phải tính hoàn toàn bằng long long: tràn ở $1000X$ mất 11 test, chỉ quên $Y + Z$ cũng mất 1 test – và mất 1 test cũng là mất cả subtask. Thói quen: ước lượng giá trị lớn nhất của từng biểu thức trung gian, không chỉ của đáp án.

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 😇

Lập Trình Thuật Toán