Cầu thang và những chiếc hộp
Đề bài
Mô tả
Một cầu thang gồm bậc, bậc thứ có độ cao , với .
Lần lượt có chiếc hộp hình chữ nhật được thả từ trên cao xuống cầu thang. Hộp thứ có chiều rộng và chiều cao , được thả thẳng đứng phía trên bậc đầu tiên (tức là phủ các bậc ). Hộp rơi xuống cho đến khi đáy của nó chạm vào mặt trên của một bậc thang hoặc mặt trên của một hộp đã thả trước đó (trong phạm vi các bậc ). Chỉ tính việc chạm theo mặt nằm ngang: hộp có chiều rộng không chạm vào bậc . Hộp tiếp theo chỉ được thả sau khi hộp trước đã nằm yên.
Với mỗi hộp, hãy cho biết độ cao của đáy hộp sau khi nó dừng lại.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên , số bậc thang.
- Dòng thứ hai chứa số nguyên .
- Dòng thứ ba chứa số nguyên , số hộp.
- dòng tiếp theo, dòng thứ chứa hai số nguyên và .
Dữ liệu ra
In ra dòng, dòng thứ là độ cao của đáy hộp thứ sau khi dừng lại, theo đúng thứ tự thả.
Ràng buộc
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 1 2 3 6 6 4 1 1 3 1 1 1 4 3 |
1 3 4 6 |
Hộp 1 nằm trên bậc 1 (độ cao 1), đỉnh ở độ cao 2. Hộp 2 phủ bậc 1..3, bậc 3 cao 3 nên đáy ở độ cao 3, đỉnh ở 4. Hộp 3 nằm trên hộp 2, đáy ở 4, đỉnh ở 5. Hộp 4 phủ bậc 1..4, bậc 4 cao 6 nên đáy ở 6. |
| 3 1 2 3 2 1 1 3 1 |
1 3 |
Hộp 2 phủ cả 3 bậc, chạm bậc 3 ở độ cao 3 trước khi chạm hộp 1 (đỉnh ở độ cao 2). |
| 1 1 5 1 2 1 10 1 10 1 10 1 10 |
1 3 13 23 33 |
Các hộp chồng lên nhau trên bậc duy nhất. |
Bình luận