実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
長さ N の数列 a = (a_1, a_2, ..., a_N) があります。 各 a_i は正の整数です。
すぬけ君の目標は、a の要素を自由に並べ替え、次の条件が成り立つようにすることです。
- 各 1 ≤ i ≤ N - 1 について、a_i と a_{i + 1} の積は 4 の倍数である。
すぬけ君が目標を達成できるか判定してください。
制約
- 2 ≤ N ≤ 10^5
- a_i は整数である。
- 1 ≤ a_i ≤ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
出力
すぬけ君が目標を達成できるならば Yes
を、できないならば No
を出力せよ。
入力例 1
3 1 10 100
出力例 1
Yes
例えば、(1, 100, 10) と並べ替えればよいです。
入力例 2
4 1 2 3 4
出力例 2
No
どのように並べ替えても、条件が成り立つようにできません。
入力例 3
3 1 4 1
出力例 3
Yes
最初から条件が成り立っています。
入力例 4
2 1 1
出力例 4
No
入力例 5
6 2 7 1 8 2 8
出力例 5
Yes
Score : 400 points
Problem Statement
We have a sequence of length N, a = (a_1, a_2, ..., a_N). Each a_i is a positive integer.
Snuke's objective is to permute the element in a so that the following condition is satisfied:
- For each 1 ≤ i ≤ N - 1, the product of a_i and a_{i + 1} is a multiple of 4.
Determine whether Snuke can achieve his objective.
Constraints
- 2 ≤ N ≤ 10^5
- a_i is an integer.
- 1 ≤ a_i ≤ 10^9
Input
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Output
If Snuke can achieve his objective, print Yes
; otherwise, print No
.
Sample Input 1
3 1 10 100
Sample Output 1
Yes
One solution is (1, 100, 10).
Sample Input 2
4 1 2 3 4
Sample Output 2
No
It is impossible to permute a so that the condition is satisfied.
Sample Input 3
3 1 4 1
Sample Output 3
Yes
The condition is already satisfied initially.
Sample Input 4
2 1 1
Sample Output 4
No
Sample Input 5
6 2 7 1 8 2 8
Sample Output 5
Yes
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
縦 H 行、横 W 列のマス目があります。 すぬけ君は、このマス目を色 1, 2, ..., N で塗り分けようとしています。 このとき、次の条件が成り立つようにします。
- 各 i (1 ≤ i ≤ N) について、色 i のマスはちょうど a_i 個存在する。 ただし、a_1 + a_2 + ... + a_N = H W である。
- 各 i (1 ≤ i ≤ N) について、色 i のマスは上下左右に連結である。 すなわち、どの色 i のマスからどの色 i のマスへも、上下左右に隣り合う色 i のマスのみを辿って行き来できる。
条件を満たす塗り分け方をひとつ求めてください。 解は必ず存在することが示せます。
制約
- 1 ≤ H, W ≤ 100
- 1 ≤ N ≤ H W
- a_i ≥ 1
- a_1 + a_2 + ... + a_N = H W
入力
入力は以下の形式で標準入力から与えられる。
H W N a_1 a_2 ... a_N
出力
条件を満たす塗り分け方をひとつ出力せよ。 塗り分け方は次のフォーマットで出力せよ。 ただし、c_{i j} は、上から i 行目、左から j 列目のマスの色である。
c_{1 1} ... c_{1 W} : c_{H 1} ... c_{H W}
入力例 1
2 2 3 2 1 1
出力例 1
1 1 2 3
例えば、次の塗り分け方は条件を満たしません。 色 1 のマスが上下左右に連結でないからです。
1 2 3 1
入力例 2
3 5 5 1 2 3 4 5
出力例 2
1 4 4 4 3 2 5 4 5 3 2 5 5 5 3
入力例 3
1 1 1 1
出力例 3
1
Score : 400 points
Problem Statement
We have a grid with H rows and W columns of squares. Snuke is painting these squares in colors 1, 2, ..., N. Here, the following conditions should be satisfied:
- For each i (1 ≤ i ≤ N), there are exactly a_i squares painted in Color i. Here, a_1 + a_2 + ... + a_N = H W.
- For each i (1 ≤ i ≤ N), the squares painted in Color i are 4-connected. That is, every square painted in Color i can be reached from every square painted in Color i by repeatedly traveling to a horizontally or vertically adjacent square painted in Color i.
Find a way to paint the squares so that the conditions are satisfied. It can be shown that a solution always exists.
Constraints
- 1 ≤ H, W ≤ 100
- 1 ≤ N ≤ H W
- a_i ≥ 1
- a_1 + a_2 + ... + a_N = H W
Input
Input is given from Standard Input in the following format:
H W N a_1 a_2 ... a_N
Output
Print one way to paint the squares that satisfies the conditions. Output in the following format:
c_{1 1} ... c_{1 W} : c_{H 1} ... c_{H W}
Here, c_{i j} is the color of the square at the i-th row from the top and j-th column from the left.
Sample Input 1
2 2 3 2 1 1
Sample Output 1
1 1 2 3
Below is an example of an invalid solution:
1 2 3 1
This is because the squares painted in Color 1 are not 4-connected.
Sample Input 2
3 5 5 1 2 3 4 5
Sample Output 2
1 4 4 4 3 2 5 4 5 3 2 5 5 5 3
Sample Input 3
1 1 1 1
Sample Output 3
1
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 800 点
問題文
N を正の偶数とします。
(1, 2, ..., N) の順列 p = (p_1, p_2, ..., p_N) があります。 すぬけ君は、次の手続きによって (1, 2, ..., N) の順列 q を作ろうとしています。
まず、空の数列 q を用意します。 p が空になるまで、次の操作を繰り返します。
- p の隣り合う 2 つの要素を選び、順に x, y とする。 x, y を p から取り除き (このとき、p は 2 だけ短くなる)、x, y をこの順のまま q の先頭へ追加する。
p が空になったとき、q は (1, 2, ..., N) の順列になっています。
辞書順で最小の q を求めてください。
制約
- N は偶数である。
- 2 ≤ N ≤ 2 × 10^5
- p は (1, 2, ..., N) の順列である。
入力
入力は以下の形式で標準入力から与えられる。
N p_1 p_2 ... p_N
出力
辞書順で最小の q を空白区切りで出力せよ。
入力例 1
4 3 2 4 1
出力例 1
3 1 2 4
次の順に操作を行えばよいです。
p | q |
---|---|
(3, 2, 4, 1) | () |
↓ | ↓ |
(3, 1) | (2, 4) |
↓ | ↓ |
() | (3, 1, 2, 4) |
入力例 2
2 1 2
出力例 2
1 2
入力例 3
8 4 6 3 2 8 5 7 1
出力例 3
3 1 2 7 4 6 8 5
次の順に操作を行えばよいです。
p | q |
---|---|
(4, 6, 3, 2, 8, 5, 7, 1) | () |
↓ | ↓ |
(4, 6, 3, 2, 7, 1) | (8, 5) |
↓ | ↓ |
(3, 2, 7, 1) | (4, 6, 8, 5) |
↓ | ↓ |
(3, 1) | (2, 7, 4, 6, 8, 5) |
↓ | ↓ |
() | (3, 1, 2, 7, 4, 6, 8, 5) |
Score : 800 points
Problem Statement
Let N be a positive even number.
We have a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Snuke is constructing another permutation of (1, 2, ..., N), q, following the procedure below.
First, let q be an empty sequence. Then, perform the following operation until p becomes empty:
- Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.
When p becomes empty, q will be a permutation of (1, 2, ..., N).
Find the lexicographically smallest permutation that can be obtained as q.
Constraints
- N is an even number.
- 2 ≤ N ≤ 2 × 10^5
- p is a permutation of (1, 2, ..., N).
Input
Input is given from Standard Input in the following format:
N p_1 p_2 ... p_N
Output
Print the lexicographically smallest permutation, with spaces in between.
Sample Input 1
4 3 2 4 1
Sample Output 1
3 1 2 4
The solution above is obtained as follows:
p | q |
---|---|
(3, 2, 4, 1) | () |
↓ | ↓ |
(3, 1) | (2, 4) |
↓ | ↓ |
() | (3, 1, 2, 4) |
Sample Input 2
2 1 2
Sample Output 2
1 2
Sample Input 3
8 4 6 3 2 8 5 7 1
Sample Output 3
3 1 2 7 4 6 8 5
The solution above is obtained as follows:
p | q |
---|---|
(4, 6, 3, 2, 8, 5, 7, 1) | () |
↓ | ↓ |
(4, 6, 3, 2, 7, 1) | (8, 5) |
↓ | ↓ |
(3, 2, 7, 1) | (4, 6, 8, 5) |
↓ | ↓ |
(3, 1) | (2, 7, 4, 6, 8, 5) |
↓ | ↓ |
() | (3, 1, 2, 7, 4, 6, 8, 5) |
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1200 点
問題文
無限枚のカードがあります。 カードには 1, 2, 3, ... と番号が振られています。 最初、カード x_1, x_2, ..., x_N は表向きで、それら以外のカードは裏向きです。
すぬけ君は次の操作を繰り返し行うことができます。
- 3 以上の素数 p を選ぶ。 番号が連続する p 枚のカードを選び、それらすべてをひっくり返す。
すぬけ君の目標は、すべてのカードを裏向きにすることです。 すぬけ君が目標を達成するために必要な操作回数の最小値を求めてください。
制約
- 1 ≤ N ≤ 100
- 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7
入力
入力は以下の形式で標準入力から与えられる。
N x_1 x_2 ... x_N
出力
すぬけ君が目標を達成するために必要な操作回数の最小値を出力せよ。
入力例 1
2 4 5
出力例 1
2
例えば、次の順に操作を行えばよいです。
- p = 5 を選び、カード 1, 2, 3, 4, 5 をひっくり返す。
- p = 3 を選び、カード 1, 2, 3 をひっくり返す。
入力例 2
9 1 2 3 4 5 6 7 8 9
出力例 2
3
例えば、次の順に操作を行えばよいです。
- p = 3 を選び、カード 1, 2, 3 をひっくり返す。
- p = 3 を選び、カード 4, 5, 6 をひっくり返す。
- p = 3 を選び、カード 7, 8, 9 をひっくり返す。
入力例 3
2 1 10000000
出力例 3
4
Score : 1200 points
Problem Statement
There are infinitely many cards, numbered 1, 2, 3, ... Initially, Cards x_1, x_2, ..., x_N are face up, and the others are face down.
Snuke can perform the following operation repeatedly:
- Select a prime p greater than or equal to 3. Then, select p consecutive cards and flip all of them.
Snuke's objective is to have all the cards face down. Find the minimum number of operations required to achieve the objective.
Constraints
- 1 ≤ N ≤ 100
- 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7
Input
Input is given from Standard Input in the following format:
N x_1 x_2 ... x_N
Output
Print the minimum number of operations required to achieve the objective.
Sample Input 1
2 4 5
Sample Output 1
2
Below is one way to achieve the objective in two operations:
- Select p = 5 and flip Cards 1, 2, 3, 4 and 5.
- Select p = 3 and flip Cards 1, 2 and 3.
Sample Input 2
9 1 2 3 4 5 6 7 8 9
Sample Output 2
3
Below is one way to achieve the objective in three operations:
- Select p = 3 and flip Cards 1, 2 and 3.
- Select p = 3 and flip Cards 4, 5 and 6.
- Select p = 3 and flip Cards 7, 8 and 9.
Sample Input 3
2 1 10000000
Sample Output 3
4