実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
A 歳の高橋君が観覧車に乗ろうとしています。
この観覧車は、13 歳以上が乗るには B 円 (B は偶数) かかりますが、6 歳以上 12 歳以下の人はその半額で乗ることができ、 さらに 5 歳以下の人は無料で乗ることができます。
高橋君が観覧車に乗るには何円かかるかを求めてください。
制約
- 0 ≤ A ≤ 100
- 2 ≤ B ≤ 1000
- B は偶数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
高橋君が観覧車に乗るには何円かかるかを出力せよ。
入力例 1
30 100
出力例 1
100
現在 30 歳の高橋君は、観覧車に乗るのに 100 円かかります。
入力例 2
12 100
出力例 2
50
12 歳の高橋君は、観覧車に乗るのに 100 円の半額、すなわち 50 円かかります。
入力例 3
0 100
出力例 3
0
0 歳の高橋君は、観覧車に無料で乗ることができます。
Score : 100 points
Problem Statement
Takahashi, who is A years old, is riding a Ferris wheel.
It costs B yen (B is an even number) to ride the Ferris wheel if you are 13 years old or older, but children between 6 and 12 years old (inclusive) can ride it for half the cost, and children who are 5 years old or younger are free of charge. (Yen is the currency of Japan.)
Find the cost of the Ferris wheel for Takahashi.
Constraints
- 0 ≤ A ≤ 100
- 2 ≤ B ≤ 1000
- B is an even number.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the cost of the Ferris wheel for Takahashi.
Sample Input 1
30 100
Sample Output 1
100
Takahashi is 30 years old now, and the cost of the Ferris wheel is 100 yen.
Sample Input 2
12 100
Sample Output 2
50
Takahashi is 12 years old, and the cost of the Ferris wheel is the half of 100 yen, that is, 50 yen.
Sample Input 3
0 100
Sample Output 3
0
Takahashi is 0 years old, and he can ride the Ferris wheel for free.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
ある池に生えている藻類は、以下のように成長します。
西暦 i 年になる瞬間に生えている重さの合計を x_i グラムとすると、 i≥2000 に対して、以下の式が成り立ちます:
- x_{i+1} = rx_i - D
r, D, x_{2000} が与えられます。x_{2001}, ..., x_{2010} を計算し、順に出力してください。
制約
- 2 ≤ r ≤ 5
- 1 ≤ D ≤ 100
- D < x_{2000} ≤ 200
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
r D x_{2000}
出力
10 行出力せよ。i 行目 (1 ≤ i ≤ 10) には x_{2000+i} を整数で出力せよ。
入力例 1
2 10 20
出力例 1
30 50 90 170 330 650 1290 2570 5130 10250
例えば、x_{2001} = rx_{2000} - D = 2 \times 20 - 10 = 30 、 x_{2002} = rx_{2001} - D = 2 \times 30 - 10 = 50 です。
入力例 2
4 40 60
出力例 2
200 760 3000 11960 47800 191160 764600 3058360 12233400 48933560
Score : 200 points
Problem Statement
The development of algae in a pond is as follows.
Let the total weight of the algae at the beginning of the year i be x_i gram. For i≥2000, the following formula holds:
- x_{i+1} = rx_i - D
You are given r, D and x_{2000}. Calculate x_{2001}, ..., x_{2010} and print them in order.
Constraints
- 2 ≤ r ≤ 5
- 1 ≤ D ≤ 100
- D < x_{2000} ≤ 200
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
r D x_{2000}
Output
Print 10 lines. The i-th line (1 ≤ i ≤ 10) should contain x_{2000+i} as an integer.
Sample Input 1
2 10 20
Sample Output 1
30 50 90 170 330 650 1290 2570 5130 10250
For example, x_{2001} = rx_{2000} - D = 2 \times 20 - 10 = 30 and x_{2002} = rx_{2001} - D = 2 \times 30 - 10 = 50.
Sample Input 2
4 40 60
Sample Output 2
200 760 3000 11960 47800 191160 764600 3058360 12233400 48933560
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
N 枚の ID カードと M 個のゲートがあります。
i 番目のゲートは L_i, L_i+1, ..., R_i 番目の ID カードのうちどれか 1 枚を持っていれば通過できます。
1 枚だけで全てのゲートを通過できる ID カードは何枚あるでしょうか。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq L_i \leq R_i \leq N
入力
入力は以下の形式で標準入力から与えられる。
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
出力
1 枚だけで全てのゲートを通過できる ID カードの枚数を出力せよ。
入力例 1
4 2 1 3 2 4
出力例 1
2
以下のように、1 枚だけで全てのゲートを通過できる ID カードは 2 枚です。
- 1 番目の ID カードでは 2 番目のゲートを通過できません。
- 2 番目の ID カードでは全てのゲートを通過できます。
- 3 番目の ID カードでは全てのゲートを通過できます。
- 4 番目の ID カードでは 1 番目のゲートを通過できません。
入力例 2
10 3 3 6 5 7 6 9
出力例 2
1
入力例 3
100000 1 1 100000
出力例 3
100000
Score : 300 points
Problem Statement
We have N ID cards, and there are M gates.
We can pass the i-th gate if we have one of the following ID cards: the L_i-th, (L_i+1)-th, ..., and R_i-th ID cards.
How many of the ID cards allow us to pass all the gates alone?
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq L_i \leq R_i \leq N
Input
Input is given from Standard Input in the following format:
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
Output
Print the number of ID cards that allow us to pass all the gates alone.
Sample Input 1
4 2 1 3 2 4
Sample Output 1
2
Two ID cards allow us to pass all the gates alone, as follows:
- The first ID card does not allow us to pass the second gate.
- The second ID card allows us to pass all the gates.
- The third ID card allows us to pass all the gates.
- The fourth ID card does not allow us to pass the first gate.
Sample Input 2
10 3 3 6 5 7 6 9
Sample Output 2
1
Sample Input 3
100000 1 1 100000
Sample Output 3
100000
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
N 枚のカードがあり、i 番目のカードには整数 A_i が書かれています。
あなたは、j = 1, 2, ..., M について順に以下の操作を 1 回ずつ行います。
操作: カードを B_j 枚まで選ぶ(0 枚でもよい)。選んだカードに書かれている整数をそれぞれ C_j に書き換える。
M 回の操作終了後に N 枚のカードに書かれた整数の合計の最大値を求めてください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i, C_i \leq 10^9
- 1 \leq B_i \leq N
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_N B_1 C_1 B_2 C_2 \vdots B_M C_M
出力
M 回の操作終了後に N 枚のカードに書かれた整数の合計の最大値を出力せよ。
入力例 1
3 2 5 1 4 2 3 1 5
出力例 1
14
2 番目のカードに書かれた整数を 5 に書き換えることで、3 枚のカードに書かれた整数の合計が 5 + 5 + 4 = 14 となり、このときが最大です。
入力例 2
10 3 1 8 5 7 100 4 52 33 13 5 3 10 4 30 1 4
出力例 2
338
入力例 3
3 2 100 100 100 3 99 3 99
出力例 3
300
入力例 4
11 3 1 1 1 1 1 1 1 1 1 1 1 3 1000000000 4 1000000000 3 1000000000
出力例 4
10000000001
出力が 32 bit 整数型に収まらない場合があります。
Score : 400 points
Problem Statement
You have N cards. On the i-th card, an integer A_i is written.
For each j = 1, 2, ..., M in this order, you will perform the following operation once:
Operation: Choose at most B_j cards (possibly zero). Replace the integer written on each chosen card with C_j.
Find the maximum possible sum of the integers written on the N cards after the M operations.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i, C_i \leq 10^9
- 1 \leq B_i \leq N
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N B_1 C_1 B_2 C_2 \vdots B_M C_M
Output
Print the maximum possible sum of the integers written on the N cards after the M operations.
Sample Input 1
3 2 5 1 4 2 3 1 5
Sample Output 1
14
By replacing the integer on the second card with 5, the sum of the integers written on the three cards becomes 5 + 5 + 4 = 14, which is the maximum result.
Sample Input 2
10 3 1 8 5 7 100 4 52 33 13 5 3 10 4 30 1 4
Sample Output 2
338
Sample Input 3
3 2 100 100 100 3 99 3 99
Sample Output 3
300
Sample Input 4
11 3 1 1 1 1 1 1 1 1 1 1 1 3 1000000000 4 1000000000 3 1000000000
Sample Output 4
10000000001
The output may not fit into a 32-bit integer type.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
N 行 M 列のマス目があり、上から i 行目、左から j 列目のマスを (i, j) で表します。
このうち K マスに駒を 1 つずつ置きます。
K 個の駒がそれぞれ (x_1, y_1), (x_2, y_2), ..., (x_K, y_K) に置かれているとき、この配置のコストは
\sum_{i=1}^{K-1} \sum_{j=i+1}^K (|x_i - x_j| + |y_i - y_j|)
と計算されます。
駒の全ての配置のコストの総和を計算してください。この値は非常に大きくなることがあるので、10^9+7 で割った余りを出力してください。
ただし、2 つの駒の配置が異なるとは、片方の配置では駒があるがもう一方では駒が無いようなマスが存在する場合を表します。
制約
- 2 \leq N \times M \leq 2 \times 10^5
- 2 \leq K \leq N \times M
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
駒の全ての配置のコストの総和を 10^9+7 で割った余りを出力せよ。
入力例 1
2 2 2
出力例 1
8
駒の配置としては、以下の 6 通りが考えられます。
- ((1,1),(1,2)), コストは |1-1|+|1-2| = 1
- ((1,1),(2,1)), コストは |1-2|+|1-1| = 1
- ((1,1),(2,2)), コストは |1-2|+|1-2| = 2
- ((1,2),(2,1)), コストは |1-2|+|2-1| = 2
- ((1,2),(2,2)), コストは |1-2|+|2-2| = 1
- ((2,1),(2,2)), コストは |2-2|+|1-2| = 1
これらの総和は 8 です。
入力例 2
4 5 4
出力例 2
87210
入力例 3
100 100 5000
出力例 3
817260251
総和を 10^9+7 で割った余りを出力することに注意してください。
Score : 500 points
Problem Statement
We have a grid of squares with N rows and M columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. We will choose K of the squares and put a piece on each of them.
If we place the K pieces on squares (x_1, y_1), (x_2, y_2), ..., and (x_K, y_K), the cost of this arrangement is computed as:
\sum_{i=1}^{K-1} \sum_{j=i+1}^K (|x_i - x_j| + |y_i - y_j|)
Find the sum of the costs of all possible arrangements of the pieces. Since this value can be tremendous, print it modulo 10^9+7.
We consider two arrangements of the pieces different if and only if there is a square that contains a piece in one of the arrangements but not in the other.
Constraints
- 2 \leq N \times M \leq 2 \times 10^5
- 2 \leq K \leq N \times M
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the sum of the costs of all possible arrangements of the pieces, modulo 10^9+7.
Sample Input 1
2 2 2
Sample Output 1
8
There are six possible arrangements of the pieces, as follows:
- ((1,1),(1,2)), with the cost |1-1|+|1-2| = 1
- ((1,1),(2,1)), with the cost |1-2|+|1-1| = 1
- ((1,1),(2,2)), with the cost |1-2|+|1-2| = 2
- ((1,2),(2,1)), with the cost |1-2|+|2-1| = 2
- ((1,2),(2,2)), with the cost |1-2|+|2-2| = 1
- ((2,1),(2,2)), with the cost |2-2|+|1-2| = 1
The sum of these costs is 8.
Sample Input 2
4 5 4
Sample Output 2
87210
Sample Input 3
100 100 5000
Sample Output 3
817260251
Be sure to print the sum modulo 10^9+7.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
関数 f(x) があります。 はじめ、これは定数関数 f(x) = 0 です。
Q 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。
- 更新クエリ
1 a b
: 2整数 a, b が与えられるので、g(x) = f(x) + |x - a| + b として f(x) を g(x) で置き換える。 - 求値クエリ
2
: f(x) の最小値を与える x、および f(x) の最小値を出力する。ただし、そのような x が複数存在する場合には最小の x を答える。
この時、求値クエリにおいて出力すべき値は常に整数となることが示せます。 したがって、出力する際は小数点を用いず、整数で出力してください。
制約
- 入力は全て整数
- 1 \leq Q \leq 2 \times 10^5
- -10^9 \leq a, b \leq 10^9
- 1 番目のクエリは更新クエリである
入力
入力は以下の形式で標準入力から与えられる。
Q Query_1 : Query_Q
実例は入出力例 1 を参照せよ。
出力
求値クエリに対する応答を、クエリが与えられた順にそれぞれ 1 行で出力せよ。
各求値クエリに対する応答では、f(x) の最小値を与える最小の x、および f(x) の最小値を空白スペース区切りで出力すること。
入力例 1
4 1 4 2 2 1 1 -8 2
出力例 1
4 2 1 -3
1 つ目の求値クエリにおいて、f(x) = |x - 4| + 2 となっています。 したがって x = 4 において最小値 2 を取ります。
2 つ目の求値クエリでは、f(x) = |x - 1| + |x - 4| - 6 となっており、x が 1 \leq x \leq 4 を満たすならば最小値 -3 を与えます。この時、最小値を与える x が複数存在していますが、その中で最小の値である 1 を出力してください。
入力例 2
4 1 -1000000000 1000000000 1 -1000000000 1000000000 1 -1000000000 1000000000 2
出力例 2
-1000000000 3000000000
Score : 600 points
Problem Statement
There is a function f(x), which is initially a constant function f(x) = 0.
We will ask you to process Q queries in order. There are two kinds of queries, update queries and evaluation queries, as follows:
- An update query
1 a b
: Given two integers a and b, let g(x) = f(x) + |x - a| + b and replace f(x) with g(x). - An evaluation query
2
: Print x that minimizes f(x), and the minimum value of f(x). If there are multiple such values of x, choose the minimum such value.
We can show that the values to be output in an evaluation query are always integers, so we ask you to print those values as integers without decimal points.
Constraints
- All values in input are integers.
- 1 \leq Q \leq 2 \times 10^5
- -10^9 \leq a, b \leq 10^9
- The first query is an update query.
Input
Input is given from Standard Input in the following format:
Q Query_1 : Query_Q
See Sample Input 1 for an example.
Output
For each evaluation query, print a line containing the response, in the order in which the queries are given.
The response to each evaluation query should be the minimum value of x that minimizes f(x), and the minimum value of f(x), in this order, with space in between.
Sample Input 1
4 1 4 2 2 1 1 -8 2
Sample Output 1
4 2 1 -3
In the first evaluation query, f(x) = |x - 4| + 2, which attains the minimum value of 2 at x = 4.
In the second evaluation query, f(x) = |x - 1| + |x - 4| - 6, which attains the minimum value of -3 when 1 \leq x \leq 4. Among the multiple values of x that minimize f(x), we ask you to print the minimum, that is, 1.
Sample Input 2
4 1 -1000000000 1000000000 1 -1000000000 1000000000 1 -1000000000 1000000000 2
Sample Output 2
-1000000000 3000000000