Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋くんは今、白い服を着ています。
高橋くんは、白い服を着た次の日には黒い服を、黒い服を着た次の日には白い服を着ます。
N 日後には何色の服を着るでしょうか？
制約
- N は整数である
- 1 \leq N \leq 30
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 日後に白い服を着るなら White を、黒い服を着るなら Black を出力せよ。
入力例 1
2
出力例 1
White
高橋くんは 1 日後に黒い服を、 2 日後に白い服を着ます。
入力例 2
5
出力例 2
Black
Score : 100 points
Problem Statement
Takahashi is wearing white now.
He wears black on the day after he wears white, and he wears white on the day after he wears black.
What color will he wear N days later?
Constraints
- N is an integer.
- 1 \leq N \leq 30
Input
Input is given from Standard Input in the following format:
N
Output
If he will wear white N days later, print White; if he will wear black, print Black.
Sample Input 1
2
Sample Output 1
White
Takahashi will wear black one day later and wear white two days later.
Sample Input 2
5
Sample Output 2
Black
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
何も書かれていない黒板があります。 高橋くんは N 回の操作を行い、黒板に整数を書きます。
i 回目の操作では、 A_i 以上 B_i 以下の整数すべてを 1 個ずつ、合計 B_i - A_i + 1 個の整数を書きます。
N 回の操作を終えたときの、黒板に書かれた整数の合計を求めてください。
制約
- 入力はすべて整数
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq B_i \leq 10^6
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 \vdots A_N B_N
出力
N 回の操作を終えたときの、黒板に書かれた整数の合計を出力せよ。
入力例 1
2 1 3 3 5
出力例 1
18
1 回目の操作では、黒板に 1, 2, 3 を書きます。
2 回目の操作では、黒板に 3, 4, 5 を書きます。
黒板に書かれた整数の合計は 1+2+3+3+4+5=18 です。
入力例 2
3 11 13 17 47 359 44683
出力例 2
998244353
入力例 3
1 1 1000000
出力例 3
500000500000
Score : 200 points
Problem Statement
We have a blackboard with nothing written on it. Takahashi will do N operations to write integers on it.
In the i-th operation, he will write each integer from A_i through B_i once, for a total of B_i - A_i + 1 integers.
Find the sum of the integers written on the blackboard after the N operations.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq B_i \leq 10^6
Input
Input is given from Standard Input in the following format:
N A_1 B_1 \vdots A_N B_N
Output
Print the sum of the integers written on the blackboard after the N operations.
Sample Input 1
2 1 3 3 5
Sample Output 1
18
In the 1-st operation, he will write 1, 2, and 3 on the blackboard.
In the 2-nd operation, he will write 3, 4, and 5 on the blackboard.
The sum of the integers written is 1+2+3+3+4+5=18.
Sample Input 2
3 11 13 17 47 359 44683
Sample Output 2
998244353
Sample Input 3
1 1 1000000
Sample Output 3
500000500000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
無限に広い 2 次元平面の上に N 個の点があります。
i 番目の点は (x_i,y_i) にあります。
N 個の点の中の相異なる 3 点であって、同一直線上にあるものは存在するでしょうか？
制約
- 入力はすべて整数
- 3 \leq N \leq 10^2
- |x_i|, |y_i| \leq 10^3
- i \neq j ならば (x_i, y_i) \neq (x_j, y_j)
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 \vdots x_N y_N
出力
同一直線上にある相異なる 3 点が存在するなら Yes を、存在しないなら No を出力せよ。
入力例 1
4 0 1 0 2 0 3 1 1
出力例 1
Yes
(0, 1), (0, 2), (0, 3) の 3 点は直線 x = 0 上にあります。
入力例 2
14 5 5 0 1 2 5 8 0 2 1 0 0 3 6 8 6 5 9 7 9 3 4 9 2 9 8 7 2
出力例 2
No
入力例 3
9 8 2 2 3 1 3 3 7 1 0 8 8 5 6 9 7 0 1
出力例 3
Yes
Score : 300 points
Problem Statement
We have N points on a two-dimensional infinite coordinate plane.
The i-th point is at (x_i,y_i).
Is there a triple of distinct points lying on the same line among the N points?
Constraints
- All values in input are integers.
- 3 \leq N \leq 10^2
- |x_i|, |y_i| \leq 10^3
- If i \neq j, (x_i, y_i) \neq (x_j, y_j).
Input
Input is given from Standard Input in the following format:
N x_1 y_1 \vdots x_N y_N
Output
If there is a triple of distinct points lying on the same line, print Yes; otherwise, print No.
Sample Input 1
4 0 1 0 2 0 3 1 1
Sample Output 1
Yes
The three points (0, 1), (0, 2), (0, 3) lie on the line x = 0.
Sample Input 2
14 5 5 0 1 2 5 8 0 2 1 0 0 3 6 8 6 5 9 7 9 3 4 9 2 9 8 7 2
Sample Output 2
No
Sample Input 3
9 8 2 2 3 1 3 3 7 1 0 8 8 5 6 9 7 0 1
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
1 〜 9 の数字のみからなる数字列 S が与えられます。
蜂の高橋くんは、 8 の倍数が好きです。
高橋くんは、数字列 S を並び替えて 8 の倍数を作ろうとしています。
8 の倍数を作れるかどうか判定してください。
制約
- 1 \leq |S| \leq 2 \times 10^5
- S の各文字は
1〜9のいずれか
入力
入力は以下の形式で標準入力から与えられる。
S
出力
数字列 S を並び替えて 8 の倍数を作れるなら Yes を、作れないなら No を出力せよ。
入力例 1
1234
出力例 1
Yes
例えば、 1234 を並べ替えて 1432 にすると 8 の倍数になります。
入力例 2
1333
出力例 2
No
1333 をどう並べ替えても 8 の倍数を作ることはできません。
入力例 3
8
出力例 3
Yes
Score : 400 points
Problem Statement
Given is a digit sequence S consisting of the digits from 1 through 9.
Takahashi, the bee, loves multiples of 8.
He is trying to make a multiple of 8 by permuting the digit sequence S.
Determine whether it is possible.
Constraints
- 1 \leq |S| \leq 2 \times 10^5
- Each character of S is one of the digits from
1through9.
Input
Input is given from Standard Input in the following format:
S
Output
If it is possible to make a multiple of 8 by permuting the digit sequence S, print Yes; otherwise, print No.
Sample Input 1
1234
Sample Output 1
Yes
For example, permuting 1234 into 1432 results in a multiple of 8.
Sample Input 2
1333
Sample Output 2
No
There is no way to permute 1333 into a multiple of 8.
Sample Input 3
8
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 人の児童がおり、 i 番目の児童の身長は H_i です。 N は奇数です。
今から、先生であるあなたを含めた N+1 人で 2 人 1 組を \large\frac{N+1}2 ペア組みます。
あなたの目標は、それぞれのペアの身長の差の合計を最小化することです。
すなわち、 i 番目のペアの身長の組を (x_i, y_i) としたとき、 \displaystyle \sum_{i=1}^{(N+1)/2}|x_i-y_i| を最小化したいです。
あなたには M 個の変身形態があり、 i 番目の変身形態での身長は W_i です。
あなたの変身形態とペアの組み方を工夫することで、それぞれのペアの身長の差の合計が最小でいくつにできるか求めてください。
制約
- 入力はすべて整数
- 1 \leq N, M \leq 2 \times 10^5
- N は奇数
- 1 \leq H_i \leq 10^9
- 1 \leq W_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M H_1 \dots H_N W_1 \dots W_M
出力
変身形態とペアの組み方を工夫したときの、それぞれのペアの身長の差の合計の最小値を出力せよ。
入力例 1
5 3 1 2 3 4 7 1 3 8
出力例 1
3
身長 8 の変身形態を選び、身長が (1, 2), (3, 4), (7, 8) のペアを作ると最小になります。
入力例 2
7 7 31 60 84 23 16 13 32 96 80 73 76 87 57 29
出力例 2
34
入力例 3
15 10 554 525 541 814 661 279 668 360 382 175 833 783 688 793 736 496 732 455 306 189 207 976 73 567 759
出力例 3
239
Score : 500 points
Problem Statement
There are N children in a kindergarten. The height of the i-th child is H_i. Here, N is an odd number.
You, the teacher, and these children - N+1 people in total - will make \large\frac{N+1}2 pairs.
Your objective is to minimize the sum of the differences in height over those pairs. That is, you want to minimize \displaystyle \sum_{i=1}^{(N+1)/2}|x_i-y_i|, where (x_i, y_i) is the pair of heights of people in the i-th pair.
You have M forms that you can transform into. Your height in the i-th form is W_i.
Find the minimum possible sum of the differences in height over all pairs, achieved by optimally choosing your form and making pairs.
Constraints
- All values in input are integers.
- 1 \leq N, M \leq 2 \times 10^5
- N is an odd number.
- 1 \leq H_i \leq 10^9
- 1 \leq W_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N M H_1 \dots H_N W_1 \dots W_M
Output
Print the minimum possible sum of the differences in height over all pairs, achieved by optimally choosing your form and making pairs.
Sample Input 1
5 3 1 2 3 4 7 1 3 8
Sample Output 1
3
The minimum is minimized by choosing the form with the height 8 and making pairs with heights (1, 2), (3, 4), and (7, 8).
Sample Input 2
7 7 31 60 84 23 16 13 32 96 80 73 76 87 57 29
Sample Output 2
34
Sample Input 3
15 10 554 525 541 814 661 279 668 360 382 175 833 783 688 793 736 496 732 455 306 189 207 976 73 567 759
Sample Output 3
239
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
xy 平面上に 2 直線 y=-100,\ y=100 で囲まれた通路があります。
この通路の中の -100 < x < 100 の部分に N 本の大きさの無視できる釘が打たれており、 i 本目の釘の座標は (x_i, y_i) です。
高橋くんは実数 r \ (0 < r \leq 100) を 1 つ選び、半径 r の円を中心が (-10^9, 0) に位置するように置きます。
その後、円を (-10^9, 0) から (10^9, 0) まで移動させます。
このとき、円は通路の境界や釘が円の内部に入らないような範囲で連続的に動かすことができるものとします。
円を (10^9, 0) まで動かせるような最大の r を求めてください。
制約
- 入力はすべて整数
- 1 \leq N \leq 100
- |x_i|, |y_i| < 100
- i \neq j ならば (x_i, y_i) \neq (x_j, y_j)
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 \vdots x_N y_N
出力
円を (10^9, 0) まで動かせるような最大の r を出力せよ。
なお、想定解答との絶対誤差または相対誤差が 10^{-4} 以下であれば正解として扱われる。
入力例 1
2 0 -40 0 40
出力例 1
40
r=40 の円を図のように y=0 に沿って動かすと、 (-10^9, 0) から (10^9, 0) まで移動させることができます。
x=0 のときにちょうど 2 つの点と接しますが、円の内部には入っていないため問題ありません。
r を 40 より大きくすると、円の中心を (10^9, 0) まで動かすことができなくなるため、 r=40 が最大になります。
入力例 2
4 0 -10 99 10 0 91 99 -91
出力例 2
50.5
入力例 3
10 -90 40 20 -30 0 -90 10 -70 80 70 -90 30 -20 -80 10 90 50 30 60 -70
出力例 3
33.541019662496845446
入力例 4
10 65 -90 -34 -2 62 99 42 -13 47 -84 84 87 16 -78 56 35 90 8 90 19
出力例 4
35.003571246374276203
Score : 600 points
Problem Statement
On the xy-plane, we have a passage surrounded by the two lines y=-100 and y=100.
In the part of this passage with -100 < x < 100, there are N negligibly small nails. The coordinates of the i-th nail are (x_i, y_i).
Takahashi will choose a real number r \ (0 < r \leq 100) and put a circle of radius r so that its center is at (-10^9, 0).
Then, he will move the circle from (-10^9, 0) to (10^9, 0).
Here, he continuously moves the circle so that the boundaries of the passage or the nails do not penetrate the interior of the circle.
Find the maximum possible value of r such that it is possible to move the circle to (10^9, 0).
Constraints
- All values in input are integers.
- 1 \leq N \leq 100
- |x_i|, |y_i| < 100
- If i \neq j, (x_i, y_i) \neq (x_j, y_j).
Input
Input is given from Standard Input in the following format:
N x_1 y_1 \vdots x_N y_N
Output
Print the maximum possible value of r such that it is possible to move the circle to (10^9, 0). Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-4}.
Sample Input 1
2 0 -40 0 40
Sample Output 1
40
As shown in the figure, we can move the circle with r=40 from (-10^9, 0) to (10^9, 0) by moving it along y=0.
When x=0, the circle exactly touches the two nails, which is fine since they do not penetrate the interior of the circle.
Any value of r greater than 40 makes it impossible to move the circle to (10^9, 0), so the maximum possible value is r=40.
Sample Input 2
4 0 -10 99 10 0 91 99 -91
Sample Output 2
50.5
Sample Input 3
10 -90 40 20 -30 0 -90 10 -70 80 70 -90 30 -20 -80 10 90 50 30 60 -70
Sample Output 3
33.541019662496845446
Sample Input 4
10 65 -90 -34 -2 62 99 42 -13 47 -84 84 87 16 -78 56 35 90 8 90 19
Sample Output 4
35.003571246374276203