AtCoder Beginner Contest 111

A - AtCoder Beginner Contest 999

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

問題文

猫のすぬけは文字を書く練習をしています。すぬけは今日、数字の 1 と 9 を書く練習をしていたのですが、間違えて 1 と 9 をあべこべに書いてしまいました。

すぬけが書いた 3 桁の整数 n が与えられます。 n に含まれる 1 という桁をそれぞれ 9 に、 9 という桁をそれぞれ 1 に置き換えて得られる整数を出力してください。

制約

111 \leq n \leq 999
n は各桁が 1 か 9 である整数

入力

入力は以下の形式で標準入力から与えられる。

出力

n の各桁の 1 と 9 を入れ替えた整数を出力してください。

入力例 1

出力例 1

一の位の 9 を 1 に、十の位の 1 を 9 に、百の位の 1 を 9 に書き換えた 991 が答えとなります．

入力例 2

出力例 2

Score : 100 points

Problem Statement

Cat Snuke is learning to write characters. Today, he practiced writing digits 1 and 9, but he did it the other way around.

You are given a three-digit integer n written by Snuke. Print the integer obtained by replacing each digit 1 with 9 and each digit 9 with 1 in n.

Constraints

111 \leq n \leq 999
n is an integer consisting of digits 1 and 9.

Input

Input is given from Standard Input in the following format:

Output

Print the integer obtained by replacing each occurrence of 1 with 9 and each occurrence of 9 with 1 in n.

Sample Input 1

Sample Output 1

Replace the 9 in the ones place with 1, the 1 in the tens place with 9 and the 1 in the hundreds place with 9. The answer is 991.

Sample Input 2

Sample Output 2

B - AtCoder Beginner Contest 111

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200 点

問題文

黒橋君は，AtCoder Beginner Contest (ABC) にまだ参加したことがありません．

次に行われる ABC は第 N 回です．黒橋君は，初めて参加する ABC を第 x 回としたときに，x の十進法表記でのすべての桁の数字が同じであるようにしたいです．

黒橋君が初めて参加する ABC としてふさわしいもののうち，最も早いものは第何回でしょうか？

制約

100 \leq N \leq 999
N は整数

入力

入力は以下の形式で標準入力から与えられる．

出力

黒橋君が初めて参加する ABC としてふさわしいもののうち，最も早いものは第何回かを出力せよ．

入力例 1

出力例 1

次に行われる ABC は第 111 回です．これは黒橋君が初めて参加する ABC としてふさわしいです．

入力例 2

出力例 2

次に行われる ABC は第 112 回です．そのため，第 111 回の ABC にはもう参加することはできません．黒橋君が初めて参加する ABC としてふさわしいもののうち，最も早いものは第 222 回です．

入力例 3

出力例 3

Score : 200 points

Problem Statement

Kurohashi has never participated in AtCoder Beginner Contest (ABC).

The next ABC to be held is ABC N (the N-th ABC ever held). Kurohashi wants to make his debut in some ABC x such that all the digits of x in base ten are the same.

What is the earliest ABC where Kurohashi can make his debut?

Constraints

100 \leq N \leq 999
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

If the earliest ABC where Kurohashi can make his debut is ABC n, print n.

Sample Input 1

Sample Output 1

The next ABC to be held is ABC 111, where Kurohashi can make his debut.

Sample Input 2

Sample Output 2

The next ABC to be held is ABC 112, which means Kurohashi can no longer participate in ABC 111. Among the ABCs where Kurohashi can make his debut, the earliest one is ABC 222.

Sample Input 3

Sample Output 3

C - /\/\/\/

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

数列 a_1,a_2,... ,a_n が以下の条件を満たすとき、 /\/\/\/ と呼ぶことにします。

各 i = 1,2,..., n-2 について、a_i = a_{i+2}
数列に現れる数はちょうど 2 種類

偶数長の数列 v_1,v_2,...,v_n が与えられます。要素をいくつか書き換えることでこの数列を /\/\/\/ にしたいです。書き換える要素の数は最小でいくつになるか求めてください。

制約

2 \leq n \leq 10^5
n は偶数
1 \leq v_i \leq 10^5
v_i は整数

入力

入力は以下の形式で標準入力から与えられる。

n
v_1 v_2 ... v_n

出力

書き換える要素数の最小値を出力してください。

入力例 1

4
3 1 3 2

出力例 1

数列 3,1,3,2 は /\/\/\/ ではありませんが、1 要素書き換えることで /\/\/\/ にすることができます。例えば、4 要素目を書き換えて 3,1,3,1 とすればよいです。

入力例 2

6
105 119 105 119 105 119

出力例 2

数列 105,119,105,119,105,119 は /\/\/\/ です。

入力例 3

4
1 1 1 1

出力例 3

数列 1,1,1,1 は 1 種類の数からなる数列であるため、 /\/\/\/ ではありません。

Score : 300 points

Problem Statement

A sequence a_1,a_2,... ,a_n is said to be /\/\/\/ when the following conditions are satisfied:

For each i = 1,2,..., n-2, a_i = a_{i+2}.
Exactly two different numbers appear in the sequence.

You are given a sequence v_1,v_2,...,v_n whose length is even. We would like to make this sequence /\/\/\/ by replacing some of its elements. Find the minimum number of elements that needs to be replaced.

Constraints

2 \leq n \leq 10^5
n is even.
1 \leq v_i \leq 10^5
v_i is an integer.

Input

Input is given from Standard Input in the following format:

n
v_1 v_2 ... v_n

Output

Print the minimum number of elements that needs to be replaced.

Sample Input 1

4
3 1 3 2

Sample Output 1

The sequence 3,1,3,2 is not /\/\/\/, but we can make it /\/\/\/ by replacing one of its elements: for example, replace the fourth element to make it 3,1,3,1.

Sample Input 2

6
105 119 105 119 105 119

Sample Output 2

The sequence 105,119,105,119,105,119 is /\/\/\/.

Sample Input 3

4
1 1 1 1

Sample Output 3

The elements of the sequence 1,1,1,1 are all the same, so it is not /\/\/\/.

D - Robot Arms

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

すぬけ君の工場では，次のような特徴を持つ ロボットアーム を導入することになりました：

ロボットアームは，m 個の腕と m+1 個の関節からなる．腕には 1, 2, ..., m で，関節には 0, 1, ..., m で番号が付けられている．腕 i は関節 i-1 と関節 i をつなぐ．腕 i の長さは d_i である．
各腕には，それぞれ独立に モード を指定することができる．モードは L, R, D, U のいずれかであり，腕のモードはその腕の向きを指定する．工場を座標平面とみなすと，関節 i の座標 (x_i, y_i) は次のように定まる：
- (x_0, y_0) = (0, 0)．
- 腕 i のモードが L のとき，(x_i, y_i) = (x_{i-1} - d_{i}, y_{i-1})．
- 腕 i のモードが R のとき，(x_i, y_i) = (x_{i-1} + d_{i}, y_{i-1})．
- 腕 i のモードが D のとき，(x_i, y_i) = (x_{i-1}, y_{i-1} - d_{i})．
- 腕 i のモードが U のとき，(x_i, y_i) = (x_{i-1}, y_{i-1} + d_{i})．

すぬけ君は，腕のモードをうまく指定することにより，N 個の点 (X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N) のいずれにもロボットアームの関節 m をちょうど一致させられるようなロボットアームを導入したいです．このようなことは可能でしょうか？可能ならば，条件を満たすロボットアームおよび，各点 (X_j, Y_j) にそのロボットアームの関節 m を到達させるためのモードの指定方法を求めてください．

制約

入力はすべて整数である
1 \leq N \leq 1000
-10^9 \leq X_i \leq 10^9
-10^9 \leq Y_i \leq 10^9

部分点

300 点分のテストケースでは，-10 \leq X_i \leq 10 および -10 \leq Y_i \leq 10 が成り立つ．

入力

入力は以下の形式で標準入力から与えられる．

N
X_1 Y_1
X_2 Y_2
:
X_N Y_N

出力

条件を満たすことが可能なら，次の形式で出力せよ．不可能な場合は -1 を出力せよ．

m
d_1 d_2 ... d_m
w_1
w_2
:
w_N

m および d_i はロボットアームの情報を表す．それぞれの変数の意味は問題文を参照せよ．ここで，1 \leq m \leq 40, 1 \leq d_i \leq 10^{12} かつ m, d_i はすべて整数でなければならない．

w_j は m 文字からなる文字列であり，点 (X_j, Y_j) にロボットアームの関節 m を到達させる方法を表す． w_j の i 文字目は L, R, D, U のいずれかの文字であり，腕 i のモードを表す．

入力例 1

出力例 1

2
1 2
RL
UU
DR

それぞれの (X_j, Y_j) にロボットアームの関節 m を到達させる方法において，各関節の位置は次のようになります．

(X_1, Y_1) = (-1, 0) に到達させる方法では，まず関節 0 の位置は (x_0, y_0) = (0, 0) です．腕 1 のモードが R なので，関節 1 の位置は (x_1, y_1) = (1, 0) です．腕 2 のモードが L なので，関節 m=2 の位置は (x_2, y_2) = (-1, 0) です．
(X_2, Y_2) = (0, 3) に到達させる方法では，(x_0, y_0) = (0, 0), (x_1, y_1) = (0, 1), (x_2, y_2) = (0, 3) です．
(X_3, Y_3) = (2, -1) に到達させる方法では，(x_0, y_0) = (0, 0), (x_1, y_1) = (0, -1), (x_2, y_2) = (2, -1) です．

入力例 2

出力例 2

-1

入力例 3

2
1 1
1 1

出力例 3

2
1 1
RU
UR

(X_j, Y_j) の中に同じ点が含まれることもあります．

入力例 4

3
-7 -3
7 3
-3 -7

出力例 4

5
3 1 4 1 5
LRDUL
RDULR
DULRD

Score : 600 points

Problem Statement

Snuke is introducing a robot arm with the following properties to his factory:

The robot arm consists of m sections and m+1 joints. The sections are numbered 1, 2, ..., m, and the joints are numbered 0, 1, ..., m. Section i connects Joint i-1 and Joint i. The length of Section i is d_i.
For each section, its mode can be specified individually. There are four modes: L, R, D and U. The mode of a section decides the direction of that section. If we consider the factory as a coordinate plane, the position of Joint i will be determined as follows (we denote its coordinates as (x_i, y_i)):
- (x_0, y_0) = (0, 0).
- If the mode of Section i is L, (x_{i}, y_{i}) = (x_{i-1} - d_{i}, y_{i-1}).
- If the mode of Section i is R, (x_{i}, y_{i}) = (x_{i-1} + d_{i}, y_{i-1}).
- If the mode of Section i is D, (x_{i}, y_{i}) = (x_{i-1}, y_{i-1} - d_{i}).
- If the mode of Section i is U, (x_{i}, y_{i}) = (x_{i-1}, y_{i-1} + d_{i}).

Snuke would like to introduce a robot arm so that the position of Joint m can be matched with all of the N points (X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N) by properly specifying the modes of the sections. Is this possible? If so, find such a robot arm and how to bring Joint m to each point (X_j, Y_j).

Constraints

All values in input are integers.
1 \leq N \leq 1000
-10^9 \leq X_i \leq 10^9
-10^9 \leq Y_i \leq 10^9

Partial Score

In the test cases worth 300 points, -10 \leq X_i \leq 10 and -10 \leq Y_i \leq 10 hold.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
:
X_N Y_N

Output

If the condition can be satisfied, follow the following format. If the condition cannot be satisfied, print -1.

m
d_1 d_2 ... d_m
w_1
w_2
:
w_N

m and d_i are the configurations of the robot arm. Refer to the problem statement for what each of them means. Here, 1 \leq m \leq 40 and 1 \leq d_i \leq 10^{12} must hold. Also, m and d_i must all be integers.

w_j is a string of length m that represents the way to bring Joint m of the robot arm to point (X_j, Y_j). The i-th character of w_j should be one of the letters L, R, D and U, representing the mode of Section i.

Sample Input 1

Sample Output 1

2
1 2
RL
UU
DR

In the given way to bring Joint m of the robot arm to each (X_j, Y_j), the positions of the joints will be as follows:

To (X_1, Y_1) = (-1, 0): First, the position of Joint 0 is (x_0, y_0) = (0, 0). As the mode of Section 1 is R, the position of Joint 1 is (x_1, y_1) = (1, 0). Then, as the mode of Section 2 is L, the position of Joint 2 is (x_2, y_2) = (-1, 0).
To (X_2, Y_2) = (0, 3): (x_0, y_0) = (0, 0), (x_1, y_1) = (0, 1), (x_2, y_2) = (0, 3).
To (X_3, Y_3) = (2, -1): (x_0, y_0) = (0, 0), (x_1, y_1) = (0, -1), (x_2, y_2) = (2, -1).

Sample Input 2

Sample Output 2

-1

Sample Input 3

2
1 1
1 1

Sample Output 3

2
1 1
RU
UR

There may be duplicated points among (X_j, Y_j).

Sample Input 4

3
-7 -3
7 3
-3 -7

Sample Output 4

5
3 1 4 1 5
LRDUL
RDULR
DULRD