実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
1 以上 3 以下の整数 A, B が与えられます。
A \times B \times C が奇数となるような 1 以上 3 以下の整数 C が存在するか判定してください。
制約
- 入力はすべて整数である
- 1 \leq A, B \leq 3
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
条件を満たすような C が存在するなら Yes、そうでないなら No を出力せよ。
入力例 1
3 1
出力例 1
Yes
C = 3 とすると A \times B \times C = 3 \times 1 \times 3 = 9 となり、奇数となります。
入力例 2
1 2
出力例 2
No
入力例 3
2 2
出力例 3
No
Score : 100 points
Problem Statement
You are given integers A and B, each between 1 and 3 (inclusive).
Determine if there is an integer C between 1 and 3 (inclusive) such that A \times B \times C is an odd number.
Constraints
- All values in input are integers.
- 1 \leq A, B \leq 3
Input
Input is given from Standard Input in the following format:
A B
Output
If there is an integer C between 1 and 3 that satisfies the condition, print Yes; otherwise, print No.
Sample Input 1
3 1
Sample Output 1
Yes
Let C = 3. Then, A \times B \times C = 3 \times 1 \times 3 = 9, which is an odd number.
Sample Input 2
1 2
Sample Output 2
No
Sample Input 3
2 2
Sample Output 3
No
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
高橋くんは今日も 1 人でしりとりの練習をしています。
しりとりとは以下のルールで遊ばれるゲームです。
- はじめ、好きな単語を発言する
- 以降、次の条件を満たす単語を発言することを繰り返す
- その単語はまだ発言していない単語である
- その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する
高橋くんは、10 秒間にできるだけ多くの単語を発言する練習をしています。
高橋くんが発言した単語の個数 N と i 番目に発言した単語 W_i が与えられるので、どの発言もしりとりのルールを守っていたかを判定してください。
制約
- N は 2 \leq N \leq 100 を満たす整数である
- W_i は英小文字からなる長さ 1 以上 10 以下の文字列である
入力
入力は以下の形式で標準入力から与えられる。
N W_1 W_2 : W_N
出力
高橋くんのどの発言もしりとりのルールを守っていたなら Yes、そうでなければ No を出力せよ。
入力例 1
4 hoge english hoge enigma
出力例 1
No
hoge が複数回発言されているのでしりとりのルールを守っていません。
入力例 2
9 basic c cpp php python nadesico ocaml lua assembly
出力例 2
Yes
入力例 3
8 a aa aaa aaaa aaaaa aaaaaa aaa aaaaaaa
出力例 3
No
入力例 4
3 abc arc agc
出力例 4
No
Score : 200 points
Problem Statement
Takahashi is practicing shiritori alone again today.
Shiritori is a game as follows:
- In the first turn, a player announces any one word.
- In the subsequent turns, a player announces a word that satisfies the following conditions:
- That word is not announced before.
- The first character of that word is the same as the last character of the last word announced.
In this game, he is practicing to announce as many words as possible in ten seconds.
You are given the number of words Takahashi announced, N, and the i-th word he announced, W_i, for each i. Determine if the rules of shiritori was observed, that is, every word announced by him satisfied the conditions.
Constraints
- N is an integer satisfying 2 \leq N \leq 100.
- W_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
N W_1 W_2 : W_N
Output
If every word announced by Takahashi satisfied the conditions, print Yes; otherwise, print No.
Sample Input 1
4 hoge english hoge enigma
Sample Output 1
No
As hoge is announced multiple times, the rules of shiritori was not observed.
Sample Input 2
9 basic c cpp php python nadesico ocaml lua assembly
Sample Output 2
Yes
Sample Input 3
8 a aa aaa aaaa aaaaa aaaaaa aaa aaaaaaa
Sample Output 3
No
Sample Input 4
3 abc arc agc
Sample Output 4
No
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
数直線上に N 個の都市があり、i 番目の都市は座標 x_i にあります。
あなたの目的は、これら全ての都市を 1 度以上訪れることです。
あなたは、はじめに正整数 D を設定します。
その後、あなたは座標 X から出発し、以下の移動 1、移動 2 を好きなだけ行います。
- 移動 1: 座標 y から座標 y + D に移動する
- 移動 2: 座標 y から座標 y - D に移動する
全ての都市を 1 度以上訪れることのできる D の最大値を求めてください。
ここで、都市を訪れるとは、その都市のある座標に移動することです。
制約
- 入力はすべて整数である
- 1 \leq N \leq 10^5
- 1 \leq X \leq 10^9
- 1 \leq x_i \leq 10^9
- x_i はすべて異なる
- x_1, x_2, ..., x_N \neq X
入力
入力は以下の形式で標準入力から与えられる。
N X x_1 x_2 ... x_N
出力
全ての都市を 1 度以上訪れることのできる D の最大値を出力せよ。
入力例 1
3 3 1 7 11
出力例 1
2
D = 2 と設定すれば次のように移動を行うことですべての都市を訪れることができ、これが最大です。
- 移動 2 を行い、座標 1 に移動する
- 移動 1 を行い、座標 3 に移動する
- 移動 1 を行い、座標 5 に移動する
- 移動 1 を行い、座標 7 に移動する
- 移動 1 を行い、座標 9 に移動する
- 移動 1 を行い、座標 11 に移動する
入力例 2
3 81 33 105 57
出力例 2
24
入力例 3
1 1 1000000000
出力例 3
999999999
Score : 300 points
Problem Statement
There are N cities on a number line. The i-th city is located at coordinate x_i.
Your objective is to visit all these cities at least once.
In order to do so, you will first set a positive integer D.
Then, you will depart from coordinate X and perform Move 1 and Move 2 below, as many times as you like:
- Move 1: travel from coordinate y to coordinate y + D.
- Move 2: travel from coordinate y to coordinate y - D.
Find the maximum value of D that enables you to visit all the cities.
Here, to visit a city is to travel to the coordinate where that city is located.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq X \leq 10^9
- 1 \leq x_i \leq 10^9
- x_i are all different.
- x_1, x_2, ..., x_N \neq X
Input
Input is given from Standard Input in the following format:
N X x_1 x_2 ... x_N
Output
Print the maximum value of D that enables you to visit all the cities.
Sample Input 1
3 3 1 7 11
Sample Output 1
2
Setting D = 2 enables you to visit all the cities as follows, and this is the maximum value of such D.
- Perform Move 2 to travel to coordinate 1.
- Perform Move 1 to travel to coordinate 3.
- Perform Move 1 to travel to coordinate 5.
- Perform Move 1 to travel to coordinate 7.
- Perform Move 1 to travel to coordinate 9.
- Perform Move 1 to travel to coordinate 11.
Sample Input 2
3 81 33 105 57
Sample Output 2
24
Sample Input 3
1 1 1000000000
Sample Output 3
999999999
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
縦 H 行横 W 列に区切られたマス目があり、上から i 番目、左から j 列目のマスをマス (i, j) と呼びます。
マス (i, j) には a_{ij} 枚のコインが置かれています。
あなたは以下の操作を何度でも行うことができます。
操作: まだ選んだことのないマスのうち 1 枚以上のコインが置かれているマスを 1 つ選び、そのマスに置かれているコインのうち 1 枚を上下左右に隣接するいずれかのマスに移動する
偶数枚のコインが置かれたマスの数を最大化してください。
制約
- 入力はすべて整数である
- 1 \leq H, W \leq 500
- 0 \leq a_{ij} \leq 9
入力
入力は以下の形式で標準入力から与えられる。
H W
a_{11} a_{12} ... a_{1W}
a_{21} a_{22} ... a_{2W}
:
a_{H1} a_{H2} ... a_{HW}
出力
偶数枚のコインが置かれたマスの数が最大となるような操作の列を次の形式で出力せよ。
N y_1 x_1 y_1' x_1' y_2 x_2 y_2' x_2' : y_N x_N y_N' x_N'
すなわち、1 行目には操作の回数を表す 0 以上 H \times W 以下の整数 N を出力せよ。
i+1 (1 \leq i \leq N) 行目には i 回目の操作を表す整数 y_i, x_i, y_i', x_i' (1 \leq y_i, y_i' \leq H かつ 1 \leq x_i, x_i' \leq W) を出力せよ。 ただし、これはマス (y_i, x_i) にあるコインのうち 1 枚を上下左右に隣接するマス (y_i', x_i') に移動させる操作を表す。
問題文中の操作でないような操作が与えられた場合や、出力の形式が正しくない場合には Wrong Answer となるので注意せよ。
入力例 1
2 3 1 2 3 0 1 1
出力例 1
3 2 2 2 3 1 1 1 2 1 3 1 2
次のように操作を行えば、全てのマスに置かれたコインの数を偶数にできます。
- マス (2, 2) に置かれているコインのうち 1 枚をマス (2, 3) に移動します
- マス (1, 1) に置かれているコインのうち 1 枚をマス (1, 2) に移動します
- マス (1, 3) に置かれているコインのうち 1 枚をマス (1, 2) に移動します
入力例 2
3 2 1 0 2 1 1 0
出力例 2
3 1 1 1 2 1 2 2 2 3 1 3 2
入力例 3
1 5 9 9 9 9 9
出力例 3
2 1 1 1 2 1 3 1 4
Score : 400 points
Problem Statement
There is a grid of square cells with H horizontal rows and W vertical columns. The cell at the i-th row and the j-th column will be denoted as Cell (i, j).
In Cell (i, j), a_{ij} coins are placed.
You can perform the following operation any number of times:
Operation: Choose a cell that was not chosen before and contains one or more coins, then move one of those coins to a vertically or horizontally adjacent cell.
Maximize the number of cells containing an even number of coins.
Constraints
- All values in input are integers.
- 1 \leq H, W \leq 500
- 0 \leq a_{ij} \leq 9
Input
Input is given from Standard Input in the following format:
H W
a_{11} a_{12} ... a_{1W}
a_{21} a_{22} ... a_{2W}
:
a_{H1} a_{H2} ... a_{HW}
Output
Print a sequence of operations that maximizes the number of cells containing an even number of coins, in the following format:
N y_1 x_1 y_1' x_1' y_2 x_2 y_2' x_2' : y_N x_N y_N' x_N'
That is, in the first line, print an integer N between 0 and H \times W (inclusive), representing the number of operations.
In the (i+1)-th line (1 \leq i \leq N), print four integers y_i, x_i, y_i' and x_i' (1 \leq y_i, y_i' \leq H and 1 \leq x_i, x_i' \leq W), representing the i-th operation. These four integers represents the operation of moving one of the coins placed in Cell (y_i, x_i) to a vertically or horizontally adjacent cell, (y_i', x_i').
Note that if the specified operation violates the specification in the problem statement or the output format is invalid, it will result in Wrong Answer.
Sample Input 1
2 3 1 2 3 0 1 1
Sample Output 1
3 2 2 2 3 1 1 1 2 1 3 1 2
Every cell contains an even number of coins after the following sequence of operations:
- Move the coin in Cell (2, 2) to Cell (2, 3).
- Move the coin in Cell (1, 1) to Cell (1, 2).
- Move one of the coins in Cell (1, 3) to Cell (1, 2).
Sample Input 2
3 2 1 0 2 1 1 0
Sample Output 2
3 1 1 1 2 1 2 2 2 3 1 3 2
Sample Input 3
1 5 9 9 9 9 9
Sample Output 3
2 1 1 1 2 1 3 1 4