trang chủ / đề bài / 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,…,k−1,k,k−1,…,2,1].

Tại thời điểm nguyên t (t≥0), độ 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 (0≤x≤n):

  • 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 1≤x≤n 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

  • 1≤t≤100
  • 1≤n≤100; 1≤k≤100; 1≤l≤100
  • 0≤di≤100
  • 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 0≤1 và 1≤1, 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=10≤l.

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0