Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
高橋君は以下のような基準で人を 3 種類のタイプ(A, B, Cのいずれか)に分類することにしました。
- BMIが 20 未満ならばA
- BMIが 20 以上 25 未満ならばB
- BMIが 25 以上ならばC
なお、身長が h m、体重が w kgの人のBMIは \frac{w}{h^2} と表せます。
身長が H cm、体重が W kgの人がどのタイプに分類されるかを判定してください。
制約
- 100 \leq H \leq 200
- 30 \leq W \leq 200
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
出力
身長が H cm、体重が W kgの人が分類されるタイプ(A, B, Cのいずれか)を出力してください。
入力例 1
170 55
出力例 1
A
身長が 170 cm、体重が 55 kgの人のBMIは 19.03114... であり、20 未満なのでAに分類されます。
入力例 2
100 200
出力例 2
C
BMIが 200 であり、25 以上なのでCに分類されます。
Problem Statement
Takahashi is going to classify a person into the following three types (A, B, or C):
- A: Their BMI is strictly less than 20.
- B: Their BMI is 20 or greater, and strictly less than 25.
- C: Their BMI is 25 or greater.
The BMI of a person of height h meters and weight w kilograms is represented as \frac{w}{h^2}.
Determine the type of a person of height H centimeters and weight W kilograms.
Constraints
- 100 \leq H \leq 200
- 30 \leq W \leq 200
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W
Output
Print the type (A, B, or C) of a person of height H centimeters and weight W kilograms.
Sample Input 1
170 55
Sample Output 1
A
The BMI of a person of height 170 centimeters and weight 55 kilograms is 19.03114..., which is less than 20. Thus, they are classified as type A.
Sample Input 2
100 200
Sample Output 2
C
Their BMI is 200, which is greater than or equal to 25, so they are classified as type C.
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
N 個の文字列の組 S = (S_1,S_2,\ldots,S_N) が与えられます。
各 S_i は Perfect
, Great
, Good
, Bad
, Miss
のいずれかです。
S が Perfect
のみからなるならば All Perfect
を、
そうでなく Perfect
と Great
のみからなるならば Full Combo
を、
これらの条件をいずれも満たさないならば Failed
を出力してください。
制約
- 1\leq N \leq 100
- N は整数
- S_i は
Perfect
,Great
,Good
,Bad
,Miss
のいずれか
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
3 Perfect Great Perfect
出力例 1
Full Combo
S は Perfect
のみからなるわけではありませんが、Perfect
と Great
のみからなります。
よって Full Combo
を出力します。
入力例 2
1 Perfect
出力例 2
All Perfect
入力例 3
5 Bad Miss Perfect Great Good
出力例 3
Failed
Problem Statement
You are given a tuple of N strings: S = (S_1,S_2,\ldots,S_N).
Each S_i is one of Perfect
, Great
, Good
, Bad
, and Miss
.
If S only contains Perfect
, print All Perfect
;
otherwise, if it consists of Perfect
and Great
, print Full Combo
;
otherwise, print Failed
.
Constraints
- 1\leq N \leq 100
- N is an integer.
- S_i is one of
Perfect
,Great
,Good
,Bad
, andMiss
.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
3 Perfect Great Perfect
Sample Output 1
Full Combo
S does not consist only of Perfect
, but it consists of Perfect
and Great
.
Thus, Full Combo
should be printed.
Sample Input 2
1 Perfect
Sample Output 2
All Perfect
Sample Input 3
5 Bad Miss Perfect Great Good
Sample Output 3
Failed
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
高橋君は N 枚のカードを持っています。
i = 1, 2, \ldots, N について、高橋君が持っている i 枚目のカードには 1 以上 10 以下の整数 A_i が書かれています。
x = 1, 2, \ldots, 10 について、整数 x が書かれたカードは 1 枚ごとに P_x 円に換金できます。
高橋君が持っているカード全てを換金するときに得られる合計金額を出力してください。
制約
- 1 \leq N \leq 10
- 1 \leq A_i \leq 10
- 1 \leq P_x \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N P_1 P_2 \ldots P_{10}
出力
答えを整数として出力せよ。
入力例 1
4 3 10 7 3 31 41 59 26 53 58 97 93 23 84
出力例 1
299
- 1 枚目のカードには整数 3 が書かれています。よって、P_3 = 59 円に換金できます。
- 2 枚目のカードには整数 10 が書かれています。よって、P_{10} = 84 円に換金できます。
- 3 枚目のカードには整数 7 が書かれています。よって、P_7 = 97 円に換金できます。
- 4 枚目のカードには整数 3 が書かれています。よって、P_3 = 59 円に換金できます。
よって、高橋君が持っているカード全てを換金するときに得られる合計金額は、 59 + 84 + 97 + 59 = 299 円です。
入力例 2
10 7 7 7 7 7 7 7 7 7 7 1 1 1 1 1 1 1000000000 1 1 1
出力例 2
10000000000
答えが 32 bit整数型に収まらないこともあります。
Problem Statement
Takahashi has N cards.
For i = 1, 2, \ldots, N, his i-th card has an integer A_i between 1 and 10 written on it.
For x = 1, 2, \ldots, 10, a card with the integer x written on it can be changed into P_x yen (currency in Japan).
Find the total amount of money Takahashi can get by changing all his cards into money.
Constraints
- 1 \leq N \leq 10
- 1 \leq A_i \leq 10
- 1 \leq P_x \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N P_1 P_2 \ldots P_{10}
Output
Print the answer as an integer.
Sample Input 1
4 3 10 7 3 31 41 59 26 53 58 97 93 23 84
Sample Output 1
299
- The 1-st card has an integer 3 written on it, which is worth P_3 = 59 yen.
- The 2-nd card has an integer 10 written on it, which is worth P_{10} = 84 yen.
- The 3-rd card has an integer 7 written on it, which is worth P_7 = 97 yen.
- The 4-th card has an integer 3 written on it, which is worth P_3 = 59 yen.
Thus, he can change all his cards into money to get a total of 59 + 84 + 97 + 59 = 299 yen.
Sample Input 2
10 7 7 7 7 7 7 7 7 7 7 1 1 1 1 1 1 1000000000 1 1 1
Sample Output 2
10000000000
The answer may not fit into a 32-bit integer type.
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
あなたはあるWebサービスの機能を一年間利用しようとしています。
まず、あなたは会員登録を行い、無料会員、一般会員、プレミアム会員のいずれかになる必要があります。
- 無料会員には無料でなれます。無料会員は毎月 3 回まで無料で機能を利用できますが、4 回目以降は利用のたびに A 円を支払う必要があります。
- 一般会員になるには登録時に一年分の会費として B 円を支払う必要があります。一般会員は毎月 50 回まで無料で機能を利用できますが、51 回目以降は利用のたびに A 円を支払う必要があります。
- プレミアム会員になるには登録時に一年分の会費として C 円を支払う必要があります。プレミアム会員は何回でも無料で機能を利用できます。
あなたは i=1,2,\ldots,12 に対し、今月から数えて i 番目の月に x_i 回機能を利用することが分かっています。
会員登録と機能の利用で支払うことになる合計金額の最小値を求めてください。
制約
- 1 \leq A \leq 1000
- 1 \leq B \lt C \leq 1000
- 1 \leq x_i \leq 1000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A B C x_1 \ldots x_{12}
出力
答えが X 円のとき、X を整数として出力せよ。
入力例 1
5 20 30 1 2 3 4 5 6 7 8 9 10 11 12
出力例 1
20
無料会員になると、1,2,3 月は 3 回までしか機能を利用しないので支払いが必要ありませんが、4 月以降は 4 回以上利用するのでそれぞれ 1,2,\ldots,9 回 A 円の支払いが発生し、合計で 225 円支払うことになります。
一般会員になると、初めに一年分の会費として 20 円を支払う必要がありますが、どの月も機能を 50 回以下しか利用しないためこれ以外の支払いはありません。
プレミアム会員になると、初めに一年分の会費として 30 円を支払う必要があります。プレミアム会員は何回でも無料で機能を利用できるので、これ以外の支払いはありません。
以上より、一般会員になった場合に支払う 20 円が最小です。
入力例 2
5 20 30 100 100 100 100 100 100 100 100 100 100 100 100
出力例 2
30
入力例 3
1 999 1000 50 50 50 50 50 50 50 50 50 50 50 50
出力例 3
564
Problem Statement
You are going to use a feature of a web service for a year.
First of all, you must sign up to become a free member, a standard member, or a premium member.
- You can become a free member with no charge. A free member can use the feature at most three times a month, but subsequent usage costs A yen each time.
- To become a standard member, you need to pay an annual fee of B yen on registration. A standard member can use the feature up to 50 times a month, with each additional use costing A yen.
- To become a premium member, you need to pay an annual fee of C yen on registration. A premium member can use the feature any number of times for free.
For i=1,2,\ldots,12, you are going to use the feature x_i times in the i-th month.
Find the minimum total cost required for the registration and using the feature.
Constraints
- 1 \leq A \leq 1000
- 1 \leq B \lt C \leq 1000
- 1 \leq x_i \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A B C x_1 \ldots x_{12}
Output
If the answer is X yen, print the integer X.
Sample Input 1
5 20 30 1 2 3 4 5 6 7 8 9 10 11 12
Sample Output 1
20
Suppose that you become a free member. In the first three months, you will use the features at most three times a month, and no payment is required; for the remaining months, you will use it more than three times a month, so you need to pay A yen once, twice, \ldots, and nine times, for a total of 225 yen.
Now consider becoming a standard member. You need to pay the annual fee of 20 yen on registration, but you will use the feature no more than 50 times a month, so no further payment is required.
If you become a premium member, you first need to pay an annual fee of 30 yen. But a premium member can use the feature as many times as they want, so no more payment is required.
Therefore, the minimum cost is 20 yen, when you become a standard member.
Sample Input 2
5 20 30 100 100 100 100 100 100 100 100 100 100 100 100
Sample Output 2
30
Sample Input 3
1 999 1000 50 50 50 50 50 50 50 50 50 50 50 50
Sample Output 3
564
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
与えられた文字列を、同じ文字が連続する区間に分割して、文字と連続する長さの組からなる列で表現することを 連長圧縮 と呼びます。
例えば S = AAABCCCC
を連長圧縮すると (\mathrm{A}, 3), (\mathrm{B}, 1), (\mathrm{C}, 4) になります。
英大文字からなる文字列 S が与えられます。S を連長圧縮した列を出力形式に従って出力してください。
制約
- S は英大文字からなる長さ 1 以上 2 \times 10^5 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S を連長圧縮した列を (c_1, l_1), (c_2, l_2), \dots, (c_k, l_k) とする。このとき、以下の形式で答えを出力せよ。
c_1 l_1 c_2 l_2 \dots c_k l_k
入力例 1
ABBCCC
出力例 1
A 1 B 2 C 3
S = ABBCCC
を連長圧縮すると (\mathrm{A}, 1), (\mathrm{B}, 2), (\mathrm{C}, 3) になります。
入力例 2
AAAAAAAAAAAAA
出力例 2
A 13
入力例 3
ABCDE
出力例 3
A 1 B 1 C 1 D 1 E 1
Problem Statement
Applying the run-length encoding to a string is achieved by splitting the string into chunks, each consisting of the same character, and representing them as a sequence of pairs of the characters and the lengths.
For example, applying the run-length encoding to S = AAABCCCC
yields (\mathrm{A}, 3), (\mathrm{B}, 1), (\mathrm{C}, 4).
Given a string S consisting of uppercase English letters, apply the run-length encoding to S and print the resulting sequence in the specified format.
Constraints
- S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of uppercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Let (c_1, l_1), (c_2, l_2), \dots, (c_k, l_k) be the sequence obtained by applying the run-length encoding to S. Print it in the following format.
c_1 l_1 c_2 l_2 \dots c_k l_k
Sample Input 1
ABBCCC
Sample Output 1
A 1 B 2 C 3
Applying the run-length encoding to S = ABBCCC
yields (\mathrm{A}, 1), (\mathrm{B}, 2), (\mathrm{C}, 3).
Sample Input 2
AAAAAAAAAAAAA
Sample Output 2
A 13
Sample Input 3
ABCDE
Sample Output 3
A 1 B 1 C 1 D 1 E 1
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
頂点に 1 から N までの番号がついた N 頂点の根付き二分木があります。根は頂点 1 で、頂点 i (2 \leq i \leq N) の親は頂点 p_i です。すべての頂点は 子を持たないか、ちょうど 2 個の子を持つか のいずれかです。
また、頂点 i には S_i が書きこまれています。S_i は整数または文字で、二分木の葉の頂点には整数が、葉でない頂点には +
または x
が書かれています。
あなたは次の 2 種類の操作を自由な順番で操作を行えなくなるまで繰り返します。
- 自身に
+
が書かれていて、両方の子の頂点に整数が書かれている頂点を選ぶ。子に書かれた整数をそれぞれ a, b として、頂点に書かれている+
を整数 a+b に書き換える。そして、子の頂点を取り除く。 - 自身に
x
が書かれていて、両方の子の頂点に整数が書かれている頂点を選ぶ。子に書かれた整数をそれぞれ a, b として、頂点に書かれているx
を整数 a \times b に書き換える。そして、子の頂点を取り除く。
操作を終了した時点で、整数が書かれた頂点がちょうど 1 個残ります。その頂点に書かれた整数を 998244353 で割った余りを求めてください。(どのような順番で操作しても残った頂点に書かれている整数は同じになることが証明できます。)
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq p_i \leq i - 1 (2 \leq i \leq N)
- 全ての頂点は p_2, p_3, \dots, p_N にちょうど 0 回または 2 回現れる
- S_i は次の 2 種類のいずれか
- 頂点 i が葉の頂点のとき、S_i は 1 以上 10^8 以下の整数
- 頂点 i が葉でない頂点のとき、S_i は
+
またはx
入力
入力は以下の形式で標準入力から与えられる。
N p_2 p_3 \dots p_N S_1 S_2 \dots S_N
出力
答えを出力せよ。
入力例 1
5 1 1 2 2 + x 3 2 5
出力例 1
13
以下の手順により、13 が書かれた頂点が残るので答えは 13 です。
- 頂点 2 を選ぶ。頂点 2 に書かれている
x
を 2 \times 5 = 10 に書き換えて、頂点 4 と頂点 5 を削除する。 - 頂点 1 を選ぶ。頂点 1 に書かれている
+
を 10 + 3 = 13 に書き換えて、頂点 2 と頂点 3 を削除する。
入力例 2
7 1 2 1 4 4 2 x + 31415 + 92653 58979 32384
出力例 2
689770791
998244353 で割った余りを求めることに注意してください。
Problem Statement
There is a N-vertex rooted binary tree whose vertices are numbered 1 through N. The root is vertex 1, and the parent of vertex i (2 \leq i \leq N) is vertex p_i. Every vertex has exactly zero or two children.
Vertex i has S_i written on it. S_i is either an integer or a character. If the vertex is a leaf, S_i is an integer; otherwise, it is either +
or x
.
You will repeatedly perform the following two kinds of operations in any order, until you are unable to do so.
- Choose a vertex, with
+
written on it, whose children both have integers written on them. Let a and b be those integers. Replace the+
written on the vertex with the integer a+b, and remove the children. - Choose a vertex, with
x
written on it, whose children both have integers written on them. Let a and b be those integers. Replace thex
written on the vertex with the integer a \times b, and remove the children.
Once you are done, there will be only one remaining vertex with an integer written on it. Find this integer, modulo 998244353. (One can prove that the integer written on the final vertex is unique regardless of the order of the operations.)
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq p_i \leq i - 1 (2 \leq i \leq N)
- Every vertex occurs exactly zero times or twice in p_2, p_3, \dots, p_N.
- S_i is:
- an integer between 1 and 10^8, inclusive, if vertex i is a leaf;
- either
+
orx
if vertex i is not a leaf.
Input
The input is given from Standard Input in the following format:
N p_2 p_3 \dots p_N S_1 S_2 \dots S_N
Output
Print the answer.
Sample Input 1
5 1 1 2 2 + x 3 2 5
Sample Output 1
13
By the following steps, there will be left a vertex with 13 written on it, so the answer is 13.
- Choose vertex 2. Replace the
x
written on vertex 2 with 2 \times 5 = 10, and remove vertices 4 and 5. - Choose vertex 1. Replace the
+
written on vertex 1 with 10 + 3 = 13, and remove vertices 2 and 3.
Sample Input 2
7 1 2 1 4 4 2 x + 31415 + 92653 58979 32384
Sample Output 2
689770791
Make sure to find the answer modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と呼びます。
各マスには英小文字が書かれています。(i, j) に書かれている文字は G_{i, j} です。
長さ N の文字列 S が与えられます。マスの列 (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N) であって次の条件を満たすものは存在しますか?存在する場合はYes
を、そうでない場合は No
を出力してください。
- (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N) は全て互いに異なる。
- (a_i, b_i) と (a_{i+1}, b_{i+1}) は 8 方向に隣接している。言い換えると \max(\vert a_i - a_{i+1} \vert, \vert b_i - b_{i+1} \vert) = 1 である。
- (a_i, b_i) に書かれた文字は S の i 文字目と一致する。
制約
- 1 \leq H, W \leq 10
- G_{i, j} は英小文字
- 1 \leq N \leq 5
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W G_{1,1}G_{1,2}\dots G_{1,W} G_{2,1}G_{2,2}\dots G_{2,W} \vdots G_{H,1}G_{H,2}\dots G_{H,W} N S
出力
問題文の条件を満たすマスの列が存在する場合はYes
を、そうでない場合は No
を出力せよ。
入力例 1
3 3 ekz sza znz 5 snake
出力例 1
Yes
マスの列 (2, 1), (3, 2), (2, 3), (1, 2), (1, 1) は問題文の条件を全て満たします。よって答えは Yes
です。
入力例 2
2 5 qwert asdfg 4 awrg
出力例 2
No
入力例 3
3 3 abc zbc zzc 5 abcba
出力例 3
No
Problem Statement
There is a grid with H horizontal rows and W vertical columns. We denote by (i,j) the cell in the i-th row from the top and j-th column from the left.
Each cell has a lowercase English letter written on it. The letter written on (i, j) is G_{i, j}.
You are given a string S of length N. Is there a sequence of cells (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N) that satisfies the following conditions? Print Yes
if there is, and No
otherwise.
- (a_1, b_1), (a_2, b_2), \dots, and (a_N, b_N) are pairwise distinct.
- (a_i, b_i) and (a_{i+1}, b_{i+1}) are adjacent in one of the eight directions. In other words, \max(\vert a_i - a_{i+1} \vert, \vert b_i - b_{i+1} \vert) = 1.
- The letter written on (a_i, b_i) coincides with the i-th character of S.
Constraints
- 1 \leq H, W \leq 10
- G_{i, j} is a lowercase English letter.
- 1 \leq N \leq 5
- S is a length-N string consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
H W G_{1,1}G_{1,2}\dots G_{1,W} G_{2,1}G_{2,2}\dots G_{2,W} \vdots G_{H,1}G_{H,2}\dots G_{H,W} N S
Output
Print Yes
if there is a conforming sequence of cells; print No
otherwise.
Sample Input 1
3 3 ekz sza znz 5 snake
Sample Output 1
Yes
The sequence of cells (2, 1), (3, 2), (2, 3), (1, 2), (1, 1) satisfies all the conditions in the problem statement, so the answer is Yes
.
Sample Input 2
2 5 qwert asdfg 4 awrg
Sample Output 2
No
Sample Input 3
3 3 abc zbc zzc 5 abcba
Sample Output 3
No
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
ある大学では N 個の科目が開講されています。i 番目の科目は履修するのに必要な労力が a_i で、時間割上で b_i 番目の時間に講義が行われ、履修すると c_i 単位を取得できます。
あなたはこれらの科目からいくつかを履修して合計で M 単位以上を取得する必要があります。ただし、時間割上で同じ時間に講義が行われる科目を同時に履修することはできません。
M 単位以上を取得することができるならばそのために必要な労力の合計の最小値を、できないならば -1
を出力してください。
制約
- 1 \leq N, M \leq 5000
- 1 \leq a_i,b_i,c_i \leq 5000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 c_1 \vdots a_N b_N c_N
出力
M 単位以上を取得することができるならばそのために必要な労力の合計の最小値を、できないならば -1
を出力せよ。
入力例 1
3 4 3 1 2 4 1 2 5 2 2
出力例 1
8
1,3 番目の科目を履修すると、必要な労力の合計が 8 になります。これが最小値です。
なお、1,2 番目の科目は同じ時間に講義が行われるので同時に履修することができません。
入力例 2
3 100 1 100 1 1 200 1 1 300 1
出力例 2
-1
すべての科目を履修しても 100 単位以上を取得することができません。
入力例 3
2 100 10 5 99 10 5 99
出力例 3
-1
2 つの科目は同じ時間に講義が行われるので同時に履修することができず、100 単位以上を取得することができません。
入力例 4
10 522 4575 1426 4445 3772 81 3447 629 3497 2202 2775 4325 3982 4784 3417 2156 1932 902 728 3537 3857 739 1918 4211 4679 3506 3340 1568 1868 16 2940
出力例 4
629
Problem Statement
There are N courses in a university. The i-th course requires an effort of a_i, is scheduled at the b_i-th time slot, and counts for c_i credits.
You need to take some of the courses to earn a total of M credits. However, you cannot take multiple courses scheduled at the same time slot.
If you can earn M or more credits, print the minimum total effort required to do so; otherwise, print -1
.
Constraints
- 1 \leq N, M \leq 5000
- 1 \leq a_i,b_i,c_i \leq 5000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M a_1 b_1 c_1 \vdots a_N b_N c_N
Output
If you can earn M or more credits, print the minimum total effort required to do so; otherwise, print -1
.
Sample Input 1
3 4 3 1 2 4 1 2 5 2 2
Sample Output 1
8
If you take the 1-st and 3-rd courses, the total effort required is 8, which is the minimum.
Note that you cannot take both the 1-st and 2-nd courses, because they are scheduled at the same slot.
Sample Input 2
3 100 1 100 1 1 200 1 1 300 1
Sample Output 2
-1
Even if you take all the courses, you cannot earn 100 or more credits.
Sample Input 3
2 100 10 5 99 10 5 99
Sample Output 3
-1
The two courses are scheduled at the same time slot, so you cannot earn 100 or more credits.
Sample Input 4
10 522 4575 1426 4445 3772 81 3447 629 3497 2202 2775 4325 3982 4784 3417 2156 1932 902 728 3537 3857 739 1918 4211 4679 3506 3340 1568 1868 16 2940
Sample Output 4
629
Time Limit: 6 sec / Memory Limit: 1024 MiB
問題文
N 個の文字列 S_1,\ldots,S_N が与えられます。
以下の条件をともに満たす整数の組 (i,j) の個数を求めてください。
- 1 \leq i,j \leq N
- S_i が S_j の部分列である
部分列とは
文字列の部分列とは、文字列から 0 個以上の位置の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことをいいます。 例えば、a
, pe
, apple
は apple
の部分列ですが、ea
, hoge
は違います。
制約
- 1 \leq N \leq 10^5
- N は整数
- S_i は英小文字のみからなる長さが 1 以上 5 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 \vdots S_N
出力
答えを出力せよ。
入力例 1
3 ps past post
出力例 1
5
1 \leq i,j \leq N を満たす整数組 (i,j) は 9 個ありますが、そのうち以下の 5 個において S_i が S_j の部分列です。
- (i,j)=(1,1)
- (i,j)=(1,2)
- (i,j)=(1,3)
- (i,j)=(2,2)
- (i,j)=(3,3)
入力例 2
5 a aa aaa aaaa aaaaa
出力例 2
15
入力例 3
2 hoge hoge
出力例 3
4
Problem Statement
You are given N strings S_1,\ldots,S_N.
Find the number of integer pairs (i,j) such that:
- 1 \leq i,j \leq N, and
- S_i is a subsequence of S_j.
What is subsequence?
A subsequence of a string is a string obtained by removing characters at zero or more positions and concatenating the remaining characters without changing their order. For example,a
, pe
, and apple
are subsequences of apple
, but ea
and hoge
are not.
Constraints
- 1 \leq N \leq 10^5
- N is an integer.
- S_i is a string of length between 1 and 5, inclusive, consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N S_1 \vdots S_N
Output
Print the answer.
Sample Input 1
3 ps past post
Sample Output 1
5
Among nine pairs of integers (i,j) such that 1 \leq i,j \leq N, the following five satisfy the condition that S_i is a subsequence of S_j.
- (i,j)=(1,1)
- (i,j)=(1,2)
- (i,j)=(1,3)
- (i,j)=(2,2)
- (i,j)=(3,3)
Sample Input 2
5 a aa aaa aaaa aaaaa
Sample Output 2
15
Sample Input 3
2 hoge hoge
Sample Output 3
4
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
カフェに、客 1 、客 2 、\ldots 、客 N と番号づけられた N 人の客が来店しました。
i = 1, 2, \ldots, N について、客 i は時刻 A_i から時刻 B_i まで(時刻 A_i と時刻 B_i も含む)カフェに滞在しました。
また、これら N 人の他には、カフェに来店した客はいませんでした。
Q 個の時刻 t_1, t_2, \ldots, t_Q について、 その時刻にカフェにいた客の人数を出力してください。
制約
- 1 \leq N, Q \leq 2 \times 10^5
- 1 \leq A_i \lt B_i \leq 10^9
- 1 \leq t_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N Q t_1 t_2 \vdots t_Q
出力
Q 行出力せよ。 i = 1, 2, \ldots, Q について、i 行目には時刻 t_i にカフェにいた客の人数を出力せよ。
入力例 1
4 2 4 4 5 3 6 4 5 7 1 2 3 4 5 6 7
出力例 1
0 1 2 4 3 1 0
- 時刻 1 には、カフェには客は誰もいません。
- 時刻 2 には、カフェに 客 1 の 1 人の客のみがいます。
- 時刻 3 には、カフェに 客 1, 3 の 2 人の客がいます。
- 時刻 4 には、カフェに 客 1, 2, 3, 4 の 4 人の客がいます。
- 時刻 5 には、カフェに 客 2, 3, 4 の 3 人の客がいます。
- 時刻 6 には、カフェに 客 3 の 1 人の客のみがいます。
- 時刻 7 には、カフェには客は誰もいません。
入力例 2
1 1 1000000000 2 1000000000 1
出力例 2
1 1
Problem Statement
N customers visited a cafe: customer 1, customer 2, \ldots, and customer N.
For i = 1, 2, \ldots, N, customer i stayed in the cafe from time A_i to time B_i (including time A_i and time B_i).
No customers other than these N visited the cafe.
For each of Q times t_1, t_2, \ldots, t_Q, find the number of customers who were staying in the cafe at that time.
Constraints
- 1 \leq N, Q \leq 2 \times 10^5
- 1 \leq A_i \lt B_i \leq 10^9
- 1 \leq t_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N Q t_1 t_2 \vdots t_Q
Output
Print Q lines. For i = 1, 2, \ldots, Q, the i-th line should contain the number of customers who were staying in the cafe at time t_i.
Sample Input 1
4 2 4 4 5 3 6 4 5 7 1 2 3 4 5 6 7
Sample Output 1
0 1 2 4 3 1 0
- At time 1, no one was in the cafe.
- At time 2, one customer was in the cafe: customer 1.
- At time 3, two customers were in the cafe: customers 1 and 3.
- At time 4, four customers were in the cafe: customers 1, 2, 3, and 4.
- At time 5, three customers were in the cafe: customers 2, 3, and 4.
- At time 6, one customer was in the cafe: customer 3.
- At time 7, no one was in the cafe.
Sample Input 2
1 1 1000000000 2 1000000000 1
Sample Output 2
1 1
Time Limit: 3 sec / Memory Limit: 1024 MiB
問題文
数字と ?
からなる長さ N の文字列 S が与えられます。
全ての ?
を数字に置き換えて以下の値を 10 の倍数にすることができるか判定し、可能な場合は ?
の置き換え方を 1 通り求めてください。
- \displaystyle \sum^{N}_{i=1} i \times ( S の i 文字目を 1 桁の整数とみなした時の値 )
制約
- N は 1 以上 2 \times 10^5 以下の整数
- S は数字と
?
からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
問題文中の条件を満たす置き換え方が存在しない場合、 No
と 1 行に出力してください。
そうでない場合、以下の形式に従い置き換え方を出力してください。
Yes T
まず、 1 行目に Yes
と出力してください。
次に、 2 行目に ?
を問題文中の条件を満たすように置き換えた文字列 T を出力してください。
入力例 1
5 935?0
出力例 1
Yes 93550
935?0
の 4 文字目の ?
を置き換えることを考えます。
- 4 文字目の
?
を 5 に置き換えた時、置き換えた後の文字列は T=93550
となります。- 1 \times 9 + 2 \times 3 + 3 \times 5 + 4 \times 5 + 5 \times 0 = 50 となり、これは確かに 10 の倍数です。
他にも、 4 文字目の ?
を 0 に置き換えた 93500
も問題文中の条件を満たします。
入力例 2
5 1?3?5
出力例 2
No
1?3?5
の 2 つの ?
を数字に置き換える方法は全部で 100 通りありますが、どのように置き換えても問題文中の条件を満たすことができません。
入力例 3
1 0
出力例 3
Yes 0
文字列 0
は置き換えるべき ?
を含みませんが、 1 \times 0 = 0 は元々 10 の倍数です。
Problem Statement
You are given a length-N string S consisting of digits and ?
.
Determine if one can replace each occurrence of ?
with a digit so that the following value is a multiple of 10. If it is possible, find one such replacement.
- \displaystyle \sum^{N}_{i=1} i \times (the i-th character of S interpreted as a one-digit integer).
Constraints
- N is an integer between 1 and 2 \times 10^5, inclusive.
- S is a length-N string consisting of digits and
?
.
Input
The input is given from Standard Input in the following format:
N S
Output
Print No
in a single line if there is no conforming replacement.
Otherwise, print a replacement in the following format.
Yes T
The first line should contain Yes
.
The second line should contain a string T obtained by a replacement that satisfies the condition in the problem statement.
Sample Input 1
5 935?0
Sample Output 1
Yes 93550
Consider what digit should replace the 4-th character ?
of 935?0
.
- If the 4-th character
?
is replaced by 5, the resulting string is T=93550
.- 1 \times 9 + 2 \times 3 + 3 \times 5 + 4 \times 5 + 5 \times 0 = 50, which is indeed a multiple of 10.
Alternatively, we can also satisfy the condition in the problem statement by replacing the 4-th character ?
with 0, thus yielding 93500
.
Sample Input 2
5 1?3?5
Sample Output 2
No
There are 100 ways to replace the two occurrences of ?
in 1?3?5
, but none of them satisfies the condition in the problem statement.
Sample Input 3
1 0
Sample Output 3
Yes 0
While the string 0
does not contain ?
to replace, 1 \times 0 = 0 is already a multiple of 10.
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
1 から N までの番号がついた N 個の都市があります。
すべての相異なる都市同士の間には双方向に通行できる有料道路があります。また、すべての道路に使用できる割引券があり、これを使用すると通行料を安くすることができます。
都市 i と都市 j (i \lt j) を結ぶ道路の通行料は a_{i,j} 円で、割引券を使うと b_{i,j} 円になります。(b_{i,j} \lt a_{i,j})
i \lt j を満たすすべての都市の組 (i, j) に対して次の値を求めてください。
- 割引券を合計 1 回以下使用して都市 i から都市 j へ移動するのに必要な最小の金額。
制約
- 2 \leq N \leq 300
- 1 \leq b_{i,j} \lt a_{i,j} \leq 10^4 (i \lt j)
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_{1,2} a_{1,3} \dots a_{1,N} a_{2,3} \dots a_{2,N} \vdots a_{N-1,N} b_{1,2} b_{1,3} \dots b_{1,N} b_{2,3} \dots b_{2,N} \vdots b_{N-1,N}
出力
答えを以下の形式で出力せよ。ここで c_{i,j} は 割引券を合計 1 回以下使用して都市 i から都市 j へ移動するのに必要な最小の金額を意味する。
c_{1,2} c_{1,3} \dots c_{1,N} c_{2,3} \dots c_{2,N} \vdots c_{N-1,N}
入力例 1
4 4 8 5 6 8 3 1 6 1 5 2 1
出力例 1
1 4 1 5 2 1
例えば都市 1 から都市 3 へ割引券を合計 1 回以下使用して移動する場合は、次のように移動すれば 4 円で移動することができて、これが最小です。
- 都市 1 から都市 4 へ割引券を利用して 1 円掛けて移動する。
- 都市 4 から都市 3 へ割引券を利用せずに 3 円掛けて移動する。
入力例 2
6 2255 36 196 3623 6579 681 183 473 8830 7549 743 8216 1078 9 224 105 3 1 810 15 7 125 11 3 50 6 1781 537 4 85
出力例 2
43 3 1 42 10 7 12 11 3 37 6 46 94 4 85
Problem Statement
There are N cities numbered 1 through N.
Every pair of different cities is connected by a bidirectional toll road. There is a voucher that can be used on any road to get a discount on the toll.
The toll of the road between city i and city j (i \lt j) is a_{i,j} yen; with the voucher, it is b_{i,j} yen. (b_{i,j} \lt a_{i,j})
Find the following value for all pairs of cities (i, j) such that i \lt j:
- the minimum amount of money required to travel from city i to city j, using the voucher at most once in total.
Constraints
- 2 \leq N \leq 300
- 1 \leq b_{i,j} \lt a_{i,j} \leq 10^4 (i \lt j)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N a_{1,2} a_{1,3} \dots a_{1,N} a_{2,3} \dots a_{2,N} \vdots a_{N-1,N} b_{1,2} b_{1,3} \dots b_{1,N} b_{2,3} \dots b_{2,N} \vdots b_{N-1,N}
Output
Print the answer in the following format. Here, c_{i,j} denotes the minimum amount of money required to travel from city i to city j, using the voucher at most once.
c_{1,2} c_{1,3} \dots c_{1,N} c_{2,3} \dots c_{2,N} \vdots c_{N-1,N}
Sample Input 1
4 4 8 5 6 8 3 1 6 1 5 2 1
Sample Output 1
1 4 1 5 2 1
For example, you can travel from city 1 to city 3 using the voucher at most once for a total cost of 4 yen, which is the minimum, as follows:
- Travel from city 1 to city 4 for a cost of 1 yen, using the voucher.
- Travel from city 4 to city 3 for a cost of 3 yen, without using the voucher.
Sample Input 2
6 2255 36 196 3623 6579 681 183 473 8830 7549 743 8216 1078 9 224 105 3 1 810 15 7 125 11 3 50 6 1781 537 4 85
Sample Output 2
43 3 1 42 10 7 12 11 3 37 6 46 94 4 85
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
座標平面上に 2 つの長方形 A,B があり、一定の速度でそれぞれ平行移動します。
いずれの長方形もつねに各辺は x 軸, y 軸のいずれかに平行であり、時刻 t において、
長方形 A の左下の頂点は (U_1\times t+P_1,V_1\times t+Q_1), 右上の頂点は (U_1\times t+R_1,V_1\times t+S_1) 、
長方形 B の左下の頂点は (U_2\times t+P_2,V_2\times t+Q_2), 右上の頂点は (U_2\times t+R_2,V_2\times t+S_2) にあります。
ここで、(U_1,V_1)\neq (U_2, V_2) である事が保証されます。
時刻 t=0 から t=10^{100} までの間で長方形 A,B が重なっている、すなわち 2 つの長方形の重なりが正の面積を持つ時間の長さを求めてください。
制約
- -1000\leq P_i<R_i\leq 1000
- -1000\leq Q_i<S_i\leq 1000
- -1000\leq U_i,V_i\leq 1000
- (U_1,V_1)\neq (U_2, V_2)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
P_1 Q_1 R_1 S_1 U_1 V_1 P_2 Q_2 R_2 S_2 U_2 V_2
出力
2 つの長方形の重なりが正の面積を持つ時間の長さを出力せよ。
正しい値との相対誤差または絶対誤差が 10^{-7} 以下であれば正答とみなされる。
入力例 1
0 0 1 1 2 0 2 -1 4 2 1 0
出力例 1
3.000000000000000
時刻 t=1 から t=4 まで、かつその時に限り 2 つの長方形は重なっています。 よって重なっている時間の長さは 3 です。
入力例 2
0 0 5 5 1 1 2 2 3 3 0 -1
出力例 2
1.500000000000000
入力例 3
-5 -5 0 5 0 0 0 0 1 1 0 1
出力例 3
0.000000000000000
2 つの長方形が辺や頂点のみを共有している状態では長方形の重なりの面積は 0 であるため、2 つの長方形が重なっているとは判定されない事に注意してください。
Problem Statement
There are two rectangles A and B on a coordinate plane, each moving at a constant velocity in parallel translation.
Each side of each rectangle is parallel to x or y axis. At time t,
the bottom-left and top-right vertices of rectangle A are at (U_1\times t+P_1,V_1\times t+Q_1) and (U_1\times t+R_1,V_1\times t+S_1), respectively;
the bottom-left and top-right vertices of rectangle B are at (U_2\times t+P_2,V_2\times t+Q_2) and (U_2\times t+R_2,V_2\times t+S_2), respectively.
Here, it is guaranteed that (U_1,V_1)\neq (U_2, V_2).
Between time 0 and time t=10^{100}, find the duration that rectangles A and B overlap; in other words, the intersection of the two rectangles has a positive area.
Constraints
- -1000\leq P_i<R_i\leq 1000
- -1000\leq Q_i<S_i\leq 1000
- -1000\leq U_i,V_i\leq 1000
- (U_1,V_1)\neq (U_2, V_2)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
P_1 Q_1 R_1 S_1 U_1 V_1 P_2 Q_2 R_2 S_2 U_2 V_2
Output
Print the duration that the intersection of the two rectangles has a positive area.
Your answer is considered correct if the relative or absolute error from the correct value is at most 10^{-7}.
Sample Input 1
0 0 1 1 2 0 2 -1 4 2 1 0
Sample Output 1
3.000000000000000
The two rectangles overlap between time t=1 and t=4, but not otherwise. Thus, the duration of overlap is 3.
Sample Input 2
0 0 5 5 1 1 2 2 3 3 0 -1
Sample Output 2
1.500000000000000
Sample Input 3
-5 -5 0 5 0 0 0 0 1 1 0 1
Sample Output 3
0.000000000000000
Note that when two rectangles only share sides or vertices, the area of the intersection is 0, so they are not considered overlapping.
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
高橋君はソフトウェア 1、ソフトウェア 2、\cdots、ソフトウェア N と番号づけられた N 個のソフトウェアのアップデートを行おうとしており、
ソフトウェア i (1\leq i\leq N) のアップデートには T_i だけ時間がかかります。
高橋君はこれらのアップデートを行う順番を指定する事ができ、
コンピュータは時刻 0 にアップデートを始め、 与えられた順番に従って 1 つずつアップデートを実行していきます。
すなわち、高橋君が i (1\leq i\leq N) 番目にソフトウェア p_i のアップデートを実行するように指定した時、コンピュータは次のように動きます。
- 時刻 (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}) から時刻 (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}+T_{p_k}) までソフトウェア p_k のアップデートを行う。
高橋君はアップデートの実行中に状態を確認した時、 N 個のアップデート全体にかかる時間をなるべく正しく推定する事ができるように順番を定めたいと考えました。
ここで、アップデートの実行中は現在何番目のアップデートを実行しているかしか知ることができないため、
高橋君は時刻 t に k 番目のアップデートが行われていた時、アップデート全体にかかる時間を f(t)=\frac{N}{k-0.5}\cdot t と見積ります。
なお、i 番目のアップデートが始まるちょうどその時刻には i 番目のアップデートを実行しているとみなされます。
すなわち、時刻 0 には 1 番目のアップデートが実行されているとみなされ、
ちょうど i 番目のアップデートが終了し i+1 番目のアップデートが開始する時刻には i+1 番目のアップデートが実行されている
とみなされます。
アップデート全体にかかる時間を S\left(=\displaystyle\sum_{i=1}^N T_i\right) とし、 高橋君がアップデート全体にかかる時間を見積もる時刻 t が 0 以上 S 未満の実数から連続一様分布に従って選ばれる時、 \lvert f(t)-S\rvert の期待値が最小となるように高橋君が順番を指定した時の \lvert f(t)-S\rvert の期待値を求めてください。
制約
- 2\leq N\leq 18
- 1\leq T_i\leq 10^6
- 入力は整数
入力
入力は以下の形式で標準入力から与えられる。
N T_1 T_2 \ldots T_N
出力
高橋君が問題文のように順番を指定した時の \lvert f(t)-S\rvert の期待値を出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
2 3 7
出力例 1
3.066666666666667
アップデートにかかる時間は S=3+7=10 となります。
高橋君がアップデートの順番をソフトウェア 1\to 2 と指定した時、時刻 t (0\leq t<10) に状態を確認した時のアップデート全体にかかる推定時間 f(t) は、
- 0\leq t< 3 において、f(t)=\frac{2}{1-0.5}\cdot t=4t,
- 3\leq t< 10 において、f(t)=\frac{2}{2-0.5}\cdot t=\frac{4}{3}t
となります。t が 0\leq t\lt 10 の範囲から一様な確率で選ばれる時、\lvert f(t)-S\rvert の期待値は \frac{46}{15}=3.066\cdots となり、 この時が最小となります。
入力例 2
3 3 1 1
出力例 2
1.420000000000000
高橋君がアップデートの順番をソフトウェア 1\to 3\to 2 と指定した時、 \lvert f(t)-S\rvert の期待値は最小となります。
Problem Statement
Takahashi is going to update N apps numbered app 1, app 2, \ldots, and app N.
Updating app i (1\leq i\leq N) costs T_i units of time.
Takahashi can choose the order of the apps to update.
Starting at time 0, his computer updates the apps one by one in the specified order.
Formally, if he lets the i-th (1\leq i\leq N) app to be updated be app p_i, the computer behaves as follows:
- updates app p_k from time (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}) to time (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}+T_{p_k}).
He wants to choose the order so that, when he checks the progress during the updates, he can estimate the total duration required for the entire updates as correctly as possible.
However, during the updates, he only has access to a single integer k, which indicates that the k-th update is underway.
If he recognizes that the k-th update is underway at time t, he estimates that the duration of the entire updates is f(t)=\frac{N}{k-0.5}\cdot t.
Here, at the time when the i-th update starts, he recognizes that the i-th update is underway.
Specifically, at time 0 he regards that the 1-st update is underway;
at the time when the i-th update finishes and (i+1)-th update starts, he regards that the (i+1)-th update is
underway.
Let S\left(=\displaystyle\sum_{i=1}^N T_i\right) be the total duration for the entire updates. Suppose he estimates the duration of the entire updates at time t, which is a random real variable chosen from 0 (inclusive) to t (exclusive) uniformly at random. Find the minimum expected value of \lvert f(t)-S\rvert when he chooses the permutation to minimize it.
Constraints
- 2\leq N\leq 18
- 1\leq T_i\leq 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T_1 T_2 \ldots T_N
Output
Print the expected value of \lvert f(t)-S\rvert when he chooses the permutation to minimize it.
Your answer is considered correct if the absolute or relative error from the true value is at most 10^{-6}.
Sample Input 1
2 3 7
Sample Output 1
3.066666666666667
The total duration of the entire updates is S=3+7=10.
When he specify the updating order of the apps to be 1\to 2, his estimated duration f(t) of the entire updates if he checks the progress at time t (0\leq t<10) is:
- f(t)=\frac{2}{1-0.5}\cdot t=4t if 0\leq t< 3;
- f(t)=\frac{2}{2-0.5}\cdot t=\frac{4}{3}t if 3\leq t< 10.
When t is chosen from the range 0\leq t\lt 10 uniformly at random, the expected value of \lvert f(t)-S\rvert is \frac{46}{15}=3.066\cdots, which is the minimum possible value.
Sample Input 2
3 3 1 1
Sample Output 2
1.420000000000000
The expected value of \lvert f(t)-S\rvert is minimum if he specifies the updating order of the apps to be 1\to 3\to 2.
Time Limit: 4 sec / Memory Limit: 1024 MiB
問題文
長さ N の整数列 A = (A_1,A_2,\ldots,A_N) が与えられます。 この数列に対する操作を以下のように定めます。
- 操作:A の要素を 1 つ選んで、 1 または -1 を加算する。
クエリが Q 個与えられるので、与えられた順番に処理してください。クエリは次の 2 種類のいずれかです。
1 k d
: A_k に d を加算する (d は 1 または -1)。2 x
: A の要素を全て x にするために必要な操作回数の最小値を求める。ただし、実際には操作は行わない。
制約
- 入力は全て整数
- 1\leq N,Q \leq 2\times 10^5
- |A_i| \leq 10^9
- 1 番目の形式のクエリについて、1\leq k \leq N
- 1 番目の形式のクエリについて、d は 1 または -1
- 2 番目の形式のクエリについて、|x| \leq 10^9
- 2 番目の形式のクエリが少なくとも 1 つ与えられる
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N Q \mathrm{query}_1 \mathrm{query}_2 \vdots \mathrm{query}_Q
ただし、\mathrm{query}_i は i 個目のクエリを表しており、次の形式のいずれかで与えられる。
1 k d
2 x
出力
2 番目の形式のクエリの回数を q 回として、q 行出力せよ。 j\ (1\leq j \leq q) 行目には、2 番目の形式のクエリのうち j 個目のものに対する答えを出力せよ。
入力例 1
4 3 5 7 2 4 2 4 1 1 1 1 2 -1 2 4
出力例 1
7 5
最初、A = (3,5,7,2) です。
- 1 番目のクエリでは、A_1 に 1 を足す操作を 1 回、A_2 に -1 を足す操作を 1 回、 A_3 に -1 を足す操作を 3 回、A_4 に 1 を足す操作を 2 回行うのが最適です。よって、1+1+3+2=7 を出力します。
- 2 番目のクエリでは、A_1 に 1 が足されます。A=(4,5,7,2) になります。
- 3 番目のクエリでは、A_2 に -1 が足されます。A=(4,4,7,2) になります。
- 4 番目のクエリでは、A_3 に -1 を足す操作を 3 回、A_4 に 1 を足す操作を 2 回行うのが最適です。よって、3+2=5 を出力します。
入力例 2
10 403 -397 -538 -996 496 -499 80 768 714 -346 10 1 4 -1 2 -362 2 389 2 -470 1 2 -1 2 -58 1 5 1 1 10 1 2 -88 1 3 1
出力例 2
5270 5856 5632 5239 5239
Problem Statement
You are given an integer sequence A = (A_1,A_2,\ldots,A_N) of length N. We define an operation against this sequence as follows.
- Operation: choose an element of A, and add 1 or -1.
Given Q queries, process them in the given order. Each query is of one of the following two kinds.
1 k d
: Add d to A_k (where d is 1 or -1).2 x
: Find the minimum number of operations to make all the elements of A equal x. The operations are not actually performed.
Constraints
- All input values are integers.
- 1\leq N,Q \leq 2\times 10^5
- |A_i| \leq 10^9
- For each query of the 1-st kind, 1\leq k \leq N.
- For each query of the 1-st kind, d is 1 or -1.
- For each query of the 2-nd kind, |x| \leq 10^9.
- There is at least one query of the 2-nd kind.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N Q \mathrm{query}_1 \mathrm{query}_2 \vdots \mathrm{query}_Q
Here, \mathrm{query}_i represents the i-th query, which is given in one of the following formats:
1 k d
2 x
Output
Print q lines, where q is the number of queries of the 2-nd kind. The j-th (1\leq j \leq q) line should contain the answer to the j-th query of the second kind.
Sample Input 1
4 3 5 7 2 4 2 4 1 1 1 1 2 -1 2 4
Sample Output 1
7 5
Initially, A = (3,5,7,2).
- For the 1-st query, it is optimal to add 1 to A_1 once, add -1 to A_2 once, add -1 to A_3 three times, and 1 to A_4 twice. Thus, 1+1+3+2=7 should be printed.
- For the 2-nd query, add 1 to A_1. Now, A=(4,5,7,2).
- For the 3-rd query, add -1 to A_2. Now, A=(4,4,7,2).
- For the 4-th query, it is optimal to add -1 to A_3 three times and 1 to A_4 twice. Thus, 3+2=5 should be printed.
Sample Input 2
10 403 -397 -538 -996 496 -499 80 768 714 -346 10 1 4 -1 2 -362 2 389 2 -470 1 2 -1 2 -58 1 5 1 1 10 1 2 -88 1 3 1
Sample Output 2
5270 5856 5632 5239 5239