Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
100 mL あたり A kcal のエネルギーを持つドリンクがあります。このドリンク B mL は何 kcal のエネルギーを持つでしょうか?
制約
- 0 \leq A, B \leq 1000
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを表す数値を出力せよ。
なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
45 200
出力例 1
90
100 mL あたり 45 kcal のエネルギーを持つドリンクがあり、このドリンク 200 mL は 90 kcal のエネルギーを持ちます。
入力例 2
37 450
出力例 2
166.5
答えは整数でないこともあります。
入力例 3
0 1000
出力例 3
0
入力例 4
50 0
出力例 4
0
Score : 100 points
Problem Statement
We have a drink that has A kilocalories of energy per 100 milliliters. How many kilocalories of energy does B milliliters of this drink have?
Constraints
- 0 \leq A, B \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B
Output
Print a number representing the answer.
Your output is considered correct when its absolute or relative error from our answer is at most 10^{-6}.
Sample Input 1
45 200
Sample Output 1
90
We have a drink that has 45 kilocalories of energy per 100 milliliters. 200 milliliters of this drink has 90 kilocalories of energy.
Sample Input 2
37 450
Sample Output 2
166.5
The answer may not be an integer.
Sample Input 3
0 1000
Sample Output 3
0
Sample Input 4
50 0
Sample Output 4
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
1 以上 N 以下の整数からなる長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。
A が (1, 2, \dots, N) の並び替えによって得られるかどうか判定してください。
制約
- 1 \leq N \leq 10^3
- 1 \leq A_i \leq N
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
A が (1, 2, \dots, N) の並び替えによって得られるなら Yes
、そうでないなら No
と出力せよ。
入力例 1
5 3 1 2 4 5
出力例 1
Yes
(3, 1, 2, 4, 5) は (1, 2, 3, 4, 5) を並び替えて得られるため、Yes
と出力します。
入力例 2
6 3 1 4 1 5 2
出力例 2
No
(1, 2, 3, 4, 5, 6) をどのように並び替えても (3, 1, 4, 1, 5, 2) にすることはできないので、No
と出力します。
入力例 3
3 1 2 3
出力例 3
Yes
入力例 4
1 1
出力例 4
Yes
Score : 200 points
Problem Statement
You are given a sequence of N integers between 1 and N (inclusive): A = (A_1, A_2, \dots, A_N).
Determine whether A is a permutation of (1, 2, \dots, N).
Constraints
- 1 \leq N \leq 10^3
- 1 \leq A_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
If A is a permutation of (1, 2, \dots, N), print Yes
; otherwise, print No
.
Sample Input 1
5 3 1 2 4 5
Sample Output 1
Yes
(3, 1, 2, 4, 5) is a permutation of (1, 2, 3, 4, 5), so we should print Yes
.
Sample Input 2
6 3 1 4 1 5 2
Sample Output 2
No
(3, 1, 4, 1, 5, 2) is not a permutation of (1, 2, 3, 4, 5, 6), so we should print No
.
Sample Input 3
3 1 2 3
Sample Output 3
Yes
Sample Input 4
1 1
Sample Output 4
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
数 X を Y 回掛けたものを「X の Y 乗」といい、\text{pow}(X,Y) で表します。 例えば \text{pow}(2,3)=2\times 2\times 2=8 です。
3 つの整数 A,B,C が与えられるので、\text{pow}(A,C) と \text{pow}(B,C) の大小を比較してください。
制約
- -10^9 \leq A,B \leq 10^9
- 1 \leq C \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
\text{pow}(A,C)< \text{pow}(B,C) なら <
を、\text{pow}(A,C)>\text{pow}(B,C) なら >
を、\text{pow}(A,C)=\text{pow}(B,C) なら =
を出力せよ。
入力例 1
3 2 4
出力例 1
>
\text{pow}(3,4)=81, \text{pow}(2,4)=16 です。
入力例 2
-7 7 2
出力例 2
=
\text{pow}(-7,2)=49, \text{pow}(7,2)=49 です。
入力例 3
-8 6 3
出力例 3
<
\text{pow}(-8,3)=-512, \text{pow}(6,3)=216 です。
Score : 300 points
Problem Statement
For a base number X, the product of multiplying it Y times is called X to the Y-th power and represented as \text{pow}(X, Y). For example, we have \text{pow}(2,3)=2\times 2\times 2=8.
Given three integers A, B, and C, compare \text{pow}(A,C) and \text{pow}(B,C) to determine which is greater.
Constraints
- -10^9 \leq A,B \leq 10^9
- 1 \leq C \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B C
Output
If \text{pow}(A,C)< \text{pow}(B,C), print <
; if \text{pow}(A,C)>\text{pow}(B,C), print >
; if \text{pow}(A,C)=\text{pow}(B,C), print =
.
Sample Input 1
3 2 4
Sample Output 1
>
We have \text{pow}(3,4)=81 and \text{pow}(2,4)=16.
Sample Input 2
-7 7 2
Sample Output 2
=
We have \text{pow}(-7,2)=49 and \text{pow}(7,2)=49.
Sample Input 3
-8 6 3
Sample Output 3
<
We have \text{pow}(-8,3)=-512 and \text{pow}(6,3)=216.
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の正整数列 A = (A_1, A_2, \dots, A_N) と Q 個のクエリが与えられます。
i \, (1 \leq i \leq Q) 番目のクエリでは、正整数 K_i が与えられるので、A_1, A_2, \dots, A_N のいずれとも異なる正整数のうち、小さい方から数えて K_i 番目のものを求めてください。
制約
- 1 \leq N, Q \leq 10^5
- 1 \leq A_1 < A_2 < \dots < A_N \leq 10^{18}
- 1 \leq K_i \leq 10^{18}
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \ldots A_N K_1 K_2 \vdots K_Q
出力
Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。
入力例 1
4 3 3 5 6 7 2 5 3
出力例 1
2 9 4
3, 5, 6, 7 のいずれとも異なる正整数を小さい順に並べると 1, 2, 4, 8, 9, 10, 11, \dots となります。 小さい方から 2 番目、5 番目、3 番目はそれぞれ 2, 9, 4 です。
入力例 2
5 2 1 2 3 4 5 1 10
出力例 2
6 15
Score : 400 points
Problem Statement
You are given a sequence of N positive integers: A = (A_1, A_2, \dots, A_N), and Q queries.
In the i-th query (1 \leq i \leq Q), given a positive integer K_i, find the K_i-th smallest integer among the positive integers that differ from all of A_1, A_2, \dots, A_N.
Constraints
- 1 \leq N, Q \leq 10^5
- 1 \leq A_1 < A_2 < \dots < A_N \leq 10^{18}
- 1 \leq K_i \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q A_1 A_2 \ldots A_N K_1 K_2 \vdots K_Q
Output
Print Q lines. The i-th line should contain the response to the i-th query.
Sample Input 1
4 3 3 5 6 7 2 5 3
Sample Output 1
2 9 4
The positive integers that differ from all of A_1, A_2, \dots, A_N are 1, 2, 4, 8, 9, 10, 11, \dots in ascending order. The second, fifth, and third smallest of them are 2, 9, and 4, respectively.
Sample Input 2
5 2 1 2 3 4 5 1 10
Sample Output 2
6 15
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
白いボール N 個と黒いボール M 個を横一列に並べる方法であって、次の条件を満たすものは何通りありますか?
- 各 i \, (1 \leq i \leq N + M) について左から i 個のボールのうち白いものの個数を w_i、黒いものの個数を b_i とおいたとき、全ての i について w_i \leq b_i + K が成り立つ。
ただし、答えは非常に大きくなることがあるので、(10^9 + 7) で割ったあまりを求めてください。
制約
- 0 \leq N, M \leq 10^6
- 1 \leq N + M
- 0 \leq K \leq N
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを出力せよ。(10^9 + 7) で割ったあまりを求めることに注意すること。
入力例 1
2 3 1
出力例 1
9
白いボール 2 個と黒いボール 3 個を並べる方法は 10 通りあり、白いボールを w
、黒いボールを b
で表すと以下のようになります。
wwbbb
wbwbb
wbbwb
wbbbw
bwwbb
bwbwb
bwbbw
bbwwb
bbwbw
bbbww
このうち、条件を満たさないのは wwbbb
のみです。左から 2 個のボールのうち白いものは 2 個、黒いものは 0 個ありますが、2 > 0 + K = 1 となっています。
入力例 2
1 0 0
出力例 2
0
条件を満たす並べ方が存在しないこともあります。
入力例 3
1000000 1000000 1000000
出力例 3
192151600
(10^9 + 7) で割ったあまりを出力することに注意してください。
Score : 500 points
Problem Statement
How many ways are there to arrange N white balls and M black balls in a row from left to right to satisfy the following condition?
- For each i (1 \leq i \leq N + M), let w_i and b_i be the number of white balls and black balls among the leftmost i balls, respectively. Then, w_i \leq b_i + K holds for every i.
Since the count can be enormous, find it modulo (10^9 + 7).
Constraints
- 0 \leq N, M \leq 10^6
- 1 \leq N + M
- 0 \leq K \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer. Be sure to find the count modulo (10^9 + 7).
Sample Input 1
2 3 1
Sample Output 1
9
There are 10 ways to arrange 2 white balls and 3 black balls in a row, as shown below, where w
and b
stand for a white ball and a black ball, respectively.
wwbbb
wbwbb
wbbwb
wbbbw
bwwbb
bwbwb
bwbbw
bbwwb
bbwbw
bbbww
Among them, wwbbb
is the only one that does not satisfy the condition. Here, there are 2 white balls and 0 black balls among the 2 leftmost balls, and we have 2 > 0 + K = 1.
Sample Input 2
1 0 0
Sample Output 2
0
There may be no way to satisfy the condition.
Sample Input 3
1000000 1000000 1000000
Sample Output 3
192151600
Be sure to print the count modulo (10^9 + 7).
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
H 行 W 列のグリッドがあり、上から r 行目、左から c 列目のマスを (r, c) と表します。
N 個の駒があり、i \, (1 \leq i \leq N) 個目の駒に対しては
- A_i \leq r \leq C_i かつ B_i \leq c \leq D_i を満たすいずれか一つのマス (r, c) に置く
- 置かない
のいずれかを選択することができます。ここで、二つの駒が同じ行や同じ列に存在するような置き方をすることはできません。
最大で何個の駒を置くことができるでしょうか?
制約
- 1 \leq H, W, N \leq 100
- 1 \leq A_i \leq C_i \leq H
- 1 \leq B_i \leq D_i \leq W
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
H W N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
出力
答えを出力せよ。
入力例 1
2 3 3 1 1 2 2 1 2 2 3 1 1 1 3
出力例 1
2
一つ目の駒をマス (1, 1) に、二つ目の駒をマス (2, 2) に置き、三つ目の駒は置かないようにすることで、2 個置くことができます。3 個置くことは不可能であるので、2 を出力します。
入力例 2
5 5 3 1 1 5 5 1 1 4 4 2 2 3 3
出力例 2
3
Score : 600 points
Problem Statement
There is a grid with H rows and W columns. Let (r, c) denote the square at the r-th row from the top and c-th column from the left.
We have N pieces. For the i-th piece, we can choose to do one of the following:
- Put it at a square (r, c) such that A_i \leq r \leq C_i and B_i \leq c \leq D_i.
- Do not put it on the grid.
However, we cannot put two pieces in the same row or the same column.
At most how many pieces can we put on the grid?
Constraints
- 1 \leq H, W, N \leq 100
- 1 \leq A_i \leq C_i \leq H
- 1 \leq B_i \leq D_i \leq W
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
Output
Print the answer.
Sample Input 1
2 3 3 1 1 2 2 1 2 2 3 1 1 1 3
Sample Output 1
2
By putting the first piece at (1, 1), the second piece at (2, 2), and not putting the third piece on the grid, we can put two pieces on the grid. We cannot put three, so we should print 2.
Sample Input 2
5 5 3 1 1 5 5 1 1 4 4 2 2 3 3
Sample Output 2
3