Editorial for Ốc Sên Và Ly Trà Sữa


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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:

  1. 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.
  2. 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

There are no comments at the moment.