実行時間制限: 2 sec / メモリ制限: 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
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
文字列 S, T が与えられます。以下の操作を高々 1 回行うことで、S を T と一致させることができるかを判定してください。
- S の隣り合う 2 文字を選び、入れ替える。
なお、上記の操作を一度も行わないことも可能です。
制約
- S, T はそれぞれ英小文字のみからなる、長さ 2 以上 100 以下の文字列
- S の長さと T の長さは等しい
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
問題文中の操作を高々 1 回行うことで S を T と一致させることができるなら Yes を、できないなら No を出力せよ。
入力例 1
abc acb
出力例 1
Yes
S の 2 文字目と 3 文字目を入れ替えることで、S を T と一致させることができます。
入力例 2
aabb bbaa
出力例 2
No
どのように操作を行っても、S を T と一致させることはできません。
入力例 3
abcde abcde
出力例 3
Yes
S と T は既に一致しています。
Score : 200 points
Problem Statement
You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:
- choose two adjacent characters in S and swap them.
Note that it is allowed to choose not to do the operation.
Constraints
- Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
- S and T have the same length.
Input
Input is given from Standard Input in the following format:
S T
Output
If it is possible to make S and T equal by doing the operation in Problem Statement at most once, print Yes; otherwise, print No.
Sample Input 1
abc acb
Sample Output 1
Yes
You can swap the 2-nd and 3-rd characters of S to make S and T equal.
Sample Input 2
aabb bbaa
Sample Output 2
No
There is no way to do the operation to make S and T equal.
Sample Input 3
abcde abcde
Sample Output 3
Yes
S and T are already equal.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
N 棟のビルが等間隔に一列に並んでいます。手前から i 番目のビルの高さは H_i です。
あなたは次の条件をともに満たすようにいくつかのビルを選んで電飾で飾ろうとしています。
- 選んだビルたちは高さが等しい
- 選んだビルたちは等間隔に並んでいる
最大でいくつのビルを選ぶことができますか？ なお、ちょうど 1 つのビルを選んだときは条件を満たすとみなします。
制約
- 1 \leq N \leq 3000
- 1 \leq H_i \leq 3000
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N H_1 \ldots H_N
出力
答えを出力せよ。
入力例 1
8 5 7 5 7 7 5 7 7
出力例 1
3
手前から 2,5,8 番目のビルを選ぶと条件を満たします。
入力例 2
10 100 200 300 400 500 600 700 800 900 1000
出力例 2
1
1つのビルを選んだときは条件を満たすとみなします。
入力例 3
32 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5
出力例 3
3
Score : 350 points
Problem Statement
There are N buildings arranged in a line at equal intervals. The height of the i-th building from the front is H_i.
You want to decorate some of these buildings with illuminations so that both of the following conditions are satisfied:
- The chosen buildings all have the same height.
- The chosen buildings are arranged at equal intervals.
What is the maximum number of buildings you can choose? If you choose exactly one building, it is considered to satisfy the conditions.
Constraints
- 1 \leq N \leq 3000
- 1 \leq H_i \leq 3000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H_1 \ldots H_N
Output
Print the answer.
Sample Input 1
8 5 7 5 7 7 5 7 7
Sample Output 1
3
Choosing the 2nd, 5th, and 8th buildings from the front satisfies the conditions.
Sample Input 2
10 100 200 300 400 500 600 700 800 900 1000
Sample Output 2
1
Choosing just one building is considered to satisfy the conditions.
Sample Input 3
32 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5
Sample Output 3
3
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
1 から N の番号がついた N 人の人がいます。
人 i は数 Q_i が書かれたゼッケンを着けており、人 P_i を見つめています。
i が書かれたゼッケンを着けている人が見つめている人の着けているゼッケンにかかれている数を、i=1,2,\ldots,N のそれぞれについて求めてください。
制約
- 2 \leq N \leq 3\times 10^5
- 1 \leq P_i \leq N
- P_i は相異なる
- 1 \leq Q_i \leq N
- Q_i は相異なる
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \dots P_N Q_1 Q_2 \dots Q_N
出力
i が書かれたゼッケンを着けている人が見つめている人の着けているゼッケンにかかれている数を S_i とする。
S_1,S_2,\ldots,S_N をこの順に空白区切りで出力せよ。
入力例 1
4 4 3 2 1 2 3 1 4
出力例 1
3 4 1 2
人 3 は 1 が書かれたゼッケンを着けており、人 3 が見つめている人 2 は 3 が書かれたゼッケンを着けています。 よって i=1 に対する答えは 3 になります。
入力例 2
10 2 6 4 3 7 8 9 10 1 5 1 4 8 2 10 5 7 3 9 6
出力例 2
4 8 6 5 3 10 9 2 1 7
Score : 300 points
Problem Statement
There are N people numbered from 1 to N.
Person i is wearing a bib with the number Q_i and is staring at person P_i.
For each i = 1,2,\ldots,N, find the number written on the bib of the person that the person wearing the bib with number i is staring at.
Constraints
- 2 \leq N \leq 3\times 10^5
- 1 \leq P_i \leq N
- The values of P_i are distinct.
- 1 \leq Q_i \leq N
- The values of Q_i are distinct.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \dots P_N Q_1 Q_2 \dots Q_N
Output
Let S_i be the number written on the bib of the person that the person wearing the bib with number i is staring at.
Print S_1, S_2, \ldots, S_N in this order, separated by a single space.
Sample Input 1
4 4 3 2 1 2 3 1 4
Sample Output 1
3 4 1 2
Person 3 is wearing the bib with the number 1, and the person that person 3 is staring at, person 2, is wearing the bib with the number 3. Thus, the answer for i = 1 is 3.
Sample Input 2
10 2 6 4 3 7 8 9 10 1 5 1 4 8 2 10 5 7 3 9 6
Sample Output 2
4 8 6 5 3 10 9 2 1 7
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君はすぬけ君たちを捕まえようとしています。
数直線上の座標 0,1,2,3,4 の 5 箇所に穴があり、すぬけ君たちの巣につながっています。
これから N 匹のすぬけ君が穴から出てきます。i 番目のすぬけ君は時刻 T_i に座標 X_i の穴から出てきて、大きさは A_i であることがわかっています。
高橋君は時刻 0 に座標 0 におり、数直線上を単位時間あたり 1 以下の速さで移動することができます。
すぬけ君が穴から出てきたのと同じ時刻に同じ座標に高橋君がいるとき、かつ、そのときに限り、高橋君はすぬけ君を捕まえることができます。
すぬけ君を捕まえるのにかかる時間は無視できます。
高橋君が適切に行動したとき、捕まえることができるすぬけ君の大きさの合計の最大値を求めてください。
制約
- 1 \leq N \leq 10^5
- 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
- 0 \leq X_i \leq 4
- 1 \leq A_i \leq 10^9
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N T_1 X_1 A_1 T_2 X_2 A_2 \vdots T_N X_N A_N
出力
答えを整数として出力せよ。
入力例 1
3 1 0 100 3 3 10 5 4 1
出力例 1
101
次のように行動するのが最適です。
- 座標 0 で待機し、時刻 1 に 1 番目のすぬけ君を捕まえる
- 座標 4 へ移動し、時刻 5 に 3 番目のすぬけ君を捕まえる
1 番目と 2 番目のすぬけ君を両方とも捕まえることはできないので、これが最大です。
入力例 2
3 1 4 1 2 4 1 3 4 1
出力例 2
0
高橋君はすぬけ君を 1 匹も捕まえることができません。
入力例 3
10 1 4 602436426 2 1 623690081 3 3 262703497 4 4 628894325 5 3 450968417 6 1 161735902 7 1 707723857 8 2 802329211 9 0 317063340 10 2 125660016
出力例 3
2978279323
Score : 400 points
Problem Statement
Takahashi is trying to catch many Snuke.
There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.
Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.
Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.
Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.
Constraints
- 1 \leq N \leq 10^5
- 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
- 0 \leq X_i \leq 4
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N T_1 X_1 A_1 T_2 X_2 A_2 \vdots T_N X_N A_N
Output
Print the answer as an integer.
Sample Input 1
3 1 0 100 3 3 10 5 4 1
Sample Output 1
101
The optimal strategy is as follows.
- Wait at coordinate 0 to catch the first Snuke at time 1.
- Go to coordinate 4 to catch the third Snuke at time 5.
It is impossible to catch both the first and second Snuke, so this is the best he can.
Sample Input 2
3 1 4 1 2 4 1 3 4 1
Sample Output 2
0
Takahashi cannot catch any Snuke.
Sample Input 3
10 1 4 602436426 2 1 623690081 3 3 262703497 4 4 628894325 5 3 450968417 6 1 161735902 7 1 707723857 8 2 802329211 9 0 317063340 10 2 125660016
Sample Output 3
2978279323