Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
明日の入学試験に合格するために、太郎くんはあと T 時間の勉強をする必要があります。
幸いにも、彼は今いる世界(世界A)の X 倍の速度で時間が進む世界Bへ世界跳躍(ワールドリープ)することができます。
世界Bで (X \times t) 時間進むと、世界Aでは t 時間進みます。
世界Bで T 時間勉強したとき、世界Aでは何時間進んでいるでしょうか。
制約
- 入力は全て整数である。
- 1 \leq T \leq 100
- 1 \leq X \leq 100
入力
入力は以下の形式で標準入力から与えられる。
T X
出力
世界Aでは何時間進んでいるかを出力せよ。
なお、想定解答との絶対誤差または相対誤差が 10^{-3} 以下であれば正解として扱われる。
入力例 1
8 3
出力例 1
2.6666666667
3 倍の速度で時間が進む世界Bで 8 時間勉強すると世界Aでは 2.6666... 時間進んでいます。
10^{-3} 以下の絶対誤差・相対誤差が許容されることに注意してください。
入力例 2
99 1
出力例 2
99.0000000000
入力例 3
1 100
出力例 3
0.0100000000
Score : 100 points
Problem Statement
In order to pass the entrance examination tomorrow, Taro has to study for T more hours.
Fortunately, he can leap to World B where time passes X times as fast as it does in our world (World A).
While (X \times t) hours pass in World B, t hours pass in World A.
How many hours will pass in World A while Taro studies for T hours in World B?
Constraints
- All values in input are integers.
- 1 \leq T \leq 100
- 1 \leq X \leq 100
Input
Input is given from Standard Input in the following format:
T X
Output
Print the number of hours that will pass in World A.
The output will be regarded as correct when its absolute or relative error from the judge's output is at most 10^{-3}.
Sample Input 1
8 3
Sample Output 1
2.6666666667
While Taro studies for eight hours in World B where time passes three times as fast, 2.6666... hours will pass in World A.
Note that an absolute or relative error of at most 10^{-3} is allowed.
Sample Input 2
99 1
Sample Output 2
99.0000000000
Sample Input 3
1 100
Sample Output 3
0.0100000000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
2 次元平面上に辺の長さがそれぞれ L_1, L_2, ..., L_N の N 角形(凸多角形でなくてもよい)が描けるかを判定してください。
ここで、次の定理を利用しても構いません。
定理 : 一番長い辺が他の N-1 辺の長さの合計よりも真に短い場合に限り、条件を満たす N 角形が描ける。
制約
- 入力は全て整数である。
- 3 \leq N \leq 10
- 1 \leq L_i \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N L_1 L_2 ... L_N
出力
条件を満たす N 角形が描けるなら Yes、そうでないなら No を出力せよ。
入力例 1
4 3 8 5 1
出力例 1
Yes
8 < 9 = 3 + 5 + 1 なので、定理より 2 次元平面上に条件を満たす N 角形が描けます。
入力例 2
4 3 8 4 1
出力例 2
No
8 \geq 8 = 3 + 4 + 1 なので、定理より 2 次元平面上に条件を満たす N 角形は描けません。
入力例 3
10 1 8 10 5 8 12 34 100 11 3
出力例 3
No
Score : 200 points
Problem Statement
Determine if an N-sided polygon (not necessarily convex) with sides of length L_1, L_2, ..., L_N can be drawn in a two-dimensional plane.
You can use the following theorem:
Theorem: an N-sided polygon satisfying the condition can be drawn if and only if the longest side is strictly shorter than the sum of the lengths of the other N-1 sides.
Constraints
- All values in input are integers.
- 3 \leq N \leq 10
- 1 \leq L_i \leq 100
Input
Input is given from Standard Input in the following format:
N L_1 L_2 ... L_N
Output
If an N-sided polygon satisfying the condition can be drawn, print Yes; otherwise, print No.
Sample Input 1
4 3 8 5 1
Sample Output 1
Yes
Since 8 < 9 = 3 + 5 + 1, it follows from the theorem that such a polygon can be drawn on a plane.
Sample Input 2
4 3 8 4 1
Sample Output 2
No
Since 8 \geq 8 = 3 + 4 + 1, it follows from the theorem that such a polygon cannot be drawn on a plane.
Sample Input 3
10 1 8 10 5 8 12 34 100 11 3
Sample Output 3
No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
数直線と N 個のコマを用いて 1 人でゲームを行います。
はじめ、これらのコマをそれぞれ好きな整数座標に置きます。
このとき、同じ座標に複数のコマを置いても構いません。
以下の移動を繰り返して、座標 X_1, X_2, ..., X_M の M 個の地点全てをいずれかのコマで訪れることが目的です。
移動: コマを 1 つ選び、そのコマの座標を x とする。そのコマを座標 x+1 もしくは座標 x-1 に移動する。
ただし、最初にコマを置いた座標はその時点で訪れたとみなします。
目的を達成するまでに移動を行う回数の最小値を求めてください。
制約
- 入力はすべて整数である。
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- -10^5 \leq X_i \leq 10^5
- X_1, X_2, ..., X_M は全て異なる。
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 X_2 ... X_M
出力
目的を達成するまでに移動を行う回数の最小値を出力せよ。
入力例 1
2 5 10 12 1 2 14
出力例 1
5
以下の手順で 5 回移動を行うと目的を達成でき、このときが最小です。
- はじめに 2 個のコマをそれぞれ座標 1, 座標 10 に置きます。
- 座標 1 のコマを座標 2 に移動します。
- 座標 10 のコマを座標 11 に移動します。
- 座標 11 のコマを座標 12 に移動します。
- 座標 12 のコマを座標 13 に移動します。
- 座標 13 のコマを座標 14 に移動します。
入力例 2
3 7 -10 -3 0 9 -100 2 17
出力例 2
19
入力例 3
100 1 -100000
出力例 3
0
Score : 300 points
Problem Statement
We will play a one-player game using a number line and N pieces.
First, we place each of these pieces at some integer coordinate.
Here, multiple pieces can be placed at the same coordinate.
Our objective is to visit all of the M coordinates X_1, X_2, ..., X_M with these pieces, by repeating the following move:
Move: Choose a piece and let x be its coordinate. Put that piece at coordinate x+1 or x-1.
Note that the coordinates where we initially place the pieces are already regarded as visited.
Find the minimum number of moves required to achieve the objective.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- -10^5 \leq X_i \leq 10^5
- X_1, X_2, ..., X_M are all different.
Input
Input is given from Standard Input in the following format:
N M X_1 X_2 ... X_M
Output
Find the minimum number of moves required to achieve the objective.
Sample Input 1
2 5 10 12 1 2 14
Sample Output 1
5
The objective can be achieved in five moves as follows, and this is the minimum number of moves required.
- Initially, put the two pieces at coordinates 1 and 10.
- Move the piece at coordinate 1 to 2.
- Move the piece at coordinate 10 to 11.
- Move the piece at coordinate 11 to 12.
- Move the piece at coordinate 12 to 13.
- Move the piece at coordinate 13 to 14.
Sample Input 2
3 7 -10 -3 0 9 -100 2 17
Sample Output 2
19
Sample Input 3
100 1 -100000
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 個の非負整数 A_1, A_2, ..., A_N および非負整数 K が与えられます。
0 以上 K 以下の整数 X に対して、f(X) = (X XOR A_1) + (X XOR A_2) + ... + (X XOR A_N) とします。
ここで、非負整数 a, b に対して a XOR b は a と b のビットごとの排他的論理和を表します。
f の最大値を求めてください。
XOR とは
整数 A, B のビットごとの排他的論理和 X は、以下のように定義されます。
- X を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 XOR 5 = 6 となります (二進数表記すると: 011 XOR 101 = 110)。
制約
- 入力は全て整数である
- 1 \leq N \leq 10^5
- 0 \leq K \leq 10^{12}
- 0 \leq A_i \leq 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 ... A_N
出力
f の最大値を出力せよ。
入力例 1
3 7 1 6 3
出力例 1
14
f(4) = (4 XOR 1) + (4 XOR 6) + (4 XOR 3) = 5 + 2 + 7 = 14 が最大です。
入力例 2
4 9 7 4 0 3
出力例 2
46
入力例 3
1 0 1000000000000
出力例 3
1000000000000
Score : 400 points
Problem Statement
You are given N non-negative integers A_1, A_2, ..., A_N and another non-negative integer K.
For a integer X between 0 and K (inclusive), let f(X) = (X XOR A_1) + (X XOR A_2) + ... + (X XOR A_N).
Here, for non-negative integers a and b, a XOR b denotes the bitwise exclusive OR of a and b.
Find the maximum value of f.
What is XOR?
The bitwise exclusive OR of a and b, X, is defined as follows:
- When X is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if, when written in base two, exactly one of A and B has 1 in the 2^k's place, and 0 otherwise.
For example, 3 XOR 5 = 6. (When written in base two: 011 XOR 101 = 110.)
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 0 \leq K \leq 10^{12}
- 0 \leq A_i \leq 10^{12}
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 ... A_N
Output
Print the maximum value of f.
Sample Input 1
3 7 1 6 3
Sample Output 1
14
The maximum value is: f(4) = (4 XOR 1) + (4 XOR 6) + (4 XOR 3) = 5 + 2 + 7 = 14.
Sample Input 2
4 9 7 4 0 3
Sample Output 2
46
Sample Input 3
1 0 1000000000000
Sample Output 3
1000000000000