Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
黒板に N 個の整数が書かれています。i 番目の整数は A_i です。
これらの数に対して、高橋君は以下の操作を繰り返します。
- 偶奇が等しい 2 つの数 A_i,A_j を一組選び、それらを黒板から消す。
- その後、二つの数の和 A_i+A_j を黒板に書く。
最終的に黒板に数が 1 つだけ残るようにできるかどうか判定して下さい。
制約
- 2 ≦ N ≦ 10^5
- 1 ≦ A_i ≦ 10^9
- A_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 … A_N
出力
黒板に数 1 つだけ残るようにできるなら YES を、そうでないなら NO を出力せよ。
入力例 1
3 1 2 3
出力例 1
YES
以下のようにすれば、数を 1 つだけ残すことができます。
- 黒板から 1 と 3 を消し、4 を書く。このとき、残る数は (2,4) である。
- 黒板から 2 と 4 を消し、6 を書く。このとき、残る数は 6 だけである。
入力例 2
5 1 2 3 4 5
出力例 2
NO
Score : 300 points
Problem Statement
There are N integers written on a blackboard. The i-th integer is A_i.
Takahashi will repeatedly perform the following operation on these numbers:
- Select a pair of integers, A_i and A_j, that have the same parity (that is, both are even or both are odd) and erase them.
- Then, write a new integer on the blackboard that is equal to the sum of those integers, A_i+A_j.
Determine whether it is possible to have only one integer on the blackboard.
Constraints
- 2 ≦ N ≦ 10^5
- 1 ≦ A_i ≦ 10^9
- A_i is an integer.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 … A_N
Output
If it is possible to have only one integer on the blackboard, print YES. Otherwise, print NO.
Sample Input 1
3 1 2 3
Sample Output 1
YES
It is possible to have only one integer on the blackboard, as follows:
- Erase 1 and 3 from the blackboard, then write 4. Now, there are two integers on the blackboard: 2 and 4.
- Erase 2 and 4 from the blackboard, then write 6. Now, there is only one integer on the blackboard: 6.
Sample Input 2
5 1 2 3 4 5
Sample Output 2
NO
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
N 個の箱が円環状に並んでおり、i 番目の箱には A_i 個の石が入っています。
以下の操作を繰り返して、全ての石を取り除くことができるか判定してください。
- 箱を一か所選ぶ。それを i 番目としたとき、1 から N の各 j に対して、i+j 番目の箱から石をちょうど j 個取り除く。
ただし、N+k 番目と表される箱は k 番目の箱と同一視するものとする。
各操作において、取り除きたい個数の石がない箱があるときは、その操作を行えないことに注意してください。
制約
- 1 ≦ N ≦ 10^5
- 1 ≦ A_i ≦ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 … A_N
出力
全ての石を取り除くことができるなら YES を、そうでないなら NO を出力せよ。
入力例 1
5 4 5 1 2 3
出力例 1
YES
最初に箱 2 を選ぶことで、一回の操作ですべての石を回収できます。
入力例 2
5 6 9 12 10 8
出力例 2
YES
入力例 3
4 1 2 3 1
出力例 3
NO
Score : 500 points
Problem Statement
There are N boxes arranged in a circle. The i-th box contains A_i stones.
Determine whether it is possible to remove all the stones from the boxes by repeatedly performing the following operation:
- Select one box. Let the box be the i-th box. Then, for each j from 1 through N, remove exactly j stones from the (i+j)-th box. Here, the (N+k)-th box is identified with the k-th box.
Note that the operation cannot be performed if there is a box that does not contain enough number of stones to be removed.
Constraints
- 1 ≦ N ≦ 10^5
- 1 ≦ A_i ≦ 10^9
Input
The input is given from Standard Input in the following format:
N A_1 A_2 … A_N
Output
If it is possible to remove all the stones from the boxes, print YES. Otherwise, print NO.
Sample Input 1
5 4 5 1 2 3
Sample Output 1
YES
All the stones can be removed in one operation by selecting the second box.
Sample Input 2
5 6 9 12 10 8
Sample Output 2
YES
Sample Input 3
4 1 2 3 1
Sample Output 3
NO
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
N 頂点からなる木があり、頂点には 1 から N の番号がついています。 また、N-1 本の辺の内、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。
今、各頂点 i には A_i 個の石が置いてあります。 以下の操作を繰り返して、全ての石を取り除くことができるか判定してください。
- 相異なる 2 つの葉を一組選ぶ。そして、その 2 頂点間のパス上にある頂点全てからちょうど 1 つ石を取り除く。
ただし、葉とは木の頂点で次数が 1 の頂点を指し、選んだ葉自体もパス上の頂点として考える。
石が置かれていない頂点がパス上にあるときは、その操作を行えないことに注意してください。
制約
- 2 ≦ N ≦ 10^5
- 1 ≦ a_i,b_i ≦ N
- 0 ≦ A_i ≦ 10^9
- 与えられるグラフは木である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 … A_N
a_1 b_1
:
a_{N-1} b_{N-1}
出力
全ての石を取り除くことができるなら YES を、そうでないなら NO を出力せよ。
入力例 1
5 1 2 1 1 2 2 4 5 2 3 2 1 3
出力例 1
YES
以下のようにすれば、すべての石を取り除くことができます。
- 葉として 4 と 5 を選ぶ。このとき、4 以外の頂点に石が 1 個残る。
- 葉として 1 と 5 を選ぶ。このとき、全ての頂点から石がなくなる。
入力例 2
3 1 2 1 1 2 2 3
出力例 2
NO
入力例 3
6 3 2 2 2 2 2 1 2 2 3 1 4 1 5 4 6
出力例 3
YES
Score : 700 points
Problem Statement
There is a tree with N vertices, numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.
Currently, there are A_i stones placed on vertex i. Determine whether it is possible to remove all the stones from the vertices by repeatedly performing the following operation:
- Select a pair of different leaves. Then, remove exactly one stone from every vertex on the path between those two vertices. Here, a leaf is a vertex of the tree whose degree is 1, and the selected leaves themselves are also considered as vertices on the path connecting them.
Note that the operation cannot be performed if there is a vertex with no stone on the path.
Constraints
- 2 ≦ N ≦ 10^5
- 1 ≦ a_i,b_i ≦ N
- 0 ≦ A_i ≦ 10^9
- The given graph is a tree.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 … A_N
a_1 b_1
:
a_{N-1} b_{N-1}
Output
If it is possible to remove all the stones from the vertices, print YES. Otherwise, print NO.
Sample Input 1
5 1 2 1 1 2 2 4 5 2 3 2 1 3
Sample Output 1
YES
All the stones can be removed, as follows:
- Select vertices 4 and 5. Then, there is one stone remaining on each vertex except 4.
- Select vertices 1 and 5. Then, there is no stone on any vertex.
Sample Input 2
3 1 2 1 1 2 2 3
Sample Output 2
NO
Sample Input 3
6 3 2 2 2 2 2 1 2 2 3 1 4 1 5 4 6
Sample Output 3
YES
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
黒板に N 個の整数が書かれています。i 番目の整数は A_i であり、これらの最大公約数は 1 です。
高橋君と青木君はこの数を使ってゲームをします。ゲームでは高橋君から始めて交互に以下の操作を繰り返します。
- 黒板の中から 2 以上の数を 1 つ選び、その数から 1 を引く。
- その後、黒板に書かれた数の最大公約数を g として、すべての数を g で割る。
黒板に書かれた数が全て 1 となっていて、操作が行えない人の負けです。 二人が最適に行動したとき、どちらが勝つか求めてください。
制約
- 1 ≦ N ≦ 10^5
- 1 ≦ A_i ≦ 10^9
- A_1 から A_N の最大公約数は 1
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 … A_N
出力
先手の高橋君が勝つなら First を、後手の青木君が勝つなら Second を出力せよ。
入力例 1
3 3 6 7
出力例 1
First
以下のようにすれば先手の高橋君が勝てます。
- 高橋君が 7 から 1 を引く。このとき、操作後は (1,2,2) となる。
- 青木君が 2 から 1 を引く。このとき、操作後は (1,1,2) となる。
- 高橋君が 2 から 1 を引く。このとき、操作後は (1,1,1) となる。
入力例 2
4 1 2 4 8
出力例 2
First
入力例 3
5 7 8 8 8 8
出力例 3
Second
Score : 1000 points
Problem Statement
There are N integers written on a blackboard. The i-th integer is A_i, and the greatest common divisor of these integers is 1.
Takahashi and Aoki will play a game using these integers. In this game, starting from Takahashi the two player alternately perform the following operation:
- Select one integer on the blackboard that is not less than 2, and subtract 1 from the integer.
- Then, divide all the integers on the black board by g, where g is the greatest common divisor of the integers written on the blackboard.
The player who is left with only 1s on the blackboard and thus cannot perform the operation, loses the game. Assuming that both players play optimally, determine the winner of the game.
Constraints
- 1 ≦ N ≦ 10^5
- 1 ≦ A_i ≦ 10^9
- The greatest common divisor of the integers from A_1 through A_N is 1.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 … A_N
Output
If Takahashi will win, print First. If Aoki will win, print Second.
Sample Input 1
3 3 6 7
Sample Output 1
First
Takahashi, the first player, can win as follows:
- Takahashi subtracts 1 from 7. Then, the integers become: (1,2,2).
- Aoki subtracts 1 from 2. Then, the integers become: (1,1,2).
- Takahashi subtracts 1 from 2. Then, the integers become: (1,1,1).
Sample Input 2
4 1 2 4 8
Sample Output 2
First
Sample Input 3
5 7 8 8 8 8
Sample Output 3
Second
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1600 点
問題文
黒板に N 個の整数が書かれています。i 番目の整数は A_i です。
高橋君と青木君は以下の手順でこれらの数を一列に並べることにしました。
- 最初に、高橋君が好きな順に一列に並べる。
- 次に、青木君が隣り合う 2 つの数を選んで入れ替えることを好きな回数だけ繰り返す。
ただし、入れ替える 2 数は互いに素でなければならない。
高橋君は最終的な並びが辞書順最小となるように、青木君は最終的な並びが辞書順最大となるように最適に行動するとしたとき、 最終的な数列を求めてください。
制約
- 1 ≦ N ≦ 2000
- 1 ≦ A_i ≦ 10^8
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 … A_N
出力
最終的な数列を一行に出力せよ。
入力例 1
5 1 2 3 4 5
出力例 1
5 3 2 4 1
高橋君は与えられた数を (1,2,3,4,5) という順番で並べれば、青木君が最適に動かしても (5,3,2,4,1) となります。
入力例 2
4 2 3 4 6
出力例 2
2 4 6 3
Score : 1600 points
Problem Statement
There are N integers written on a blackboard. The i-th integer is A_i.
Takahashi and Aoki will arrange these integers in a row, as follows:
- First, Takahashi will arrange the integers as he wishes.
- Then, Aoki will repeatedly swap two adjacent integers that are coprime, as many times as he wishes.
We will assume that Takahashi acts optimally so that the eventual sequence will be lexicographically as small as possible, and we will also assume that Aoki acts optimally so that the eventual sequence will be lexicographically as large as possible. Find the eventual sequence that will be produced.
Constraints
- 1 ≦ N ≦ 2000
- 1 ≦ A_i ≦ 10^8
Input
The input is given from Standard Input in the following format:
N A_1 A_2 … A_N
Output
Print the eventual sequence that will be produced, in a line.
Sample Input 1
5 1 2 3 4 5
Sample Output 1
5 3 2 4 1
If Takahashi arranges the given integers in the order (1,2,3,4,5), they will become (5,3,2,4,1) after Aoki optimally manipulates them.
Sample Input 2
4 2 3 4 6
Sample Output 2
2 4 6 3
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1600 点
問題文
N 頂点からなる木があり、頂点には 1 から N の番号がついています。 また、N-1 本の辺の内、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。
今、各頂点 i には A_i 個の石が置いてあります。 高橋君と青木君はこの木を使ってゲームをすることにしました。
まず、高橋君が一つの頂点を選び、そこに駒を置きます。 その後、高橋君から始めて以下の操作を交互に繰り返します。
- 今、駒がおいてある頂点から石を一つ取り除く。
- その後、その頂点に隣接する頂点を一つ選び、そこに駒を動かす。
駒が置いてある頂点に石がなく、操作を行えない人が負けです。 高橋君がこのゲームに勝つために、最初に駒を置くことができる頂点をすべて求めてください。
制約
- 2 ≦ N ≦ 3000
- 1 ≦ a_i,b_i ≦ N
- 0 ≦ A_i ≦ 10^9
- 与えられるグラフは木である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 … A_N
a_1 b_1
:
a_{N-1} b_{N-1}
出力
高橋君が最初に駒を置いて勝つことができる頂点の番号を昇順に一行に出力せよ。
入力例 1
3 1 2 3 1 2 2 3
出力例 1
2
高橋君が頂点 2 に駒を置いたとき、例えば以下のようにゲームが進みます。
- 高橋君が駒を頂点 1 に動かす。このとき、各頂点にある石の個数は (1,1,3) である。
- 青木君が駒を頂点 2 に動かす。このとき、各頂点にある石の個数は (0,1,3) である。
- 高橋君が駒を頂点 1 に動かす。このとき、各頂点にある石の個数は (0,0,3) である。
- 青木君が石を取れないため、高橋君の勝ちとなる。
入力例 2
5 5 4 1 2 3 1 2 1 3 2 4 2 5
出力例 2
1 2
入力例 3
3 1 1 1 1 2 2 3
出力例 3
題意を満たす頂点が存在しない場合があることに注意してください。
Score : 1600 points
Problem Statement
There is a tree with N vertices, numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.
Currently, there are A_i stones placed on vertex i. Takahashi and Aoki will play a game using this tree.
First, Takahashi will select a vertex and place a piece on it. Then, starting from Takahashi, they will alternately perform the following operation:
- Remove one stone from the vertex currently occupied by the piece.
- Then, move the piece to a vertex that is adjacent to the currently occupied vertex.
The player who is left with no stone on the vertex occupied by the piece and thus cannot perform the operation, loses the game. Find all the vertices v such that Takahashi can place the piece on v at the beginning and win the game.
Constraints
- 2 ≦ N ≦ 3000
- 1 ≦ a_i,b_i ≦ N
- 0 ≦ A_i ≦ 10^9
- The given graph is a tree.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 … A_N
a_1 b_1
:
a_{N-1} b_{N-1}
Output
Print the indices of the vertices v such that Takahashi can place the piece on v at the beginning and win the game, in a line, in ascending order.
Sample Input 1
3 1 2 3 1 2 2 3
Sample Output 1
2
The following is one possible progress of the game when Takahashi places the piece on vertex 2:
- Takahashi moves the piece to vertex 1. The number of the stones on each vertex is now: (1,1,3).
- Aoki moves the piece to vertex 2. The number of the stones on each vertex is now: (0,1,3).
- Takahashi moves the piece to vertex 1. The number of the stones on each vertex is now: (0,0,3).
- Aoki cannot take a stone from the vertex, and thus Takahashi wins.
Sample Input 2
5 5 4 1 2 3 1 2 1 3 2 4 2 5
Sample Output 2
1 2
Sample Input 3
3 1 1 1 1 2 2 3
Sample Output 3
Note that the correct output may be an empty line.