No.2648 [Cherry 6th Tune D] One-Dimensional Horses
レベル :
/ AI推定難易度 : 525
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 148
作問者 : 👑
Kazun
/ テスター :
hirayuu_yc
タグ : / 解いたユーザー数 148
作問者 : 👑
Kazun
/ テスター :
問題文最終更新日: 2024-02-23 21:36:30
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 418 (Re: start!)
(順位表)
の他の問題:
Problem Statement
There are $N$ horses on a number line. These horses are numbered $1,2, \dots, N$.
Initially, horse $i$ is at coordinate $A_i$.
When Cherry-chan blows her whistle, the $N$ horses simultaneously perform the following action.
- Suppose horse $i$ is at coordinate $x$ when the whistle blows. Then, horse $i$ moves to coordinate $(x+i)$.
When Cherry-chan blows the whistle any number of times, $0$ or more, is it possible for the following to be satisfied? If it is possible, find the minimum number of times Cherry-chan blows the whistle until such a situation is reached.
- Let $X_i$ be the coordinate where horse $i$ is. Then, $X_1 \lt X_2 \lt \dots \lt X_{N-1} \lt X_N$ holds.
Constraints
- $1 \leq T \leq 10^5$.
- Constraints for each test case.
- $2 \leq N \leq 2 \times 10^5$.
- $0 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$.
- Constraints for each test file.
- The sum of $N$ over the $T$ test cases is at most $2 \times 10^5$.
- All inputs are integers.
Input
$T$
${\rm Testcase}_1$
${\rm Testcase}_2$
$\vdots$
${\rm Testcase}_T$
Each test case is given in the following format.
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
Output
The output consists of $T$ lines. On line $t~(1 \leq t \leq T)$, output the answer for the $t$-th test case in the following format.
- If the condition cannot be satisfied no matter how many times the whistle is blown, output
-1. If it can be satisfied, output as an integer the minimum number of times the whistle is blown until the condition is satisfied.
Do not forget the newline at the end.
Sample
Sample 1
Input
4 3 3 1 2 5 1 2 3 4 5 4 46 46 46 46 10 886822852 554802233 259460418 345136263 8466085 424914285 852474622 856826548 201867 777749594
Output
3 0 1 856624682
- [Test case $1$] Suppose Cherry-chan blows the whistle $3$ times. Then, each horse moves as follows.
- When the $1$st whistle blows, horse $1$ moves from coordinate $3$ to coordinate $4$, horse $2$ moves from coordinate $1$ to coordinate $3$, and horse $3$ moves from coordinate $2$ to coordinate $5$.
- When the $2$nd whistle blows, horse $1$ moves from coordinate $4$ to coordinate $5$, horse $2$ moves from coordinate $3$ to coordinate $5$, and horse $3$ moves from coordinate $5$ to coordinate $8$.
- When the $3$rd whistle blows, horse $1$ moves from coordinate $5$ to coordinate $6$, horse $2$ moves from coordinate $5$ to coordinate $7$, and horse $3$ moves from coordinate $8$ to coordinate $11$.
- [Test case $2$] It is possible that $X_1 \lt X_2 \lt \dots \lt X_N$ already holds without blowing the whistle.
- [Test case $3$] Note that $X_1=X_2=X_3=X_4$ does not satisfy the condition.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。