trang chủ / đề bài / icpcwf14_j

Trượt tuyết

Đề bài

Mô tả

Như bạn đã biết, ACM ICPC không phải là sự kiện thể thao lớn duy nhất diễn ra ở Nga trong năm nay. Vài tháng trước, Thế vận hội Mùa đông 2014 được tổ chức tại Sochi, cách Ekaterinburg khoảng 3000 km.

Trong ngày càng nhiều môn thể thao, người chiến thắng không chỉ được quyết định bởi khả năng của vận động viên mà còn bởi trang thiết bị của họ. Ví dụ, trong môn trượt tuyết đổ dốc, có được công nghệ ván trượt mới nhất giúp vận động viên tăng tốc độ và cải thiện khả năng chuyển hướng.

Bạn được thuê để xác định ảnh hưởng của công nghệ ván trượt mới nhất tới khả năng của vận động viên khi trượt trên một đường đua đổ dốc. Đường đua có một số vị trí mục tiêu, và vận động viên muốn trượt qua càng nhiều mục tiêu càng tốt. Tất nhiên, công nghệ ván trượt càng tốt thì việc này càng dễ.

Để đơn giản, dùng hệ tọa độ hai chiều trong đó vận động viên xuất phát tại vị trí (0,0) và hướng "xuống dốc" là chiều dương của trục y.

Giả sử thành phần theo trục y của vận tốc vận động viên là hằng số vy. Vận động viên có thể thay đổi vận tốc theo phương ngang (phương x), nhưng trang thiết bị giới hạn gia tốc ngang không vượt quá amax. Vận động viên xuất phát với vận tốc ngang bằng 0.

Trong hình trên (ứng với ví dụ thứ nhất), đường trượt tối ưu đi qua ba trong bốn mục tiêu. Nếu amax nhỏ hơn, vận động viên có thể chỉ đi qua được hai mục tiêu hoặc ít hơn.

Dữ liệu vào

Dữ liệu vào gồm một bộ test duy nhất. Dòng đầu tiên chứa ba số nguyên n, vy và amax, trong đó n là số mục tiêu, vy là thành phần theo trục y của vận tốc vận động viên, và amax là gia tốc ngang tối đa. vy tính bằng mét trên giờ và amax tính bằng mét trên giờ bình phương.

Tiếp theo là n dòng, mỗi dòng chứa hai số nguyên xi và yi là tọa độ của một mục tiêu. Mọi tọa độ tính bằng mét. Các mục tiêu được đánh số 1,2,…,n theo thứ tự xuất hiện trong dữ liệu vào.

Dữ liệu ra

In ra dãy mục tiêu dài nhất mà vận động viên có thể đi qua trong một lượt trượt. In các mục tiêu theo thứ tự chúng được đi qua. Nếu có nhiều dãy có độ dài lớn nhất, chỉ in dãy nhỏ nhất theo thứ tự từ điển (chẳng hạn dãy 2 15 đứng trước dãy 10 15). Nếu vận động viên không thể đi qua mục tiêu nào, in ra Cannot visit any targets.

Để đảm bảo ổn định khi tính toán số thực, bạn có thể giả sử rằng đáp án không thay đổi khi amax bị thay đổi một lượng không quá 0,1.

Ràng buộc

  • 0≤n≤250.
  • 0≤vy≤105.
  • 0≤amax≤107.
  • −105≤xi,yi≤105.

Ví dụ

Input Output Giải thích
4 100 400
-100 100
50 200
-100 300
150 300
1 2 4 Ứng với hình trên. Mục tiêu 3 và 4 có cùng y=300 nên không thể đi qua cả hai; đường trượt tối ưu đi qua các mục tiêu 1, 2, 4.
1 100 100
1000 10
Cannot visit any targets Mục tiêu ở y=10 được tới sau 0,1 giờ, khi đó vận động viên chỉ dịch ngang được tối đa 100·0,12/2=0,5 mét.

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