Hướng dẫn giải của [Quảng Trị - TS10 - 2025] Bài 1: Bơm nước
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Tóm tắt đề bài
Cho 3 số nguyên dương ~X, Y, K~ (~1 \le X \le Y \le 10^{12}, 1 \le K \le 10^5~). Hỏi ta cần cộng giá trị ~K~ vào số ~X~ bao nhiêu lần để giá trị ~X~ đạt được sẽ ~\ge Y~.
Subtask 1: ~X, Y \le 10^8, Y \le 10^5~
Tại subtask này, ta chỉ cần mô phỏng lại quá trình tăng của ~X~ đến khi đạt tối thiểu là ~Y~.
ĐPT: ~O~(~\frac{Y - X}{K}~)
Subtask 2: Không có giới hạn gì thêm.
Gọi diff là hiệu giữa hai giá trị ~X~ và ~Y~.
- Nếu
diffchia hết cho ~K~, kết quả sẽ là ~\frac{diff}{K}~. - Trường hợp còn lại, kết quả sẽ là ~\frac{diff}{K} + 1~
Bạn đọc tự chứng minh tính chất trên.
ĐPT: ~O~(~1~)
Bình luận