This page is still under construction.

Parts of this page are still being built. What you see may change.

Skiing

Time limit2sMemory limit128 MB

Summary
Starting at (0,0) with fixed downhill speed and bounded lateral acceleration, choose the longest reachable target sequence with smallest indices on ties.
Level

Medium7 of 10

Topics
Dynamic programming, Math, Sorting
Solved
No attempts yet

Problem

Skier starts at (0,0)(0,0) with constant vyv_y downhill. Lateral acceleration is bounded by amaxa_{max}. Visit the longest possible sequence of targets.

Input

nn, vyv_y, amaxa_{max}, then nn target coordinates.

Output

Target indices visited, lexicographically smallest among maximum length. Or Cannot visit any targets.

Examples1

  1. Example 1

    Input
    4 100 400
-100 100
50 200
-100 300
150 300
    Expected output
    1 2 4