実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
6 桁の正整数 N が与えられます。
この整数が以下の条件を全て満たすか判定してください。
- N の各桁のうち、 1 は丁度 1 つである。
- N の各桁のうち、 2 は丁度 2 つである。
- N の各桁のうち、 3 は丁度 3 つである。
制約
- N は 100000 \le N \le 999999 を満たす整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N が問題文中の条件を全て満たすなら Yes 、そうでないなら No と 1 行に出力せよ。
入力例 1
123233
出力例 1
Yes
123233 は問題文中の条件を満たすので、 Yes と出力します。
入力例 2
123234
出力例 2
No
123234 は問題文中の条件を満たさないので、 No と出力します。
入力例 3
323132
出力例 3
Yes
入力例 4
500000
出力例 4
No
Score : 100 points
Problem Statement
You are given a 6-digit positive integer N.
Determine whether N satisfies all of the following conditions.
- Among the digits of N, the digit 1 appears exactly once.
- Among the digits of N, the digit 2 appears exactly twice.
- Among the digits of N, the digit 3 appears exactly three times.
Constraints
- N is an integer satisfying 100000 \le N \le 999999.
Input
The input is given from Standard Input in the following format:
N
Output
Print Yes if N satisfies all the conditions described in the problem statement, and No otherwise, in one line.
Sample Input 1
123233
Sample Output 1
Yes
123233 satisfies the conditions in the problem statement, so print Yes.
Sample Input 2
123234
Sample Output 2
No
123234 does not satisfy the conditions in the problem statement, so print No.
Sample Input 3
323132
Sample Output 3
Yes
Sample Input 4
500000
Sample Output 4
No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
1 以上 9 以下の整数 N が入力として与えられます。
数字 N を N 個繋げて得られる文字列を出力してください。
制約
- N は 1 以上 9 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
333
3 を 3 個繋げて得られる文字列は 333 です。
入力例 2
9
出力例 2
999999999
Score : 100 points
Problem Statement
You are given an integer N between 1 and 9, inclusive, as input.
Concatenate N copies of the digit N and print the resulting string.
Constraints
- N is an integer between 1 and 9, inclusive.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
333
Concatenate three copies of the digit 3 to yield the string 333.
Sample Input 2
9
Sample Output 2
999999999
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
長さ N の正整数列 a = (a_1, a_2, \dots, a_N) には何種類の整数が現れますか？
制約
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
6 1 4 1 2 2 1
出力例 1
3
1, 2, 4 の 3 種類の整数が現れます。
入力例 2
1 1
出力例 2
1
入力例 3
11 3 1 4 1 5 9 2 6 5 3 5
出力例 3
7
Score : 200 points
Problem Statement
In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?
Constraints
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
6 1 4 1 2 2 1
Sample Output 1
3
There are three different integers: 1, 2, 4.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
11 3 1 4 1 5 9 2 6 5 3 5
Sample Output 3
7
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
縦 N 行 横 N 列からなる 2 つのグリッド S,T があります。グリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表します。
グリッド S,T の各マスは白または黒のいずれかに塗られています。S_{i,j} が . のとき S のマス (i,j) は白く、S_{i,j} が # のとき S のマス (i,j) は黒く塗られています。T についても同様です。
次の 2 種類の操作を好きな順序で好きな回数行うとき、グリッド S をグリッド T と一致させるために必要な操作回数の最小値を求めてください。
- グリッド S のマスを 1 つ選び、色を変更する
- グリッド S 全体を 90 度右に回転する
制約
- 1\leq N \leq 100
- N は整数
- S_{i,j},T_{i,j} は
.または#
入力
入力は以下の形式で標準入力から与えられる。
N
S_{1,1}S_{1,2}\dots S_{1,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,N}
\vdots
T_{N,1}T_{N,2}\dots T_{N,N}
出力
答えを出力せよ。
入力例 1
4 ###. ..#. ..#. ..#. ...# ...# ###. ....
出力例 1
2
下図のようにして 2 回の操作で S を T と一致させることができます。
入力例 2
13 .#..###..##.. #.#.#..#.#.#. #.#.###..#... ###.#..#.#.#. #.#.###..##.. ............. ..#...#....#. .##..#.#..##. #.#..#.#.#.#. ####.#.#.#### ..#..#.#...#. ..#...#....#. ............. ............. .#....#...#.. .#...#.#..#.. ####.#.#.#### .#.#.###..#.# .##....#..##. .#....#...#.. ............. ..##..###.#.# .#.#.#..#.### .#.#..###.#.# .#.#.#..#.#.# ..##..###..#.
出力例 2
5
Score : 250 points
Problem Statement
There are two grids S and T, each with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.
Each cell of grids S and T is colored either white or black. Cell (i,j) of S is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies to T.
You may perform the following two types of operations any number of times in any order. Find the minimum number of operations required to make grid S identical to grid T.
- Choose one cell of grid S and change its color.
- Rotate the entire grid S 90 degrees clockwise.
Constraints
- 1 \le N \le 100
- N is an integer.
- Each of S_{i,j} and T_{i,j} is
.or#.
Input
The input is given from Standard Input in the following format:
N
S_{1,1}S_{1,2}\dots S_{1,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,N}
\vdots
T_{N,1}T_{N,2}\dots T_{N,N}
Output
Output the minimum number of operations required.
Sample Input 1
4 ###. ..#. ..#. ..#. ...# ...# ###. ....
Sample Output 1
2
You can match S to T in two operations as shown below.
Sample Input 2
13 .#..###..##.. #.#.#..#.#.#. #.#.###..#... ###.#..#.#.#. #.#.###..##.. ............. ..#...#....#. .##..#.#..##. #.#..#.#.#.#. ####.#.#.#### ..#..#.#...#. ..#...#....#. ............. ............. .#....#...#.. .#...#.#..#.. ####.#.#.#### .#.#.###..#.# .##....#..##. .#....#...#.. ............. ..##..###.#.# .#.#.#..#.### .#.#..###.#.# .#.#.#..#.#.# ..##..###..#.
Sample Output 2
5
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 人の巨人がいます。巨人にはそれぞれ 1, 2, \ldots, N の名前がついており、巨人 i が地面に立ったとき、肩の高さは A_i、頭の高さは B_i となります。
あなたは (1, 2, \ldots, N) を並べ替えて得られる数列 (P_1, P_2, \ldots, P_N) を選び、以下の規則に従って N 人の巨人を積み上げることができます。
-
まず地面に巨人 P_1 を立たせる。巨人 P_1 の肩は地面を基準として A_{P_1}、頭は地面を基準として B_{P_1} の高さとなる。
-
i = 1, 2, \ldots, N - 1 の順に巨人 P_i の肩の上に巨人 P_{i + 1} を立たせる。巨人 P_i の肩が地面を基準として高さ t のとき、巨人 P_{i + 1} の肩は地面を基準として t + A_{P_{i + 1}}、頭は地面を基準として t + B_{P_{i + 1}} の高さとなる。
一番上に立っている巨人、すなわち巨人 P_N の地面を基準とした頭の高さとして実現できる最大値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
3 4 10 5 8 2 9
出力例 1
18
(P_1, P_2, P_3) = (2, 1, 3) とすると、地面を基準として巨人 2 は肩の高さが 5、頭の高さが 8、巨人 1 は肩の高さが 9、頭の高さが 15、巨人 3 は肩の高さが 11、頭の高さが 18 となります。
一番上に立っている巨人の頭の高さが地面を基準として 18 より大きくなることはないため 18 を出力します。
入力例 2
5 1 1 1 1 1 1 1 1 1 1
出力例 2
5
入力例 3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
出力例 3
7362669937
Score: 300 points
Problem Statement
There are N giants, named 1 to N. When giant i stands on the ground, their shoulder height is A_i, and their head height is B_i.
You can choose a permutation (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) and stack the N giants according to the following rules:
-
First, place giant P_1 on the ground. The giant P_1's shoulder will be at a height of A_{P_1} from the ground, and their head will be at a height of B_{P_1} from the ground.
-
For i = 1, 2, \ldots, N - 1 in order, place giant P_{i + 1} on the shoulders of giant P_i. If giant P_i's shoulders are at a height of t from the ground, then giant P_{i + 1}'s shoulders will be at a height of t + A_{P_{i + 1}} from the ground, and their head will be at a height of t + B_{P_{i + 1}} from the ground.
Find the maximum possible height of the head of the topmost giant P_N from the ground.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the answer.
Sample Input 1
3 4 10 5 8 2 9
Sample Output 1
18
If (P_1, P_2, P_3) = (2, 1, 3), then measuring from the ground, giant 2 has a shoulder height of 5 and a head height of 8, giant 1 has a shoulder height of 9 and a head height of 15, and giant 3 has a shoulder height of 11 and a head height of 18.
The head height of the topmost giant from the ground cannot be greater than 18, so print 18.
Sample Input 2
5 1 1 1 1 1 1 1 1 1 1
Sample Output 2
5
Sample Input 3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
Sample Output 3
7362669937