Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
ある 3 日間の天気予報が、長さ 3 の文字列 S として与えられます。
S の i~(1 \leq i \leq 3) 文字目が S のとき、i 日目の天気予報が晴れだったことを、C のときは曇りだったことを、R のときは雨だったことを意味します。
また 3 日間の実際の天気が、長さ 3 の文字列 T として与えられます。
T の i~(1 \leq i \leq 3) 文字目が S のとき、i 日目の実際の天気が晴れだったことを、C のときは曇りだったことを、R のときは雨だったことを意味します。
3 日間で天気予報が的中した日が何日あるかを出力してください。
制約
- S および T は長さ 3 の文字列である。
- S および T は
S,C,Rのみからなる。
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
3 日間で天気予報が的中した日が何日あるかを出力せよ。
入力例 1
CSS CSR
出力例 1
2
- 1 日目の天気予報は曇り、実際の天気は曇りなので、この日の天気予報は的中している。
- 2 日目の天気予報は晴れ、実際の天気は晴れなので、この日の天気予報は的中している。
- 3 日目の天気予報は晴れ、実際の天気は雨なので、この日の天気予報は的中していない。
以上より、このケースでは 3 日間で天気予報が的中した日が 2 日あります。
入力例 2
SSR SSR
出力例 2
3
入力例 3
RRR SSS
出力例 3
0
Score : 100 points
Problem Statement
You will be given a string S of length 3 representing the weather forecast for three days in the past.
The i-th character (1 \leq i \leq 3) of S represents the forecast for the i-th day. S, C, and R stand for sunny, cloudy, and rainy, respectively.
You will also be given a string T of length 3 representing the actual weather on those three days.
The i-th character (1 \leq i \leq 3) of S represents the actual weather on the i-th day. S, C, and R stand for sunny, cloudy, and rainy, respectively.
Print the number of days for which the forecast was correct.
Constraints
- S and T are strings of length 3 each.
- S and T consist of
S,C, andR.
Input
Input is given from Standard Input in the following format:
S T
Output
Print the number of days for which the forecast was correct.
Sample Input 1
CSS CSR
Sample Output 1
2
- For the first day, it was forecast to be cloudy, and it was indeed cloudy.
- For the second day, it was forecast to be sunny, and it was indeed sunny.
- For the third day, it was forecast to be sunny, but it was rainy.
Thus, the forecast was correct for two days in this case.
Sample Input 2
SSR SSR
Sample Output 2
3
Sample Input 3
RRR SSS
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋くんの家には電源プラグの差込口が 1 口しかありません。
そこで、高橋くんは A 個口の電源タップをいくつか使って未使用の差込口を B 口以上に拡張したいと考えています。
A 個口の電源タップ 1 つと未使用の差込口 1 口を使って、新たに差込口を A 口増やすことができます。
最小でいくつの電源タップが必要でしょうか。
制約
- 入力は全て整数である。
- 2 \leq A \leq 20
- 1 \leq B \leq 20
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
必要な電源タップの個数の最小値を出力せよ。
入力例 1
4 10
出力例 1
3
4 個口の電源タップを 3 つ使うと、未使用の差込口は 10 口になります。
入力例 2
8 9
出力例 2
2
8 個口の電源タップを 2 つ使うと、未使用の差込口は 15 口になります。
入力例 3
8 8
出力例 3
1
Score : 200 points
Problem Statement
Takahashi's house has only one socket.
Takahashi wants to extend it with some number of power strips, each with A sockets, into B or more empty sockets.
One power strip with A sockets can extend one empty socket into A empty sockets.
Find the minimum number of power strips required.
Constraints
- All values in input are integers.
- 2 \leq A \leq 20
- 1 \leq B \leq 20
Input
Input is given from Standard Input in the following format:
A B
Output
Print the minimum number of power strips required.
Sample Input 1
4 10
Sample Output 1
3
3 power strips, each with 4 sockets, extend the socket into 10 empty sockets.
Sample Input 2
8 9
Sample Output 2
2
2 power strips, each with 8 sockets, extend the socket into 15 empty sockets.
Sample Input 3
8 8
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
左右一列に N 個のマスが並んでいます。
左から i 番目のマスの高さは H_i です。
あなたは好きなマスに降り立ち、右隣のマスの高さが今居るマスの高さ以下である限り右隣のマスへ移動し続けます。
最大で何回移動できるでしょうか。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^5
- 1 \leq H_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N H_1 H_2 ... H_N
出力
移動できる回数の最大値を出力せよ。
入力例 1
5 10 4 8 7 3
出力例 1
2
左から 3 番目のマスに降り立つと、右に 2 回移動できます。
入力例 2
7 4 4 5 6 6 5 5
出力例 2
3
左から 4 番目のマスに降り立つと、右に 3 回移動できます。
入力例 3
4 1 2 3 4
出力例 3
0
Score : 300 points
Problem Statement
There are N squares arranged in a row from left to right.
The height of the i-th square from the left is H_i.
You will land on a square of your choice, then repeat moving to the adjacent square on the right as long as the height of the next square is not greater than that of the current square.
Find the maximum number of times you can move.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq H_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N H_1 H_2 ... H_N
Output
Print the maximum number of times you can move.
Sample Input 1
5 10 4 8 7 3
Sample Output 1
2
By landing on the third square from the left, you can move to the right twice.
Sample Input 2
7 4 4 5 6 6 5 5
Sample Output 2
3
By landing on the fourth square from the left, you can move to the right three times.
Sample Input 3
4 1 2 3 4
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
整数 N に対して、\{1, 2, ..., N\} を並べ替えた数列 \{P_1, P_2, ..., P_N\} を選びます。
そして、各 i=1,2,...,N について、i を P_i で割った余りを M_i とします。
M_1 + M_2 + \cdots + M_N の最大値を求めてください。
制約
- N は 1 \leq N \leq 10^9 を満たす整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
M_1 + M_2 + \cdots + M_N の最大値を出力せよ。
入力例 1
2
出力例 1
1
\{1, 2\} を並び替えた数列として \{P_1, P_2\} = \{2, 1\} を選ぶと、M_1 + M_2 = 1 + 0 = 1 となります。
入力例 2
13
出力例 2
78
入力例 3
1
出力例 3
0
Score : 400 points
Problem Statement
For an integer N, we will choose a permutation \{P_1, P_2, ..., P_N\} of \{1, 2, ..., N\}.
Then, for each i=1,2,...,N, let M_i be the remainder when i is divided by P_i.
Find the maximum possible value of M_1 + M_2 + \cdots + M_N.
Constraints
- N is an integer satisfying 1 \leq N \leq 10^9.
Input
Input is given from Standard Input in the following format:
N
Output
Print the maximum possible value of M_1 + M_2 + \cdots + M_N.
Sample Input 1
2
Sample Output 1
1
When the permutation \{P_1, P_2\} = \{2, 1\} is chosen, M_1 + M_2 = 1 + 0 = 1.
Sample Input 2
13
Sample Output 2
78
Sample Input 3
1
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 人の選手がテニスの大会に参加します。彼らを選手 1、選手 2、\ldots、選手 N と呼びます。
大会は総当たり戦で、合計 N(N-1)/2 試合が行われます。 これらの試合の日程を、以下の条件をすべて満たすように決めることは可能でしょうか。可能である場合、必要な最小の日数も求めてください。
- 各選手は一日に最大で一試合を行う。
- 各選手 i (1 \leq i \leq N) は、選手 A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} とこの順に一度ずつ試合を行う。
制約
- 3 \leq N \leq 1000
- 1 \leq A_{i, j} \leq N
- A_{i, j} \neq i
- A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} はすべて異なる。
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}
出力
条件をすべて満たすように全試合の日程を決めることが可能なら必要な最小の日数を、不可能なら -1 を出力せよ。
入力例 1
3 2 3 1 3 1 2
出力例 1
3
3 日間で次のように試合を行えばすべての条件を満たせます。
- 1 日目: 選手 1 対 選手 2
- 2 日目: 選手 1 対 選手 3
- 3 日目: 選手 2 対 選手 3
これが必要な最小日数です。
入力例 2
4 2 3 4 1 3 4 4 1 2 3 1 2
出力例 2
4
4 日間で次のように試合を行えばすべての条件を満たせます。
- 1 日目: 選手 1 対 選手 2、選手 3 対 選手 4
- 2 日目: 選手 1 対 選手 3
- 3 日目: 選手 1 対 選手 4、選手 2 対 選手 3
- 4 日目: 選手 2 対 選手 4
これが必要な最小日数です。
入力例 3
3 2 3 3 1 1 2
出力例 3
-1
どのような日程で試合を行っても何らかの条件に違反します。
Score : 500 points
Problem Statement
N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.
The tournament is round-robin format, and there will be N(N-1)/2 matches in total. Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.
- Each player plays at most one matches in a day.
- Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.
Constraints
- 3 \leq N \leq 1000
- 1 \leq A_{i, j} \leq N
- A_{i, j} \neq i
- A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.
Input
Input is given from Standard Input in the following format:
N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}
Output
If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.
Sample Input 1
3 2 3 1 3 1 2
Sample Output 1
3
All the conditions can be satisfied if the matches are scheduled for three days as follows:
- Day 1: Player 1 vs Player 2
- Day 2: Player 1 vs Player 3
- Day 3: Player 2 vs Player 3
This is the minimum number of days required.
Sample Input 2
4 2 3 4 1 3 4 4 1 2 3 1 2
Sample Output 2
4
All the conditions can be satisfied if the matches are scheduled for four days as follows:
- Day 1: Player 1 vs Player 2, Player 3 vs Player 4
- Day 2: Player 1 vs Player 3
- Day 3: Player 1 vs Player 4, Player 2 vs Player 3
- Day 4: Player 2 vs Player 4
This is the minimum number of days required.
Sample Input 3
3 2 3 3 1 1 2
Sample Output 3
-1
Any scheduling of the matches violates some condition.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 600 点
問題文
E869120 君は最初、2 次元平面上の原点 (0, 0) に立っています。
彼は N 個のエンジンを持っています。エンジンの使い方と機能は以下のようになります。
- i 個目のエンジンを使うと、E869120 君のいる場所の X 座標が x_i、Y 座標が y_i 変化する。つまり、E869120 君が座標 (X, Y) にいるときに i 個目のエンジンを使うと、座標 (X + x_i, Y + y_i) に移動する。
- エンジンはどのような順番で使ってもよいが、各エンジンは 1 回までしか使えない。ただし、使わないエンジンがあってもよい。
彼は、原点から最も遠い場所に行きたいです。
最後に到達する地点の座標を (X, Y) として、原点からの距離 \sqrt{X^2 + Y^2} の最大値を求めてください。
制約
- 1 \leq N \leq 100
- -1 \ 000 \ 000 \leq x_i \leq 1 \ 000 \ 000
- -1 \ 000 \ 000 \leq y_i \leq 1 \ 000 \ 000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 : : x_N y_N
出力
最後に到達する地点の、原点からの距離の最大値を実数値として出力せよ。
ただし、実際の答えとの相対誤差または絶対誤差が 10^{-10} 以内であれば正解とみなす。
入力例 1
3 0 10 5 -5 -5 -5
出力例 1
10.000000000000000000000000000000000000000000000000
うまくエンジンを使うと、最後に到達する地点の、原点からの距離を 10 にすることができます。
これには次の 3 通りの方法があります。
- エンジン 1 を使って (0, 10) に移動する
- エンジン 2 を使って (5, -5) に移動し、その後エンジン 3 を使って (0, -10) に移動する
- エンジン 3 を使って (-5, -5) に移動し、その後エンジン 2 を使って (0, -10) に移動する
距離を 10 より大きくする方法はないので、最大値は 10 となります。
入力例 2
5 1 1 1 0 0 1 -1 0 0 -1
出力例 2
2.828427124746190097603377448419396157139343750753
最後に到達する地点の、原点からの距離の最大値は 2 \sqrt{2} = 2.82842... となります。
これを達成する方法として、次のようなものが挙げられます。
- エンジン 1 を使って (1, 1) に移動し、その後エンジン 2 を使って (2, 1) に移動し、最後にエンジン 3 を使って (2, 2) に移動する
入力例 3
5 1 1 2 2 3 3 4 4 5 5
出力例 3
21.213203435596425732025330863145471178545078130654
エンジン 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 の順で全部使うと、最終的に (15, 15) にたどり着き、原点からの距離は 15 \sqrt{2} = 21.2132... となります。
入力例 4
3 0 0 0 1 1 0
出力例 4
1.414213562373095048801688724209698078569671875376
(x_i, y_i) = (0, 0) である、何の意味も持たないエンジンがある可能性もあります。
入力例 5
1 90447 91000
出力例 5
128303.000000000000000000000000000000000000000000000000
1 個しかエンジンがない場合もあることにご注意ください。
入力例 6
2 96000 -72000 -72000 54000
出力例 6
120000.000000000000000000000000000000000000000000000000
2 個しかエンジンがない場合もあります。
入力例 7
10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
出力例 7
148.660687473185055226120082139313966514489855137208
Score: 600 points
Problem Statement
E869120 is initially standing at the origin (0, 0) in a two-dimensional plane.
He has N engines, which can be used as follows:
- When E869120 uses the i-th engine, his X- and Y-coordinate change by x_i and y_i, respectively. In other words, if E869120 uses the i-th engine from coordinates (X, Y), he will move to the coordinates (X + x_i, Y + y_i).
- E869120 can use these engines in any order, but each engine can be used at most once. He may also choose not to use some of the engines.
He wants to go as far as possible from the origin. Let (X, Y) be his final coordinates. Find the maximum possible value of \sqrt{X^2 + Y^2}, the distance from the origin.
Constraints
- 1 \leq N \leq 100
- -1 \ 000 \ 000 \leq x_i \leq 1 \ 000 \ 000
- -1 \ 000 \ 000 \leq y_i \leq 1 \ 000 \ 000
- 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 : : x_N y_N
Output
Print the maximum possible final distance from the origin, as a real value. Your output is considered correct when the relative or absolute error from the true answer is at most 10^{-10}.
Sample Input 1
3 0 10 5 -5 -5 -5
Sample Output 1
10.000000000000000000000000000000000000000000000000
The final distance from the origin can be 10 if we use the engines in one of the following three ways:
- Use Engine 1 to move to (0, 10).
- Use Engine 2 to move to (5, -5), and then use Engine 3 to move to (0, -10).
- Use Engine 3 to move to (-5, -5), and then use Engine 2 to move to (0, -10).
The distance cannot be greater than 10, so the maximum possible distance is 10.
Sample Input 2
5 1 1 1 0 0 1 -1 0 0 -1
Sample Output 2
2.828427124746190097603377448419396157139343750753
The maximum possible final distance is 2 \sqrt{2} = 2.82842.... One of the ways to achieve it is:
- Use Engine 1 to move to (1, 1), and then use Engine 2 to move to (2, 1), and finally use Engine 3 to move to (2, 2).
Sample Input 3
5 1 1 2 2 3 3 4 4 5 5
Sample Output 3
21.213203435596425732025330863145471178545078130654
If we use all the engines in the order 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5, we will end up at (15, 15), with the distance 15 \sqrt{2} = 21.2132... from the origin.
Sample Input 4
3 0 0 0 1 1 0
Sample Output 4
1.414213562373095048801688724209698078569671875376
There can be useless engines with (x_i, y_i) = (0, 0).
Sample Input 5
1 90447 91000
Sample Output 5
128303.000000000000000000000000000000000000000000000000
Note that there can be only one engine.
Sample Input 6
2 96000 -72000 -72000 54000
Sample Output 6
120000.000000000000000000000000000000000000000000000000
There can be only two engines, too.
Sample Input 7
10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Sample Output 7
148.660687473185055226120082139313966514489855137208