trang chủ / đề bài / icpc21_mn_k

Trò chơi con mực

Đề bài

Mô tả

Có n người chơi tham gia một phiên bản của trò chơi "Squid Game" trong một cơ sở bí mật. Mọi người chơi đều đứng trên một trục số (không gian một chiều). Trong trò chơi có một sát thủ. Người chơi và sát thủ đều di chuyển với tốc độ 1 mét mỗi giây, nhưng tại mỗi thời điểm chỉ có một người được di chuyển. Nếu sát thủ và một số người chơi ở cùng một điểm tại cùng một thời điểm thì những người chơi đó bị loại.

Có một nơi trú ẩn chứa được bao nhiêu người chơi cũng được, nhưng sát thủ không thể đi qua nơi trú ẩn. Nếu một người chơi tới được nơi trú ẩn và lúc đó sát thủ không ở đó thì người chơi ấy được cứu.

Bạn biết bản đồ, vị trí của mọi người chơi và vị trí của sát thủ. Trò chơi diễn ra theo từng giây: trong mỗi giây, sát thủ đi trước (di chuyển 1 mét hoặc đứng yên), sau đó bạn ra lệnh cho đúng một người chơi di chuyển 1 mét (hoặc không ra lệnh). Sát thủ hành động theo cách bất lợi nhất cho bạn.

Yêu cầu: Tìm số người chơi lớn nhất mà bạn chắc chắn cứu được.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n: số người chơi.
  • Dòng thứ hai chứa n số nguyên x1,x2,…,xn: tọa độ của các người chơi.
  • Dòng thứ ba chứa số nguyên y: tọa độ (tính bằng mét) của sát thủ.
  • Dòng cuối cùng chứa số nguyên z: tọa độ của nơi trú ẩn.

Dữ liệu ra

In ra một số nguyên: số người chơi lớn nhất mà bạn chắc chắn cứu được.

Ràng buộc

  • 1≤n≤105.
  • |xi|≤109, |y|≤109, |z|≤109.

Ví dụ

Input Output Giải thích
3
-1 1 3
2
0
1 Người ở 3 không thể vượt qua sát thủ. Ở giây đầu tiên sát thủ tới 1 và loại người ở đó; người ở −1 vẫn kịp về nơi trú ẩn.
3
0 0 9
10
1
2 Hai người ở 0 về nơi trú ẩn trong 2 giây. Người ở 9 bị sát thủ bắt ngay ở giây đầu tiên.

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