Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
二次元平面上に N 個の点があります。i 個目の点の座標は (x_i,y_i) です。
この中から 2 個の点を選ぶとき、それらを結ぶ線分の長さの最大値を求めてください。
制約
- 2 \leq N \leq 100
- -1000 \leq x_i,y_i \leq 1000
- (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
x_1 y_1
x_2 y_2
\hspace{0.4cm} \vdots
x_N y_N
出力
2 点を結ぶ線分の長さの最大値を出力せよ。
想定解との絶対誤差または相対誤差が 10^{-6} 以下であれば正解とみなされる。
入力例 1
3 0 0 0 1 1 1
出力例 1
1.4142135624
1 個目の点と 3 個目の点を選んだときそれらを結ぶ線分の長さは \sqrt 2 = 1.41421356237\dots となり、これが最大です。
入力例 2
5 315 271 -2 -621 -205 -511 -952 482 165 463
出力例 2
1455.7159750446
Score : 200 points
Problem Statement
There are N points in a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).
Find the maximum length of a segment connecting two of these points.
Constraints
- 2 \leq N \leq 100
- -1000 \leq x_i,y_i \leq 1000
- (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
\hspace{0.4cm} \vdots
x_N y_N
Output
Print the maximum length of a segment connecting two of the points.
Your answer will be considered correct when the absolute or relative error from the judge's answer is at most 10^{-6}.
Sample Input 1
3 0 0 0 1 1 1
Sample Output 1
1.4142135624
For the 1-st and 3-rd points, the length of the segment connecting them is \sqrt 2 = 1.41421356237\dots, which is the maximum length.
Sample Input 2
5 315 271 -2 -621 -205 -511 -952 482 165 463
Sample Output 2
1455.7159750446
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 R 行横 C 列の盤面があります。上から i 行目、左から j 列目のマスを (i,j) と表します。
(i,j) の現在の状態が文字 B_{i,j} として与えられます。
. は空きマス、# は壁があるマスを表し、
1, 2,\dots, 9 はそれぞれ威力 1,2,\dots,9 の爆弾があるマスを表します。
次の瞬間に、全ての爆弾が同時に爆発します。 爆弾が爆発すると、爆弾があるマスからのマンハッタン距離がその爆弾の威力以下であるような全てのマス（その爆弾があるマス自体を含む）が空きマスに変わります。 ここで、(r_1,c_1) から (r_2,c_2) までのマンハッタン距離は |r_1-r_2|+|c_1-c_2| です。
爆発後の盤面を出力してください。
制約
- 1\leq R,C \leq 20
- R,C は整数
- B_{i,j} は
.,#,1,2,\dots,9のいずれかである
入力
入力は以下の形式で標準入力から与えられる。
R C
B_{1,1}B_{1,2}\dots B_{1,C}
\vdots
B_{R,1}B_{R,2}\dots B_{R,C}
出力
爆発後の盤面を R 行で出力せよ。盤面の表し方は入力と同じ形式を用いること (R と C を出力する必要はない)。
入力例 1
4 4 .1.# ###. .#2. #.##
出力例 1
...# #... .... #...
- (1,2) にある爆弾の爆発によって、上図の青いマスと紫のマスが空きマスに変わります。
- (3,3) にある爆弾の爆発によって、上図の赤いマスと紫のマスが空きマスに変わります。
この例のように、爆弾が効果を及ぼす範囲に被りがあることもあります。
入力例 2
2 5 ..#.# ###.#
出力例 2
..#.# ###.#
爆弾が 1 つもないこともあります。
入力例 3
2 3 11# ###
出力例 3
... ..#
入力例 4
4 6 #.#3#. ###.#. ##.### #1..#.
出力例 4
...... #..... #....# ....#.
Score : 200 points
Problem Statement
We have a board with R rows running horizontally and C columns running vertically. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.
You are given characters B_{i,j} representing the current states of (i,j).
. represents an empty square; # represents a square with a wall; 1, 2,\dots, 9 represent a square with a bomb of power 1,2,\dots,9, respectively.
At the next moment, all bombs will explode simultaneously. When a bomb explodes, every square whose Manhattan distance from the square with the bomb is not greater than the power of the bomb will turn into an empty square. Here, the Manhattan distance from (r_1,c_1) to (r_2,c_2) is |r_1-r_2|+|c_1-c_2|.
Print the board after the explosions.
Constraints
- 1\leq R,C \leq 20
- R and C are integers.
- Each B_{i,j} is one of
.,#,1,2, \dots,9.
Input
The input is given from Standard Input in the following format:
R C
B_{1,1}B_{1,2}\dots B_{1,C}
\vdots
B_{R,1}B_{R,2}\dots B_{R,C}
Output
Print R lines representing the board after the explosions. Use the format used in the input (do not print R or C).
Sample Input 1
4 4 .1.# ###. .#2. #.##
Sample Output 1
...# #... .... #...
- The explosion of the bomb at (1,2) will turn the blue squares and purple squares in the above figure into empty squares.
- The explosion of the bomb at (3,3) will turn the red squares and purple squares in the above figure into empty squares.
As seen in this sample, the explosion ranges of bombs may overlap.
Sample Input 2
2 5 ..#.# ###.#
Sample Output 2
..#.# ###.#
There may be no bombs.
Sample Input 3
2 3 11# ###
Sample Output 3
... ..#
Sample Input 4
4 6 #.#3#. ###.#. ##.### #1..#.
Sample Output 4
...... #..... #....# ....#.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
文字列 S の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から K 番目にくる文字列を求めてください。
「各文字を並べ替えて作ることが可能な文字列」とは？
「文字列 A が文字列 B の各文字を並べ替えて作ることが可能な文字列である」とは、任意の文字が文字列 A と文字列 B に同数含まれるということを指します。制約
- 1 \le |S| \le 8
- S は英小文字のみからなる
- S の各文字を並べ替えてできる文字列は K 種類以上存在する
入力
入力は以下の形式で標準入力から与えられる。
S K
出力
答えを出力せよ。
入力例 1
aab 2
出力例 1
aba
文字列 aab の各文字を並べ替えて作ることが可能な文字列は \{ aab, aba, baa \} の 3 つですが、このうち辞書順で前から 2 番目にくるものは aba です。
入力例 2
baba 4
出力例 2
baab
入力例 3
ydxwacbz 40320
出力例 3
zyxwdcba
Score : 300 points
Problem Statement
Find the K-th lexicographically smallest string among the strings that are permutations of a string S.
What is a permutation of a string?
A string A is said to be a permutation of a string B when any character occurs the same number of times in A and B.Constraints
- 1 \le |S| \le 8
- S consists of lowercase English letters.
- There are at least K distinct strings that are permutations of S.
Input
Input is given from Standard Input in the following format:
S K
Output
Print the answer.
Sample Input 1
aab 2
Sample Output 1
aba
There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.
Sample Input 2
baba 4
Sample Output 2
baab
Sample Input 3
ydxwacbz 40320
Sample Output 3
zyxwdcba
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 人の生徒からなるクラスがあり、i\,(1 \leq i \leq N) 番目の生徒の身長は A_i です。
j=1,2,\ldots,Q について、以下の質問に答えてください。
- N 人のうち、身長が x_j 以上の生徒は何人か？
制約
- 1 \leq N,Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq x_j \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \ldots A_N x_1 x_2 \vdots x_Q
出力
Q 行出力せよ。
j\,(1 \leq j \leq Q) 行目には身長が x_j 以上の生徒の数を出力せよ。
入力例 1
3 1 100 160 130 120
出力例 1
2
身長が 120 以上の生徒は 2 番目の生徒と 3 番目の生徒です。
入力例 2
5 5 1 2 3 4 5 6 5 4 3 2
出力例 2
0 1 2 3 4
入力例 3
5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422
出力例 3
5 3 5 5 5
Score : 300 points
Problem Statement
There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.
For each j=1,2,\ldots,Q, answer the following question.
- How many of the N students have a height of at least x_j?
Constraints
- 1 \leq N,Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq x_j \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q A_1 A_2 \ldots A_N x_1 x_2 \vdots x_Q
Output
Print Q lines.
The j-th line (1 \leq j \leq Q) should contain the number of students with a height of at least x_j.
Sample Input 1
3 1 100 160 130 120
Sample Output 1
2
The students with a height of at least 120 are the 2-nd and 3-rd ones.
Sample Input 2
5 5 1 2 3 4 5 6 5 4 3 2
Sample Output 2
0 1 2 3 4
Sample Input 3
5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422
Sample Output 3
5 3 5 5 5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
頂点に 1 から N の番号が付いた N 頂点の重み付き無向完全グラフが与えられます。頂点 i と頂点 j\ (i< j) を結ぶ辺の重みは D_{i,j} です。
以下の条件を満たすように何本かの辺を選ぶとき、選んだ辺の重みの総和としてあり得る最大値を求めてください。
- 選んだ辺の端点はどの 2 個も相異なる。
制約
- 2\leq N\leq 16
- 1\leq D_{i,j} \leq 10^9
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
D_{1,2} D_{1,3} \ldots D_{1,N}
D_{2,3} \ldots D_{2,N}
\vdots
D_{N-1,N}
出力
答えを整数として出力せよ。
入力例 1
4 1 5 4 7 8 6
出力例 1
13
頂点 1 と頂点 3 を結ぶ辺、頂点 2 と頂点 4 を結ぶ辺を選ぶと、辺の重みの総和が 5+8=13 となります。
これが達成可能な最大値であることが示せます。
入力例 2
3 1 2 3
出力例 2
3
N が奇数の場合もあります。
入力例 3
16 5 6 5 2 1 7 9 7 2 5 5 2 4 7 6 8 7 7 9 8 1 9 6 10 8 8 6 10 3 10 5 8 1 10 7 8 4 8 6 5 1 10 7 4 1 4 5 4 5 10 1 5 1 2 2 9 9 7 6 2 2 8 3 5 2 9 10 3 1 1 2 10 7 7 5 10 6 1 8 9 3 2 4 2 10 10 8 9 2 10 7 9 5 8 8 7 5 8 2 4 2 2 6 8 3 2 7 3 10 3 5 7 10 3 8 5 7 9 1 4
出力例 3
75
Score : 400 points
Problem Statement
You are given a weighted undirected complete graph with N vertices numbered from 1 to N. The edge connecting vertices i and j (i< j) has a weight of D_{i,j}.
When choosing some number of edges under the following condition, find the maximum possible total weight of the chosen edges.
- The endpoints of the chosen edges are pairwise distinct.
Constraints
- 2\leq N\leq 16
- 1\leq D_{i,j} \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
D_{1,2} D_{1,3} \ldots D_{1,N}
D_{2,3} \ldots D_{2,N}
\vdots
D_{N-1,N}
Output
Print the answer as an integer.
Sample Input 1
4 1 5 4 7 8 6
Sample Output 1
13
If you choose the edge connecting vertices 1 and 3, and the edge connecting vertices 2 and 4, the total weight of the edges is 5+8=13.
It can be shown that this is the maximum achievable value.
Sample Input 2
3 1 2 3
Sample Output 2
3
N can be odd.
Sample Input 3
16 5 6 5 2 1 7 9 7 2 5 5 2 4 7 6 8 7 7 9 8 1 9 6 10 8 8 6 10 3 10 5 8 1 10 7 8 4 8 6 5 1 10 7 4 1 4 5 4 5 10 1 5 1 2 2 9 9 7 6 2 2 8 3 5 2 9 10 3 1 1 2 10 7 7 5 10 6 1 8 9 3 2 4 2 10 10 8 9 2 10 7 9 5 8 8 7 5 8 2 4 2 2 6 8 3 2 7 3 10 3 5 7 10 3 8 5 7 9 1 4
Sample Output 3
75