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 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í và hướng "xuống dốc" là chiều dương của trục .
Giả sử thành phần theo trục của vận tốc vận động viên là hằng số . Vận động viên có thể thay đổi vận tốc theo phương ngang (phương ), nhưng trang thiết bị giới hạn gia tốc ngang không vượt quá . Vận động viên xuất phát với vận tốc ngang bằng .

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 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 , và , trong đó là số mục tiêu, là thành phần theo trục của vận tốc vận động viên, và là gia tốc ngang tối đa. tính bằng mét trên giờ và tính bằng mét trên giờ bình phương.
Tiếp theo là dòng, mỗi dòng chứa hai số nguyên và 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ố 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 bị thay đổi một lượng không quá .
Ràng buộc
- .
- .
- .
- .
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 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 ở được tới sau giờ, khi đó vận động viên chỉ dịch ngang được tối đa mét. |
Bình luận