Koa và Bãi biển (bản dễ)
Đề bài
Mô tả
Bờ biển được mô tả (từ trái sang phải) gồm: một bãi bờ, tiếp theo là mét biển, và một hòn đảo nằm ở vị trí cách bờ mét. Người ta đo độ sâu của biển tại các vị trí mét tính từ bờ, lưu vào mảng : là độ sâu tại vị trí cách bờ mét.
Thủy triều thay đổi độ sâu theo thời gian, đặc trưng bởi tham số . Đặt mảng (đánh chỉ số từ ) có độ dài :
Tại thời điểm nguyên (), độ sâu tại vị trí cách bờ mét bằng .
Tại thời điểm Koa đang đứng ở bờ (vị trí ) và muốn tới hòn đảo. Giả sử tại thời điểm cô đang ở vị trí ():
- Trong một giây, Koa có thể bơi tiến ra xa bờ thêm mét ( tăng thành ) hoặc đứng yên ( giữ nguyên); trong cả hai trường hợp tăng thành .
- Koa bơi kém, nên nếu tại một thời điểm nguyên cô đang ở vị trí với thì độ sâu tại đó không được vượt quá , tức phải luôn có (nếu không cô sẽ chết đuối).
- Khi Koa tới hòn đảo (vị trí ) thì cô dừng lại và an toàn.
Lưu ý: trong lúc đang bơi (giữa hai thời điểm nguyên) thủy triều không ảnh hưởng tới Koa; ràng buộc độ sâu chỉ áp dụng tại các thời điểm nguyên. Bờ (vị trí ) và hòn đảo (vị trí ) luôn an toàn: Koa có thể đứng ở bờ bao lâu tùy ý.
Hãy xác định Koa có thể đi từ bờ tới hòn đảo hay không.
Dữ liệu vào
- Dòng đầu chứa số nguyên : số lượng bộ dữ liệu.
- Với mỗi bộ dữ liệu:
- Dòng đầu chứa ba số nguyên , , .
- Dòng thứ hai chứa số nguyên .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra Yes nếu Koa có thể tới hòn đảo, ngược lại in ra No. Có thể in chữ cái ở dạng hoa hoặc thường tùy ý.
Ràng buộc
- ; ;
- Tổng trên tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 2 1 1 1 0 5 2 3 1 2 3 2 2 4 3 4 0 2 4 3 2 3 5 3 0 7 2 3 3 0 2 1 3 0 1 7 1 4 4 4 3 0 2 4 2 5 2 3 1 2 3 2 2 |
Yes No Yes Yes Yes No No |
Ở bộ đầu tiên , , , . Koa đợi giây ở bờ (để thủy triều xuống), rồi lần lượt bơi qua vị trí rồi vị trí đúng vào các thời điểm độ sâu bằng và , cuối cùng bước lên đảo. Ở bộ thứ hai không có lịch trình nào an toàn. |
| 1 10 5 10 0 0 0 1 1 1 1 1 5 5 |
Yes | nên có chu kỳ , đỉnh triều là . Chọn thời điểm xuất phát thích hợp, Koa vượt qua được toàn bộ vị trí vì tổng độ sâu cực đại . |
Bình luận