No.1584 Stones around Circle Pond
Problem Statement
There is a circular pond whose circumference is $2L$. There is a point A on this circumference.
There are $2N$ spots on the circumference of this pond, and the $i$-th spot (which we will call spot $i$) is located
- (if $1 \leq i \leq N$) $\ \ $ at the position reached by traveling $d_i$ clockwise around the pond from point A
- (if $N+1 \leq i \leq 2N$) $\ \ $ at the position reached by traveling $L+d_{i-N}$ clockwise around the pond from point A
Consider P-kun performing the following operation any number of times, possibly $0$.
Operation
Choose one spot among the $2N$ spots. For every $i$ satisfying $1 \leq i \leq 2N$, place stones as follows.
- Place on spot $i$ a number of stones equal to the shortest distance from the chosen spot to spot $i$ along the circumference of the pond.
You are given an integer sequence $B_1, B_2,..., B_{2N}$ of length $2N$. Determine whether P-kun can satisfy the following condition by performing the operations appropriately.
If the condition can be satisfied, output Yes; if it can never be satisfied, output No.
Condition
Letting $C_i$ be the number of stones that have been placed on spot $i$ at the end as a result of P-kun's operations, $B_i=C_i$ holds for all $i$ satisfying $1 \leq i \leq 2N$.
Input
$N\ \ L$
$d_1\ \ d_2\ \ \ldots \ \ d_N$
$B_1\ \ B_2\ \ \ldots \ \ B_{2N}$
- $1 \leq N \leq 100$
- $1 \leq L \leq 10^6$
- $0 \leq d_1 < d_2 < \ldots < d_N < L$
- $0 \leq B_i \leq 10^9 \ (1 \leq i \leq 2N)$
- All inputs are integers.
Output
Output Yes or No, followed by a newline.
Sample
Sample 1
Input
2 5 1 3 10 8 5 7
Output
Yes
P-kun can satisfy the condition by choosing spot 1 once and spot 3 twice.
Sample 2
Input
2 5 1 3 3 8 5 4
Output
No
The condition can never be satisfied.
Sample 3
Input
2 5 1 3 0 0 0 0
Output
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
magsta
nok0