trang chủ / bài tập / koabeach37

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à n+1 mét biển, và một hòn đảo nằm ở vị trí cách bờ n+1 mét. Người ta đo độ sâu của biển tại các vị trí 1,2,,n mét tính từ bờ, lưu vào mảng d: di là độ sâu tại vị trí cách bờ i mét.

Thủy triều thay đổi độ sâu theo thời gian, đặc trưng bởi tham số k. Đặt mảng p (đánh chỉ số từ 0) có độ dài 2k:

p=[0,1,2,,k1,k,k1,,2,1].

Tại thời điểm nguyên t (t0), độ sâu tại vị trí cách bờ i mét bằng di+p[tmod2k].

Tại thời điểm t=0 Koa đang đứng ở bờ (vị trí x=0) và muốn tới hòn đảo. Giả sử tại thời điểm t cô đang ở vị trí x (0xn):

  • Trong một giây, Koa có thể bơi tiến ra xa bờ thêm 1 mét (x tăng thành x+1) hoặc đứng yên (x giữ nguyên); trong cả hai trường hợp t tăng thành t+1.
  • Koa bơi kém, nên nếu tại một thời điểm nguyên t cô đang ở vị trí x với 1xn thì độ sâu tại đó không được vượt quá l, tức phải luôn có dx+p[tmod2k]l (nếu không cô sẽ chết đuối).
  • Khi Koa tới hòn đảo (vị trí n+1) 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í 0) và hòn đảo (vị trí n+1) 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 t: số lượng bộ dữ liệu.
  • Với mỗi bộ dữ liệu:
    • Dòng đầu chứa ba số nguyên n, k, l.
    • Dòng thứ hai chứa n số nguyên d1,d2,,dn.

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

  • 1t100
  • 1n100; 1k100; 1l100
  • 0di100
  • Tổng n trên tất cả các bộ dữ liệu không vượt quá 100.

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 n=2, k=1, l=1, p=[0,1]. Koa đợi 1 giây ở bờ (để thủy triều xuống), rồi lần lượt bơi qua vị trí 1 rồi vị trí 2 đúng vào các thời điểm độ sâu bằng 0111, 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 k=5 nên p có chu kỳ 10, đỉnh triều là 5. Chọn thời điểm xuất phát thích hợp, Koa vượt qua được toàn bộ 10 vị trí vì tổng độ sâu cực đại 5+5=10l.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0