Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
あなたはコワスギ銀行の通帳を持っています。コワスギ銀行の預金通帳には、引き出し額に応じて手数料が変わるという怖すぎる性質があります。
コワスギ銀行の通帳からお金を引き出すには、1\,000 円単位で引き出し額を指定したうえで、引き出し額 1\,000 円あたり C 円の手数料を残高から別途支払う必要があります。銀行の残高が 0 円未満になる引き出しを行うことはできません。
あなたが持っているコワスギ銀行の通帳の残高が X 円のとき、そこから最大で何円を引き出せますか？
制約
- 1 \leq X \leq 10^7
- 1 \leq C \leq 999
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
X C
出力
答えを出力せよ。
入力例 1
650000 8
出力例 1
644000
644\,000 円を引き出すために必要な手数料は 644\,000 \times \displaystyle\frac{8}{1000} = 5\,152 円になるので、644\,000 + 5\,152 \leq 650\,000 より、644\,000 円は引き出すことができます。
一方で、645\,000 円引き出すために必要な手数料は 645\,000 \times \displaystyle\frac{8}{1000} = 5\,160 円になるので、645\,000 + 5\,160 > 650\,000 より、645\,000 円は引き出すことができません。
入力例 2
1003 4
出力例 2
0
まったくお金が引き出せないこともありえます。
入力例 3
10000000 24
出力例 3
9765000
Score : 150 points
Problem Statement
You have a bankbook from The Terrifying Bank. The deposit passbook of the bank has a terrifyingly scary property that the commission fee changes according to the withdrawal amount.
To withdraw money from the passbook, you need to specify the withdrawal amount in units of 1\,000 yen, and pay a commission fee of C yen per 1\,000 yen of withdrawal amount separately from the balance. Withdrawals are not allowed if they would leave the balance below 0 yen.
When the balance of your passbook from the bank is X yen, what is the maximum amount of money you can withdraw from it?
Constraints
- 1 \leq X \leq 10^7
- 1 \leq C \leq 999
- All input values are integers.
Input
The input is given from Standard Input in the following format:
X C
Output
Output the answer.
Sample Input 1
650000 8
Sample Output 1
644000
The commission fee required to withdraw 644\,000 yen is 644\,000 \times \displaystyle\frac{8}{1000} = 5\,152 yen, so since 644\,000 + 5\,152 \leq 650\,000, you can withdraw 644\,000 yen.
On the other hand, the commission fee required to withdraw 645\,000 yen is 645\,000 \times \displaystyle\frac{8}{1000} = 5\,160 yen, so since 645\,000 + 5\,160 > 650\,000, you cannot withdraw 645\,000 yen.
Sample Input 2
1003 4
Sample Output 2
0
It is possible that no money can be withdrawn at all.
Sample Input 3
10000000 24
Sample Output 3
9765000
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
チーム高橋とチーム青木が N 回の試合を行いました。 i 回め (1\leq i\leq N) の試合ではチーム高橋が X _ i 点、チーム青木が Y _ i 点を獲得しました。
N 回の試合で獲得した得点の合計がより多いチームの勝ちです。
どちらのチームが勝ったか出力してください。 ただし、獲得した得点の合計が等しい場合は引き分けとなります。
制約
- 1\leq N\leq 100
- 0\leq X _ i\leq 100\ (1\leq i\leq N)
- 0\leq Y _ i\leq 100\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X _ 1 Y _ 1 X _ 2 Y _ 2 \vdots X _ N Y _ N
出力
チーム高橋が勝った場合 Takahashi を、チーム青木が勝った場合 Aoki を、引き分けの場合 Draw を出力せよ。
入力例 1
4 10 2 10 1 10 2 3 2
出力例 1
Takahashi
4 回の試合で、チーム高橋は 33 点、チーム青木は 7 点を獲得しました。
チーム高橋が勝ったため、Takahashi を出力してください。
入力例 2
6 5 4 4 5 2 4 1 6 7 1 3 2
出力例 2
Draw
いずれのチームも 22 点を獲得しました。
引き分けなので、Draw を出力してください。
入力例 3
4 0 0 10 10 50 50 0 100
出力例 3
Aoki
一方もしくは両方のチームが、一試合のうちに 1 点も取れない場合もあります。
Score: 100 points
Problem Statement
Team Takahashi and Team Aoki played N matches. In the i-th match (1\leq i\leq N), Team Takahashi scored X _ i points, and Team Aoki scored Y _ i points.
The team with the higher total score from the N matches wins.
Print the winner. If the two teams have the same total score, it is a draw.
Constraints
- 1\leq N\leq 100
- 0\leq X _ i\leq 100\ (1\leq i\leq N)
- 0\leq Y _ i\leq 100\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X _ 1 Y _ 1 X _ 2 Y _ 2 \vdots X _ N Y _ N
Output
If Team Takahashi wins, print Takahashi; if Team Aoki wins, print Aoki; if it is a draw, print Draw.
Sample Input 1
4 10 2 10 1 10 2 3 2
Sample Output 1
Takahashi
In four matches, Team Takahashi scored 33 points, and Team Aoki scored 7 points.
Team Takahashi wins, so print Takahashi.
Sample Input 2
6 5 4 4 5 2 4 1 6 7 1 3 2
Sample Output 2
Draw
Both teams scored 22 points.
It is a draw, so print Draw.
Sample Input 3
4 0 0 10 10 50 50 0 100
Sample Output 3
Aoki
One or both teams may score no points in a match.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
非負整数 X に対し、 i=0,1,\dots,K-1 の順に次の操作を行ったとき、操作を全て終えた時点での X を求めてください。
- X の 10^i の位以下を四捨五入する。
- 厳密には、 X を「 |Y-X| が最小となる 10^{i+1} の倍数のうち最大のもの」である Y に置き換える。
- 具体例を挙げる。
- 273 の 10^1 の位以下を四捨五入すれば 300 となる。
- 999 の 10^2 の位以下を四捨五入すれば 1000 となる。
- 100 の 10^9 の位以下を四捨五入すれば 0 となる。
- 1015 の 10^0 の位以下を四捨五入すれば 1020 となる。
制約
- X,K は整数
- 0 \le X < 10^{15}
- 1 \le K \le 15
入力
入力は以下の形式で標準入力から与えられる。
X K
出力
答えを整数として出力せよ。
入力例 1
2048 2
出力例 1
2100
操作の過程で、 X は 2048 \rightarrow 2050 \rightarrow 2100 と変化します。
入力例 2
1 15
出力例 2
0
入力例 3
999 3
出力例 3
1000
入力例 4
314159265358979 12
出力例 4
314000000000000
X は 32bit 整数型に収まらない可能性があります。
Score : 200 points
Problem Statement
Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.
- Round X off to the nearest 10^i.
- Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
- Here are some examples:
- Rounding 273 off to the nearest 10^2 yields 300.
- Rounding 999 off to the nearest 10^3 yields 1000.
- Rounding 100 off to the nearest 10^{10} yields 0.
- Rounding 1015 off to the nearest 10^1 yields 1020.
Constraints
- X and K are integers.
- 0 \le X < 10^{15}
- 1 \le K \le 15
Input
The input is given from Standard Input in the following format:
X K
Output
Print the answer as an integer.
Sample Input 1
2048 2
Sample Output 1
2100
X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.
Sample Input 2
1 15
Sample Output 2
0
Sample Input 3
999 3
Sample Output 3
1000
Sample Input 4
314159265358979 12
Sample Output 4
314000000000000
X may not fit into a 32-bit integer type.
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
配点 : 300 点
問題文
N 個の宝石があります。i 番目の宝石の色（整数で表されます）は C_i で価値は V_i です。
この N 個の宝石の中から K 個を選びます。ただし、選んだ宝石の色が M 種類以上なければなりません。
このとき、選んだ宝石の価値の総和としてありうる最大値を求めてください。（与えられる入力では、このような選択が必ず可能です。）
制約
- 1 \leq M \leq K \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq N
- 1 \leq V_i \leq 10^9
- M 種類以上の色の宝石が存在する
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K M C_1 V_1 C_2 V_2 \vdots C_N V_N
出力
選んだ宝石の価値の総和としてありうる最大値を整数として出力せよ。
入力例 1
5 3 2 1 30 1 40 1 50 2 10 3 20
出力例 1
110
この例では 5 個の宝石から 3 個を選びます。選んだ宝石の色が 2 種類以上なければなりません。
宝石 2, 3, 5 を選ぶと、それらの色は 1, 1, 3 で 2 種類あります。それらの価値の総和は 40 + 50 + 20 = 110 で、これがありうる最大値です。
入力例 2
5 3 3 1 30 1 40 1 50 2 10 3 20
出力例 2
80
宝石や選ぶ個数は入力例 1 と同じですが、選んだ宝石の色が 3 種類以上なければなりません。
宝石 3, 4, 5 を選ぶと、それらの色は 1, 2, 3 で 3 種類あります。それらの価値の総和は 50 + 10 + 20 = 80 で、これがありうる最大値です。
入力例 3
5 5 1 4 1000000000 5 1000000000 4 1000000000 5 1000000000 4 1000000000
出力例 3
5000000000
オーバーフローに注意してください。
Score : 300 points
Problem Statement
There are N gems. The color (represented as an integer) of the i-th gem is C_i and its value is V_i.
Choose K gems from these N gems. Here, the chosen gems must have at least M distinct colors.
Find the maximum possible total value of the chosen gems. (Such a choice is always possible in the given input.)
Constraints
- 1 \leq M \leq K \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq N
- 1 \leq V_i \leq 10^9
- There exist gems of at least M distinct colors.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K M C_1 V_1 C_2 V_2 \vdots C_N V_N
Output
Output the maximum possible total value of the chosen gems as an integer.
Sample Input 1
5 3 2 1 30 1 40 1 50 2 10 3 20
Sample Output 1
110
In this sample, choose three gems from five gems. The chosen gems must have at least two distinct colors.
Choosing gems 2, 3, 5 gives colors 1, 1, 3, which are two distinct colors. Their total value is 40 + 50 + 20 = 110, and this is the maximum possible value.
Sample Input 2
5 3 3 1 30 1 40 1 50 2 10 3 20
Sample Output 2
80
The gems and the number to choose are the same as in Sample Input 1, but the chosen gems must have at least three distinct colors.
Choosing gems 3, 4, 5 gives colors 1, 2, 3, which are three distinct colors. Their total value is 50 + 10 + 20 = 80, and this is the maximum possible value.
Sample Input 3
5 5 1 4 1000000000 5 1000000000 4 1000000000 5 1000000000 4 1000000000
Sample Output 3
5000000000
Beware of overflow.