Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
石の山が N 個あり,i 番目 (1 \leq i \leq N) の山には A_i 個の石が積まれています.
あなたは今から正整数 k を選びます. その後,Alice と Bob がこの山を使って以下のようなゲームを行います.
- Alice から始めて両者は交互に手番をプレイする.
- 各手番では,プレイヤーは空でない山を一つ選び,その山から 1 個以上 k 個以下の好きな個数の石を取り除く.
自分の手番で操作が行えなくなった人が負けで,負けなかった人が勝ちです.
あなたは正整数 k を選ぶとき,Alice に必勝法が存在するようにしたいです. そのような k が存在するか判定してください. 存在する場合は,そのような k の最大値が存在するか判定してください. 最大値が存在する場合は,その値を答えてください.
制約
- 1 \leq N \leq 250000
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数.
入力
入力は以下の形式で標準入力から与えられる.
N A_1 A_2 \cdots A_N
出力
Alice に必勝法が存在するような k が存在しない場合,0 を出力せよ.
Alice に必勝法が存在するような k が存在するが,その最大値が存在しない場合,-1 を出力せよ.
Alice に必勝法が存在するような k が存在し,その最大値も存在する場合,その値を出力せよ.
入力例 1
3 1 2 3
出力例 1
2
例えば,k=2 とすると Alice に必勝法が存在します. 3 \leq k を選んだ場合は Alice に必勝法が存在しないので,k=2 が答えです.
入力例 2
4 1 2 3 4
出力例 2
-1
例えば,すべての k=100,200,300,\cdots に対して Alice に必勝法が存在します. よって k の最大値は存在しないため,-1 を出力します.
入力例 3
2 100 100
出力例 3
0
どのような k を選んでも Alice に必勝法は存在しません. よって 0 を出力します.
Score : 400 points
Problem Statement
There are N piles of stones, and the i-th pile (1 \leq i \leq N) has A_i stones.
You will choose a positive integer k. Then, Alice and Bob will play a game with these piles as follows.
- Starting with Alice, the players take turns to play.
- In each turn, the player must choose a non-empty pile and remove from it some number of stones between 1 and k, inclusive.
The person who cannot make a move on their turn loses, and the other person wins.
You want to choose a positive integer k for which there is a winning strategy for Alice. Determine if such a k exists. If it exists, determine if there is a maximum value for such k. If the maximum value exists, provide that value.
Constraints
- 1 \leq N \leq 250000
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
If there is no k for which Alice has a winning strategy, print 0.
If there is a k for which Alice has a winning strategy, and there is no maximum value for such k, print -1.
If there is a k for which Alice has a winning strategy, and there is a maximum value for such k, print that value.
Sample Input 1
3 1 2 3
Sample Output 1
2
For example, if k=2, Alice has a winning strategy. If k \geq 3, Alice has no winning strategy, so the answer is k=2.
Sample Input 2
4 1 2 3 4
Sample Output 2
-1
For example, Alice has winning strategies for all k=100,200,300,\cdots. Thus, there is no maximum value for k, so print -1.
Sample Input 3
2 100 100
Sample Output 3
0
No matter what k is chosen, Alice has no winning strategy. Thus, print 0.