FPC25-031.Frog and Princess

Easy · 2 s · 256 MB

icpc
fpc
2025

In the distant land of Glimmerbrook, there once lived a noble prince, brave of heart. Alas, his fate took a cruel turn when he crossed paths with an ancient and vengeful wizard. With a flick of his staff, the wizard cast a dreadful curse – transforming the prince into a frog, slimy and green. The curse was no ordinary spell, but part of an age-old magical trial known as the Geometric Arcane Puzzle of Coordinates – a test designed by the old wizards to trap the bold and free-spirited. Now, bound by enchantment, the frog-prince must reach the princess – for only her touch can break the curse and restore his true form.

The magic has twisted his very legs: he may leap no more than $n$ times. The length of each jump (measured in Euclidean distance) is strictly dictated by the ancient spell: on the $i$ th jump, the frog should jump a distance of $a_i$ , no more, no less. If he can land at the princess's side before his jumps run out, the curse will shatter instantly (even if some jumps remain) and he shall be free. But should he fall short, he will remain a frog forevermore.

Giriş formatı

The input consists of:

• One line with an integer $n$ ( $1\leq n\leq 4 \cdot 10^5$ ), the number of jumps that the frog can make.

• One line with four integers $x_f$ , $y_f$ , $x_p$ , and $y_p$ ( $-10^9\leq x_f, y_f, x_p, y_p \leq 10^9$ ), the coordinates $(x_f, y_f)$ of the starting position of the frog, and the coordinates $(x_p, y_p)$ of the princess.

• One line with $n$ integers $a_1, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ for each $i$ , and $\sum_{i=1}^n a_i \leq 2 \cdot 10^9$ ), where $a_i$ is the length of the $i$ th jump of the frog.

It is guaranteed that the coordinates of the frog and those of the princess are not the same.

Çıxış formatı

Output “yes” if the frog can jump to the exact position of the princess, and “no” otherwise.

Qeyd

Source: Freshmen Programming Contest 2025 · License: CC BY-SA 4.0 · Original: https://fpc.wisv.ch · Statement adapted for AlgoLens and shared under the same license. · 1 of the 41 original test cases (the largest) are omitted here to keep the problem lightweight.

Nümunələr

Giriş #1

3
0 0 2 2
1 2 3

Çıxış #1

yes

Giriş #2

2
0 0 -2 -2
1 1

Çıxış #2

no

Giriş #3

3
0 0 2 2
6 1 2

Çıxış #3

no

Giriş #4

1
0 1 1000000000 0
1000000000

Çıxış #4

no

Giriş formatı

The input consists of:

• One line with an integer $n$ ( $1\leq n\leq 4 \cdot 10^5$ ), the number of jumps that the frog can make.

• One line with $n$ integers $a_1, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ for each $i$ , and $\sum_{i=1}^n a_i \leq 2 \cdot 10^9$ ), where $a_i$ is the length of the $i$ th jump of the frog.

It is guaranteed that the coordinates of the frog and those of the princess are not the same.