Editorial for Ốc Sên Và Ly Trà Sữa
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: Nghaiz
Lời giải: Ốc Sên Và Ly Trà Sữa
Chủ đề: vòng lặp while
Tóm tắt đề
Ly cao \(H\). Ban ngày ốc sên bò lên \(U\), ban đêm trượt xuống \(D\) (không thấp hơn \(0\)). Hỏi ngày thứ mấy ốc sên chạm độ cao \(H\), hoặc \(-1\) nếu không bao giờ.
Ý tưởng: mô phỏng đúng như đề bằng while
Các giá trị chỉ tới \(1000\) nên ta cứ làm đúng như câu chuyện, từng ngày một:
cao, ngay = 0, 0
while True:
ngay += 1
cao += U # ban ngày bò lên
if cao >= H: # kiểm tra NGAY sau khi bò lên
break
cao = max(0, cao - D) # ban đêm trượt xuống
Có hai chi tiết quan trọng:
- Kiểm tra ngay sau khi bò lên, trước khi trượt. Ốc sên chạm miệng ly là thoát luôn, đêm hôm đó không còn trượt nữa.
- Vòng lặp trên không bao giờ dừng nếu ốc sên không thể thoát. Ta phải phát hiện trường hợp này trước khi vào vòng lặp.
Khi nào ốc sên không bao giờ thoát?
Nếu \(U \geq H\) thì ngay ngày đầu đã thoát (dù \(D\) lớn đến đâu cũng vậy, vì chưa kịp đến đêm).
Nếu \(U < H\) và \(U \leq D\): sau ngày đầu ốc sên ở độ cao \(U < H\), đêm đó trượt về \(\max(0, U - D) = 0\). Ngày hôm sau lặp lại y hệt, nên mãi mãi không thoát → in \(-1\).
Ngược lại (\(D < U < H\)), mỗi ngày đêm ốc sên tiến thêm \(U - D \geq 1\) milimét nên chắc chắn sẽ thoát sau không quá \(1000\) ngày. Vòng lặp chạy rất nhanh.
Mở rộng: nếu \(H\) lên tới \(10^{18}\) thì sao?
Mô phỏng sẽ cần tới \(10^{18}\) vòng lặp, không kịp. Khi đó ta dùng công thức: sau \(k - 1\) ngày đêm ốc sên ở độ cao \((k - 1)(U - D)\), ngày thứ \(k\) lên tới \((k - 1)(U - D) + U\). Cần \(k\) nhỏ nhất để giá trị này \(\geq H\):
\(k = \left\lceil \dfrac{H - U}{U - D} \right\rceil + 1\)
Trong Python, phép chia làm tròn lên của hai số nguyên dương nên viết là (a + b - 1) // b. Không dùng math.ceil(a / b) vì phép / trả về số thực và bị sai khi số lớn.
Độ phức tạp
Mỗi tình huống tối đa khoảng \(1000\) vòng lặp.
Code mẫu
def so_ngay(h, u, d):
if u < h and u <= d: # bò không bù nổi trượt: mãi mãi không ra được
return -1
cao = 0
ngay = 0
while True:
ngay += 1
cao += u # ban ngày bò lên
if cao >= h: # chạm miệng ly là thoát ngay
return ngay
cao = max(0, cao - d) # ban đêm trượt xuống, không thấp hơn đáy
t = int(input())
for _ in range(t):
h, u, d = map(int, input().split())
print(so_ngay(h, u, d))
Comments