EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2014
ICPC 2014

J. Skiing

As you know, the ACM ICPC is not the only major sporting event taking place in Russia this year. Several months ago, the 2014 Winter Olympics were held in Sochi, which is about 3 000 km from Ekaterinburg. In an increasing number of sports, it is not only th...

Updated May 21, 2026
Track ICPC
Year 2014
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF
Time limit 2 seconds

As you know, the ACM ICPC is not the only major sporting event taking place in Russia this year. Several months ago, the 2014 Winter Olympics were held in Sochi, which is about 3 000 km from Ekaterinburg. In an increasing number of sports, it is not only the ability of the athletes that determines who wins a competition but also their equipment. For example in downhill skiing, having the latest ski technology enables athletes to increase their speeds and improve their turning ability. You have been hired to determine the effect of the latest ski technology on the ability of skiers to navigate a downhill course. The course contains several target locations, and the skier wants to pass over as many of them as possible. Naturally, the better the ski technology, the easier it will be to do this. For simplicity, use a two-dimensional coordinate system where the skier starts at position (0,0) and where “downhill” corresponds to the direction of the positive y-axis. Assume the y-component of the athlete’s velocity is a constant vy . The athlete can change speed laterally (in the x-direction), but the skiing equipment limits this to a maximal lateral acceleration amax . The skier starts with a lateral velocity of 0.

Skier’s path
(0,0)
Figure J.1: Downhill ski path passing over three targets

In Figure J.1 (which corresponds to the first sample input), the optimal path passes over three out of four possible targets. If amax were smaller, then the skier might be able to pass over only two or fewer of the targets.

Input

The input contains a single test case. The first line contains three integers n, vy , and amax (0 ≤ n ≤ 250, 0 ≤ vy ≤ 105 and 0 ≤ amax ≤ 107 ), where n is the number of targets, vy is the y-component of the skier’s velocity, and amax is the maximum lateral acceleration. Here vy is given in meters per hour and amax in meters per hour squared. Following this are n lines, each containing two integers xi and yi (−105 ≤ xi , yi ≤ 105 ). These give the coordinates of each target to be visited on the course. All coordinates are given in meters. Targets are numbered 1, 2, ..., n in the order they are given.

Output

Display the maximal-length sequence of targets that the athlete could pass over on the course in a single run. Display the targets in the order they are visited. If there are multiple maximal-length sequences, display only the lexicographically first one. (So the sequence 2 15 would come before the sequence 10 15.) If the athlete cannot pass over any targets, print Cannot visit any targets instead. To ensure floating-point stability, you may assume the answer will not change if amax is perturbed by up to 0.1.

Sample Tests

Sample 1
Sample Input 
 4 100 400
 -100 100
 50 200
 -100 300
 150 300
Sample Output 
1 2 4
Sample 2
Sample Input 
 1 100 100
 1000 10
Sample Output 
Cannot visit any targets
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • Write the structural observations that make the problem tractable.

  • State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.

  • If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

  • Mention any non-obvious implementation detail that is easy to get wrong.

  • Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

Raw file 
#include <bits/stdc++.h>
using namespace std;

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2014/J-skiing/solution.texC++ implementationcompetitive_programming/icpc/2014/J-skiing/solution.cppStatement textcompetitive_programming/icpc/2014/J-skiing/statement.txtStatement PDFcompetitive_programming/icpc/2014/J-skiing/statement.pdfMetadatacompetitive_programming/icpc/2014/J-skiing/meta.jsonYear packetcompetitive_programming/icpc/2014/contest_problems.pdf