第二回アルゴリズム実技検定過去問

A - Elevator

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $9$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

下から順に B9, B8, ..., B1, 1F, 2F, ..., 9F と呼ばれる $18$ のフロアを持つ建物があります。

この建物のエレベーターは、隣接する $2$ つのフロア間の移動に常に $1$ 秒を要します。例えば、B9 から 9F への移動には $17$ 秒を要し、反対方向も同様です。

2 つのフロア $S$ , $T$ が与えられます。エレベーターが $S$ から $T$ へ移動するには最短で何秒を要するでしょうか。

制約

$S$ , $T$ はいずれも B1,B2,B3,B4,B5,B6,B7,B8,B9,1F,2F,3F,4F,5F,6F,7F,8F,9F のいずれかである
$S$ と $T$ は等しくない

入力

入力は以下の形式で標準入力から与えられる。

 $S$   $T$

出力

$S$ から $T$ への移動に要する最短秒数を表す整数を出力せよ。

入力例 1

1F 5F

出力例 1

1F から 5F への移動には $4$ 秒を要します。

入力例 2

B1 B7

出力例 2

B1 から B7 への移動には $6$ 秒を要します。

入力例 3

1F B1

出力例 3

1F と B1 は隣接しているため、移動に $1$ 秒を要します。

入力例 4

B9 9F

出力例 4

B9 から 9F への移動には $17$ 秒を要します。

Score : $9$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There is a building with $18$ floors called B9, B8, ..., B1, 1F, 2F, ..., 9F.

The elevator in this building always takes one second to travel between two adjacent floors. For example, it takes $17$ seconds to travel from B9 to 9F or vice versa.

Given two floors $S$ and $T$ , find the shortest time required for the elevator to travel from $S$ and $T$ .

Constraints

Each of $S$ and $T$ is B1, B2, B3, B4, B5, B6, B7, B8, B9, 1F, 2F, 3F, 4F, 5F, 6F, 7F, 8F, or 9F.
$S$ and $T$ are not equal.

Input

Input is given from Standard Input in the following format:

 $S$   $T$

Output

Print an integer representing the shortest time required to travel from $S$ to $T$ .

Sample Input 1

1F 5F

Sample Output 1

It takes $4$ seconds to travel from 1F to 5F.

Sample Input 2

B1 B7

Sample Output 2

It takes $6$ seconds to travel from B1 to B7.

Sample Input 3

1F B1

Sample Output 3

1F and B1 are adjacent, and it takes $1$ second to travel between them.

Sample Input 4

B9 9F

Sample Output 4

It takes $17$ second to travel from B9 to 9F.

B - Plurality Voting

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $8$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

ある国で選挙が行われました。候補者は a, b, c の $3$ 名です。

投票されたすべての票を表す文字列 $S$ が与えられます。 $S$ は英小文字 a, b, c からなり、 $S$ の $i$ 文字目は $i$ 番目の投票者が投票した候補者を表します。最多得票を得た候補者は誰か求めてください。

なお、最多得票を得た人物はちょうど 1 名であることが保証されています。

制約

$1 \leq |S| \leq 1000$
$S$ は a, b, c からなる文字列である
最多得票を得た人物はちょうど 1 名

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

最多得票を得た候補者を表す英小文字を出力せよ。

入力例 1

abbc

出力例 1

候補者 a が 1 票、b が 2 票、c が 1 票を得ました。最多得票者は b です。

入力例 2

cacca

出力例 2

候補者 b は 1 票も得られませんでした。

入力例 3

出力例 3

投票を行ったのは 1 人だけで、その人は b に投票したため、最多得票者は b です。

入力例 4

babababacaca

出力例 4

Score : $8$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

A country held an election. There were three candidates: a, b, and c.

Given is a string $S$ representing all the votes cast. $S$ consists of the lowercase English letters a, b, and c, and the $i$ -th character of $S$ represents the candidate the $i$ -th voter voted for. Find the candidate who received the most votes. It is guaranteed that there was exactly one candidate who received the most votes.

Constraints

$1 \leq |S| \leq 1000$
$S$ consists of a, b, and c.
There was exactly one candidate who received the most votes.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print a lowercase English letter representing the candidate with the most votes.

Sample Input 1

abbc

Sample Output 1

The candidates a, b, and c received $1$ , $2$ , and $1$ vote(s), respectively. Thus, b received the most votes.

Sample Input 2

cacca

Sample Output 2

The candidate b received no votes.

Sample Input 3

Sample Output 3

There was only one voter, and that person voted for b. Thus, b received the most votes.

Sample Input 4

babababacaca

Sample Output 4

C - Landslide

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $8$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

整数 $2 \leq N \leq 50$ に対して、縦 $N$ マス、横 $2N - 1$ マスのマス目があります。

上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と表します。

このマス目は白黒の $2$ 色で山型に塗られています。具体的には、 $|j - N| < i$ を満たす $1 \leq i \leq N, 1 \leq j \leq (2N - 1)$ についてはマス $(i, j)$ は黒く塗られており、他のマスは白く塗られています。

下は $N = 5$ の場合の例です。(# は黒く塗られたマス、. は白く塗られたマスを表します)

....#....
...###...
..#####..
.#######.
#########

ここで、黒く塗られたマスのうちいくつかに X を書きます。

書き込んだ後の状態は文字からなるサイズ $N \times (2N - 1)$ の $2$ 次元配列 $S$ として与えられ、 $S_{i, j}$ がマス $(i, j)$ の状態を表します。 $S_{i, j}$ が X のとき、マス $(i, j)$ は X の書かれた黒く塗られたマスであり、 $S_{i, j}$ が # のとき、マス $(i, j)$ は X の書かれていない黒く塗られたマスであり、 $S_{i, j}$ が . のとき、マス $(i, j)$ は白く塗られたマスです。

それから、 $i = N - 1, N - 2, \cdots, 1$ の順番で次の操作を行います。

$2 \leq j \leq 2N - 2$ に対して、マス $(i, j)$ が黒く塗られているが X は書かれておらず、マス $(i+1, j-1), (i+1, j), (i+1, j+1)$ のうち $1$ つ以上に X が書かれているとき、マス $(i, j)$ に X を書く。

全ての操作を終えた後のマス目の状態を計算してください。

制約

$2 \leq N \leq 50$
$S_{i, j}$ は . または # または X
$S$ に対応するマス目の状態は、山型に塗られたマス目の黒く塗られたマスのうち $1$ つ以上に X を書くことで得られる

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $S_{1,1}S_{i,2}\cdots S_{1,2N-1}$ 
 $S_{2,1}S_{2,2}\cdots S_{2,2N-1}$ 
 $:$ 
 $S_{N,1}S_{N,2}\cdots S_{N,2N-1}$

出力

全ての操作を終えた後のマス $(i, j)$ の状態を $T_{i,j}$ (黒かつ X が書かれているとき X、黒かつ X が書かれていないとき #、白のとき .) としたとき、以下の形式で出力せよ。

 $T_{1,1}T_{i,2}\cdots T_{1,2N-1}$ 
 $T_{2,1}T_{2,2}\cdots T_{2,2N-1}$ 
 $:$ 
 $T_{N,1}T_{N,2}\cdots T_{N,2N-1}$

入力例 1

5
....#....
...##X...
..#####..
.#X#####.
#########

出力例 1

....X....
...XXX...
..XX###..
.#X#####.
#########

入力例 2

2
.#.
#X#

出力例 2

.X.
#X#

入力例 3

10
.........#.........
........###........
.......#####.......
......#######......
.....#########.....
....###########....
...#############...
..###############..
.#################.
X#X########X#X####X

出力例 3

.........X.........
........XXX........
.......XXXXX.......
......XXXXXXX......
.....XXXXXXXXX.....
....XXXXXXXXXXX....
...XXX##XXXXXXXX...
..XXX####XXXXXXXX..
.XXX######XXXXX##X.
X#X########X#X####X

Score : $8$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have an $N \times (2N - 1)$ grid ( $N$ vertical, $2N - 1$ horizontal) for an integer $1 \leq N \leq 50$ .

Let $(i, j)$ denote the square at the $i$ -th row from the top and $j$ -th column from the left.

The squares are painted black and white so that the black part looks like a mountain. More specifically, for $1 \leq i \leq N$ and $1 \leq j \leq 2N - 1$ such that $|j - N| < i$ , $(i, j)$ is painted black, and the other squares are painted white.

Below is the grid for the case $N = 5$ . (# and . stand for a black square and a white square, respectively.)

....#....
...###...
..#####..
.#######.
#########

Now, we will write an X in some of the black squares.

The grid after this operation is given as a two-dimensional array of characters $S$ of size $N \times (2N - 1)$ , where $S_{i, j}$ corresponds to the square $(i, j)$ . If $S_{i, j}$ is X, $(i, j)$ is a black square with an X written on it; if $S_{i, j}$ is #, $(i, j)$ is a black square without an X written on it; if $S_{i, j}$ is ., $(i, j)$ is a white square.

Then, for each $i = N - 1, N - 2, \cdots, 1$ in this order, we will do the following operation:

For each $2 \leq j \leq 2N - 2$ , if $(i, j)$ is painted black, has no X written on it, and at least one of the squares $(i+1, j-1)$ , $(i+1, j)$ , and $(i+1, j+1)$ has X written in it, write X in $(i, j)$

Compute the final state of the grid after all the operations.

Constraints

$2 \leq N \leq 50$
$S_{i, j}$ is ., #, or X.
The state of the grid corresponding to $S$ can be obtained by writing an X in one or more black squares in a grid painted black and white as described in Problem Statement.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $S_{1,1}S_{i,2}\cdots S_{1,2N-1}$ 
 $S_{2,1}S_{2,2}\cdots S_{2,2N-1}$ 
 $:$ 
 $S_{N,1}S_{N,2}\cdots S_{N,2N-1}$

Output

Output in the following format, where $T_{i,j}$ is the character representing the state of the square $(i, j)$ after all the operations. ( $T_{i,j}$ should be X if $(i, j)$ is black and has an X written on it, # if $(i, j)$ is black and has no X written on it, and . if $(i, j)$ is white.)

 $T_{1,1}T_{i,2}\cdots T_{1,2N-1}$ 
 $T_{2,1}T_{2,2}\cdots T_{2,2N-1}$ 
 $:$ 
 $T_{N,1}T_{N,2}\cdots T_{N,2N-1}$

Sample Input 1

5
....#....
...##X...
..#####..
.#X#####.
#########

Sample Output 1

....X....
...XXX...
..XX###..
.#X#####.
#########

Sample Input 2

2
.#.
#X#

Sample Output 2

.X.
#X#

Sample Input 3

10
.........#.........
........###........
.......#####.......
......#######......
.....#########.....
....###########....
...#############...
..###############..
.#################.
X#X########X#X####X

Sample Output 3

.........X.........
........XXX........
.......XXXXX.......
......XXXXXXX......
.....XXXXXXXXX.....
....XXXXXXXXXXX....
...XXX##XXXXXXXX...
..XXX####XXXXXXXX..
.XXX######XXXXX##X.
X#X########X#X####X

D - String Match

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $7$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

英小文字から成る文字列 $S$ が与えられます。

英小文字または . から成る長さ $1$ 以上 $3$ 以下の文字列 $T$ が $S$ にマッチするとは、次の条件を満たすことを表します。

$T$ の長さを $K$ とする。 $S$ の連続する $K$ 文字であって、 $T$ の . を自由にそれぞれ英小文字 $1$ 文字に置き換えることで一致するような部分が存在する。

英小文字または . から成る長さ $1$ 以上 $3$ 以下の文字列全てのうち、 $S$ にマッチするものの個数を求めてください。

制約

$1 \leq |S| \leq 100$
$S$ は英小文字から成る

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

英小文字または . から成る長さ $1$ 以上 $3$ 以下の文字列全てのうち、 $S$ にマッチするものの個数を出力せよ。

入力例 1

ab

出力例 1

$S$ にマッチするような文字列としては、以下に挙げるように a, b, ., .., .b, a., ab の $7$ 通りが考えられます。

a は $S$ の $1$ 文字目と一致する。
b は $S$ の $2$ 文字目と一致する。
. は、例えば . を a に置き換えることで $S$ の $1$ 文字目と一致する。
.. は、ab に置き換えることで $S$ の $1, 2$ 文字目と一致する。
.b は、ab に置き換えることで $S$ の $1, 2$ 文字目と一致する。
a. は、ab に置き換えることで $S$ の $1, 2$ 文字目と一致する。
ab は、 $S$ の $1, 2$ 文字目と一致する。

入力例 2

aa

出力例 2

$S$ にマッチするような文字列としては、a, ., .., .a, a., aa の $6$ 通りが考えられます。

入力例 3

aabbaabb

出力例 3

Score : $7$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string $S$ consisting of lowercase English letters.

A non-empty string $T$ of length at most $3$ consisting of lowercase English letters and periods (.) is said to match $S$ if and only if the following holds:

Let $K$ be the length of $T$ . $S$ has a contiguous substring of length $K$ that can be equal to $T$ after replacing each period in $T$ with one lowercase English letter.

Among all non-empty strings of length at most $3$ consisting of lowercase English letters and periods, how many match $S$ ?

Constraints

$1 \leq |S| \leq 100$
$S$ consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the number of non-empty strings that match $S$ among all strings of length at most $3$ consisting of lowercase English letters and periods.

Sample Input 1

ab

Sample Output 1

Seven strings match $S$ : a, b, ., .., .b, a., and ab, as follows:

a: coincides with the $1$ -st character of $S$ .
b: coincides with the $2$ -nd character of $S$ .
.: coincides with the $1$ -st character of $S$ after replacing the period with a, for example.
..: coincides with the $1$ -st and $2$ -nd characters of $S$ after changing it to ab.
.b: coincides with the $1$ -st and $2$ -nd characters of $S$ after changing it to ab.
a.: coincides with the $1$ -st and $2$ -nd characters of $S$ after changing it to ab.
ab: coincides with the $1$ -st and $2$ -nd characters of $S$ .

Sample Input 2

aa

Sample Output 2

Six strings match $S$ : a, ., .., .a, a., and aa.

Sample Input 3

aabbaabb

Sample Output 3

E - Permutation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $7$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

$1, 2, \ldots, N$ の順列 $A_1, A_2, \ldots, A_N$ が与えられます。

各整数 $1 \leq i \leq N$ に対して、次の条件を満たす $1$ 以上の整数 $j$ として考えられる最小の値を求めてください。

$x = i$ とする。 $x$ を $A_x$ で置き換えるという操作をちょうど $j$ 回行った後、 $x = i$ となる。

制約

$1 \leq N \leq 100$
$1 \leq A_i \leq N$
$A_i \neq A_j (i \neq j)$
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $A_2$   $\ldots$   $A_N$

出力

$1, 2, \ldots, N$ のそれぞれに対して、この順に、問題文中の条件を満たす $1$ 以上の整数 $j$ として考えられる最小の値を出力せよ。

入力例 1

6
1 3 2 5 6 4

出力例 1

1 2 2 3 3 3

$i = 1$ のとき $A_1 = 1$ であるので、 $j = 1$ が条件を満たす最小の値です。
$i = 2$ のとき $A_2 = 3, A_3 = 2$ であるので、 $j = 2$ が条件を満たす最小の値です。
$i = 3$ のとき $A_3 = 2, A_2 = 3$ であるので、 $j = 2$ が条件を満たす最小の値です。
$i = 4$ のとき $A_4 = 5, A_5 = 6, A_6 = 4$ であるので、 $j = 3$ が条件を満たす最小の値です。
$i = 5$ のとき $A_5 = 6, A_6 = 4, A_4 = 5$ であるので、 $j = 3$ が条件を満たす最小の値です。
$i = 6$ のとき $A_6 = 4, A_4 = 5, A_5 = 6$ であるので、 $j = 3$ が条件を満たす最小の値です。

入力例 2

3
3 2 1

出力例 2

2 1 2

入力例 3

2
1 2

出力例 3

1 1

Score : $7$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a permutation $A_1, A_2, \ldots, A_N$ of $1, 2, \ldots, N$ .

For each integer $1 \leq i \leq N$ , find the minimum integer $j$ not less than $1$ that satisfies the following condition:

If we let $x = i$ and then replace $x$ with $A_x$ exactly $j$ times, we have $x = i$ .

Constraints

$1 \leq N \leq 100$
$1 \leq A_i \leq N$
$A_i \neq A_j (i \neq j)$
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

For each of the integers $1, 2, \ldots, N$ , in this order, print the minimum integer $j$ not less than $1$ that satisfies the condition in Problem Statement.

Sample Input 1

6
1 3 2 5 6 4

Sample Output 1

1 2 2 3 3 3

For $i = 1$ : Since $A_1 = 1$ , $j = 1$ is the minimum value of $j$ satisfying the condition.
For $i = 2$ : Since $A_2 = 3, A_3 = 2$ , $j = 2$ is the minimum value of $j$ satisfying the condition.
For $i = 3$ : Since $A_3 = 2, A_2 = 3$ , $j = 2$ is the minimum value of $j$ satisfying the condition.
For $i = 4$ : Since $A_4 = 5, A_5 = 6, A_6 = 4$ , $j = 3$ is the minimum value of $j$ satisfying the condition.
For $i = 5$ : Since $A_5 = 6, A_6 = 4, A_4 = 5$ , $j = 3$ is the minimum value of $j$ satisfying the condition.
For $i = 6$ : Since $A_6 = 4, A_4 = 5, A_5 = 6$ , $j = 3$ is the minimum value of $j$ satisfying the condition.

Sample Input 2

3
3 2 1

Sample Output 2

2 1 2

Sample Input 3

2
1 2

Sample Output 3

1 1

F - Tasking

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $7$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

$N$ 個のタスクがあります。 $i$ 個目のタスクは $A_i$ 日目 (今日を $1$ 日目とします) またはそれ以降に実行することができ、消化することで $B_i$ ポイントが得られます。

あなたは、これから $1$ 日ごとに、「タスクを一つ選んでそれを消化する」という行為を繰り返します。 $1$ 以上 $N$ 以下のすべての整数 $k$ に対して、これから $k$ 日間で得られるポイントの合計の最大値を求めてください。

ただし、 $1$ 以上 $N$ 以下のすべての整数 $k$ に対して、 $k$ 日目までに実行することのできるタスクが $k$ 個以上存在することが保証されています。

制約

$1 \leq N \leq 2\times10^5$
$1 \leq A_i \leq N$
$1 \leq B_i \leq 100$
入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $B_1$ 
 $A_2$   $B_2$ 
:
 $A_N$   $B_N$

出力

以下の形式で $N$ 行出力せよ。ここで、 $ans_k$ はこれから $k$ 日間で得られるポイントの合計の最大値である。

 $ans_1$ 
 $ans_2$ 
:
 $ans_N$

入力例 1

出力例 1

3
7
9

$1$ 日目に消化できるタスクは $1$ 番目のタスクだけなので、そのタスクを消化し、 $3$ ポイントを得ます。 $k=1$ の場合、これが答えです。 $2$ 日目に消化できるタスクは $1$ 番目から $3$ 番目までのすべてです。 $k=2$ の場合、 $1$ 日目に $1$ 番目のタスクを消化し、 $2$ 日目に $3$ 番目のタスクを消化することで得られる $3+4=7$ ポイントが得られる最大のポイントです。 $k=3$ の場合、 $3$ 日目までにはすべてのタスクを消化することができるので、答えは $3+2+4=9$ です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : $7$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have $N$ tasks. Let today be Day $1$ . You can do the $i$ -th task on or after Day $A_i$ , and finishing the task gives you $B_i$ points.

Each day, starting with today, you choose one task and finish it. For each integer $k$ from $1$ through $N$ , find the maximum total number of points that can be earned in the $k$ days starting with today.

It is guaranteed that there are at least $k$ tasks that you can do in the first $k$ days for each integer $k$ from $1$ through $N$ .

Constraints

$1 \leq N \leq 2\times10^5$
$1 \leq A_i \leq N$
$1 \leq B_i \leq 100$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $B_1$ 
 $A_2$   $B_2$ 
 $:$ 
 $A_N$   $B_N$

Output

Print $N$ lines in the format below, where $ans_k$ is the maximum total number of points earned on the $k$ days starting with today.

 $ans_1$ 
 $ans_2$ 
 $:$ 
 $ans_N$

Sample Input 1

Sample Output 1

3
7
9

On Day $1$ , only the first task is available. You do that task and earn $3$ points, which is the answer for $k=1$ . On Day $2$ , all three tasks are available. For $k=2$ , do the first task on Day $1$ and the third task on Day $2$ to earn the maximum number of points: $3+4=7$ . For $k=3$ , you can finish all the tasks in three days, so the answer is $3+2+4=9$ .

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

G - String Query

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

文字列 $S$ に対して $Q$ 回の操作を行います。初め文字列 $S$ は空文字列です。

$i$ 回目の操作の種類は整数 $T_i (1 \leq i \leq Q)$ で表され、その内容は以下の通りです。

$T_i = 1$ のとき
- 英小文字 $C_i$ と整数 $X_i$ が与えられる。 $S$ の末尾に $C_i$ を $X_i$ 文字追加する。
$T_i = 2$ のとき
- 整数 $D_i$ が与えられる。 $S$ の先頭から $D_i$ 文字を削除する。 $S$ の長さが $D_i$ 文字以下である場合は、 $S$ は空文字列となる。そして、この操作でa, b, c, $\cdots$ z の各文字が何文字削除されたかを求める。それぞれ $del_a, del_b, \cdots, del_z$ 文字削除された場合、 ${del_a}^2 + {del_b}^2 + \cdots + {del_z}^2$ を出力する。

制約

$1 \leq Q \leq 10^5$
$T_i = 1$ または $2$
$C_i$ は英小文字
$1 \leq X_i \leq 10^5$
$1 \leq D_i \leq 10^5$
$Q, T_i, X_i, D_i$ は整数
$T_i = 2$ の操作が $1$ つ以上存在する

入力

入力は以下の形式で標準入力から与えられる。

 $Q$ 
 $Query_1$ 
 $:$ 
 $Query_Q$

$2$ 行目から $Q+1$ 行目の $Query_i$ は以下の $2$ つのいずれかである。

 $1$   $C_i$   $X_i$

$T_i = 1$ として操作を行うことを表す。

 $2$   $D_i$

$T_i = 2$ として操作を行うことを表す。

出力

$T_i = 2$ である操作それぞれに対して順番に、各文字種の削除された文字数の $2$ 乗の和を出力せよ。

入力例 1

出力例 1

9
168
0

初め $S$ は空文字列です。

$1$ 回目の操作の後、 $S$ は aaaaa となります。
$2$ 回目の操作の後、 $S$ は aa となります。a が $3$ 文字削除され、他の文字は削除されていません。
$3$ 回目の操作の後、 $S$ は aatttttttt となります。
$4$ 回目の操作の後、 $S$ は aattttttttcccccccccc となります。
$5$ 回目の操作の後、操作前の $S$ の長さは $20$ であるので、 $S$ は空文字列となります。 a が $2$ 文字、c が $10$ 文字、t が $8$ 文字削除されています。
$6$ 回目の操作の後、 $S$ は空文字列のままです。どの文字も削除されていません。

よって、 $2$ 回目の操作では $3^2 + 0^2 + \cdots + 0^2 = 9$ を、 $5$ 回目の操作では $2^2 + 10^2 + 8^2 = 168$ を出力してください。 $6$ 回目の操作ではどの文字も削除されていないので、 $0$ を出力してください。

入力例 2

出力例 2

初め $S$ は空文字列です。

$1$ 回目の操作の後、 $S$ は xxxxx となります。
$2$ 回目の操作の後、 $S$ は xxxxxyyyyyyyy となります。
$3$ 回目の操作の後、 $S$ は yyyyyy となります。x が $5$ 文字、y が $2$ 文字削除されています。 $5^2 + 2^2 = 29$ です。
$4$ 回目の操作の後、 $S$ は yyyyyyzzzzzzzz となります。

入力例 3

出力例 3

9999400018

Score : $6$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Let us perform $Q$ operations on a string $S$ , which is initially empty.

The type of the $i$ -th operation is represented by an integer $T_i (1 \leq i \leq Q)$ , as follows:

If $T_i = 1$ :
- Given a lowercase English letter $C_i$ and an integer $X_i$ , append $X_i$ copies of $C_i$ to the end of $S$ .
If $T_i = 2$ :
- Given an integer $D_i$ , erase the first $D_i$ characters in $S$ . If the length of $S$ is $D_i$ or less, $S$ becomes empty. Then, find the number of as deleted in this operation, bs deleted in this operation, $\cdots$ , and zs deleted in this operation. Let $del_a, del_b, \cdots, del_z$ be the numbers of characters deleted. We ask you to print the value ${del_a}^2 + {del_b}^2 + \cdots + {del_z}^2$ .

Constraints

$1 \leq Q \leq 10^5$
$T_i = 1$ or $2$ .
$C_i$ is a lowercase English letters.
$1 \leq X_i \leq 10^5$
$1 \leq D_i \leq 10^5$
$Q, T_i, X_i,$ and $D_i$ are integers.
There is at least one operation with $T_i = 2$ .

Input

Input is given from Standard Input in the following format:

 $Q$ 
 $Query_1$ 
 $:$ 
 $Query_Q$

Here, on the $2$ -nd through the $(Q+1)$ -th lines, $Query_i$ is one of the following:

 $1$   $C_i$   $X_i$

representing an operation with $T_i = 1$ , and:

 $2$   $D_i$

representing an operation with $T_i = 2$ .

Output

For each operation with $T_i = 2$ in order, print the value ${del_a}^2 + {del_b}^2 + \cdots + {del_z}^2$ described in Problem Statement.

Sample Input 1

Sample Output 1

9
168
0

Initially, $S$ is empty.

After the $1$ -st operation, $S$ is aaaaa.
After the $2$ -nd operation, $S$ is aa. Here, just three as get deleted.
After the $3$ -rd operation, $S$ is aatttttttt.
After the $4$ -th operation, $S$ is aattttttttcccccccccc.
After the $5$ -th operation, $S$ is empty, since the length of $S$ is $20$ before this operation. Here, two as, ten cs, and eight ts get deleted.
After the $6$ -th operation, $S$ is still empty. No characters get deleted.

Therefore, for the second operation, print $3^2 + 0^2 + \cdots + 0^2 = 9$ ; for the fifth operation, print $2^2 + 10^2 + 8^2 = 168$ ; for the sixth operation where no characters get deleted, print $0$ .

Sample Input 2

Sample Output 2

Initially, $S$ is empty.

After the $1$ -st operation, $S$ is xxxxx.
After the $2$ -nd operation, $S$ is xxxxxyyyyyyyy.
After the $3$ -rd operation, $S$ is yyyyyy. Here, five xs and two ys get deleted, and $5^2 + 2^2 = 29$ .
After the $4$ -th operation, $S$ is yyyyyyzzzzzzzz.

Sample Input 3

Sample Output 3

9999400018

H - 1-9 Grid

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

縦 $N$ マス、横 $M$ マスのマス目があり、各マスには S, G, 1 から 9 の数字のうちいずれかが書かれています。S と G の書かれたマスはただ $1$ つ存在します。

マス目の状態は文字からなるサイズ $N \times M$ の二次元配列 $A$ で表され、上から $i$ 行目、左から $j$ 列目に書かれた文字は $A_{i, j}$ です。

今、S のマスから出発して G のマスに移動しようとしています。各マスからは、 $4$ 方向に隣り合うマスに移動することができます。マス目の外に出るような移動はできません。

S のマスから G のマスへのそのような経路であって、1, 2, $\cdots$ , 9 の書かれたマスをこの順に含むような経路のうち、隣のマスに移動する回数が最小である経路での移動回数を求めてください。また、そのような経路が存在しない場合は $-1$ を出力してください。

なお、経路が 1, 2, $\cdots$ , 9 の書かれたマスをこの順に含むとは、 $k$ 回の移動でマスに書かれていた文字を $c_0 =$ S, $c_1, c_2, \cdots, c_k$ = G としたとき、 $c_{i_1} =$ 1, $c_{i_2} =$ 2, $\cdots$ , $c_{i_9} =$ 9 となるような $1 \leq i_1 \leq i_2 \cdots \leq i_9 < k$ が存在することを表します。

ただし、同じマスは複数回通って良く、S, G の書かれたマスを途中で通過しても構いません。

制約

$1 \leq N, M \leq 50$
$A$ は S, G, および 1 から 9 の数字から成る
S, G の書かれたマスはちょうど $1$ つずつ存在する

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $A_{1,1}A_{i,2}\cdots A_{1,M}$ 
 $A_{2,1}A_{2,2}\cdots A_{2,M}$ 
 $:$ 
 $A_{N,1}A_{N,2}\cdots A_{N,M}$

出力

1, 2, $\cdots$ , 9 の書かれたマスをこの順に部分列に含むような経路のうち、隣のマスに移動する回数が最小であるような経路での移動回数を出力せよ。

入力例 1

出力例 1

1 の書かれたマスのみ $2$ つあります。上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ で表すと、次の経路は移動回数が $17$ で、これが最小です。

(1, 2), (1, 1), (1, 2), (1, 3), (1, 4), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 3), (2, 2), (2, 1), (3, 1), (3, 2), (3, 3)

例えば太字で示したマスに 1, 2, $\cdots$ , 9 がこの順で書かれています。

入力例 2

1 11
S134258976G

出力例 2

入力例 3

出力例 3

-1

6 が含まれないので、条件を満たす経路は存在しません。 $-1$ を出力してください。

Score : $6$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have an $N \times M$ grid ( $N$ vertical, $M$ horizontal), where each square contains one of the following characters: S, G, and the digits from1 through 9. There is only one square with S and only one square with G.

This grid is described by a two-dimensional array of characters $A$ of size $N \times M$ , where $A_{i, j}$ is the character contained in the square at the $i$ -th row from the top and $j$ -th column from the left.

We now want to start at the square with S and reach the square with G. From each square, we can make a move to a horizontally or vertically (but not diagonally) adjacent square. It is not allowed to go out of the grid.

Find the minimum possible number of moves in such a path from the S square to the G square that contains the squares with 1, 2, $\cdots$ , 9 in this order. If no such path exists, print $-1$ .

Here, a path is said to contain the squares with 1, 2, $\cdots$ , 9 in this order when the following holds: Assume that the path has $k$ moves, and it visited squares with the characters $c_0 =$ S, $c_1, c_2, \cdots, c_k$ = G. There exists integers $1 \leq i_1 \leq i_2 \cdots \leq i_9 < k$ such that $c_{i_1} =$ 1, $c_{i_2} =$ 2, $\cdots$ , $c_{i_9} =$ 9.

A path may visit the same square multiple times, including the squares with S and G.

Constraints

$1 \leq N, M \leq 50$
$A$ consists of S, G, and digits from1 through 9.
There is exactly one square with S and exactly one square with E.

Input

Input is given from Standard Input in the following format:

 $N$   $M$ 
 $A_{1,1}A_{i,2}\cdots A_{1,M}$ 
 $A_{2,1}A_{2,2}\cdots A_{2,M}$ 
 $:$ 
 $A_{N,1}A_{N,2}\cdots A_{N,M}$

Output

Print the minimum possible number of moves in a path from the S square to the G square that contains the squares with 1, 2, $\cdots$ , 9 in this order.

Sample Input 1

Sample Output 1

In this grid, only 1 appears twice. Let $(i, j)$ denote the square at the $i$ -th row from the top and the $j$ -th square from the left. Then, the following path has the minimum possible number of moves, which is $17$ :

(1, 2), (1, 1), (1, 2), (1, 3), (1, 4), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 3), (2, 2), (2, 1), (3, 1), (3, 2), (3, 3)

The squares shown by bold characters, for example, contain 1, 2, $\cdots$ , 9, respectively.

Sample Input 2

1 11
S134258976G

Sample Output 2

Sample Input 3

Sample Output 3

-1

The grid has no 6, so there is no path we are seeking, and we should print $-1$ .

I - Elimination

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

人 $1$ 、人 $2$ 、…、人 $2^N$ の $2^N$ 人が一列に並んでトーナメントを行いました。このトーナメントは以下のようにして行われました。

$1$ 回戦: $1 \leq i \leq 2^{N-1}$ を満たすそれぞれの $i$ について、人 $2i-1$ と人 $2i$ が戦う。どちらか一方が勝つので、勝った方が残る。
$i$ 回戦 ( $i \geq 2$ ): $i - 1$ 回戦で残った人が番号順に左から並び、左から 2 人ずつペアになり、各ペア内の $2$ 人が戦う。どちらか一方が勝つので、勝った方が残る。

各試合の記録は失われてしまいましたが、人 $i$ の強さが $A_i$ であったことは記録に残っていました。ここで、 $2$ 人の人が戦ったとき、強さの値が大きい方が勝ちます。

それぞれの人について、その人が最後に戦ったのは何回戦か求めてください。

制約

$1 \leq N \leq 16$
$1 \leq A_i \leq 2^N$
$A$ の要素は相異なる

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $A_2$   $\cdots$   $A_{2^N}$

出力

$2^N$ 行出力せよ。 $i$ 行目には、人 $i$ が最後に戦ったのは何回戦かを出力せよ。

入力例 1

2
2 4 3 1

出力例 1

$1$ 回戦: 人 $1$ (強さ $2$ ) と人 $2$ (強さ $4$ ) が戦い、人 $2$ が勝ち残った。また、人 $3$ (強さ $3$ ) と人 $4$ (強さ $1$ ) が戦い、人 $3$ が勝ち残った。
$2$ 回戦: 人 $2$ と人 $3$ が戦い、人 $2$ が勝った。

したがって、人 $1$ と人 $4$ が最後に戦ったのは $1$ 回戦、人 $2$ と人 $3$ が最後に戦ったのは $2$ 回戦です。

入力例 2

1
2 1

出力例 2

1
1

参加者が $2$ 人しかいない場合は、どちらも 1 回戦が最後の戦いになります。

入力例 3

3
4 7 5 1 6 3 2 8

出力例 3

Score : $6$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

$2^N$ players with integer IDs - Player $1$ , Player $2$ , ..., Player $2^N$ - stood in a line and played an elimination tournament, as follows:

Round $1$ : For each $i$ such that $1 \leq i \leq 2^{N-1}$ , Player $2i-1$ and Player $2i$ fight until one of them wins and survives.
Round $i$ ( $i \geq 2$ ): The players survived Round $i-1$ stand in a line in ascending order of ID. Then, for each $i$ such that $1 \leq i \leq 2^{N-i}$ , the $(2i-1)$ -th and the $(2i)-th players from the left fight until one of them wins and survives.

While the record of each fight is now lost, our record says that the strength of Player $i$ was $A_i$ . Here, when two players fight, the player with the greater strength wins.

For each of the players, find the last round in which that player fought.

Constraints

$1 \leq N \leq 16$
$1 \leq A_i \leq 2^N$
The elements of $A$ are distinct.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $A_2$   $\cdots$   $A_{2^N}$

Output

Print $2^N$ . The $i$ -th line should contain the integer representing the last round in which Player $i$ fought.

Sample Input 1

2
2 4 3 1

Sample Output 1

Round $1$ : Player $2$ (strength: $4$ ) fought against Player $1$ (strength: $2$ ) and won. Also, Player $3$ (strength: $3$ ) fought against Player $4$ (strength: $1$ ) and won.
Round $2$ : Player $2$ fought against Player $3$ and won.

Thus, the last rounds in which Player $1,2,3,4$ fought are Round $1,2,2,1$ , respectively.

Sample Input 2

1
2 1

Sample Output 2

1
1

There were just two players, in which case Round $1$ was the last round for both of them.

Sample Input 3

3
4 7 5 1 6 3 2 8

Sample Output 3

J - Parse

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

英小文字 a ~ z と ( と ) からなる文字列 $S$ が与えられます。ある文字列 $a$ と $b$ に対して $a+b$ を $a$ と $b$ をこの順に結合した文字列とします。また、ある文字列 $a$ に対して $rev(a)$ を $a$ を反転させた文字列とします。以下の操作をこれ以上操作が行えなくなるまで繰り返し行ったときの、最終的な文字列 $S$ を出力してください。

( や ) を含まない文字列 $a$ (空文字列でもよい) に対して ( $+a+$ ) のような部分文字列が $S$ の中にあったときに、その部分文字列を $a+rev(a)$ に置き換える

ただし、文字列 $S$ で正しい括弧の対応が取れていること、すなわち最終的な文字列 $S$ に ( や ) は含まれないことが保証されています。また、この条件下で最終的な文字列は一意に定まることが示せます。

制約

$S$ は長さ $1$ 以上 $1000$ 以下の、英小文字 a ~ z と ( と ) からなる文字列である。
$S$ は $1$ 文字以上の英小文字を含む。
操作をこれ以上操作が行えなくなるまで繰り返し行ったときの、最終的な文字列 $S$ の長さは $1000$ 以下であり、これに( や ) は含まれない。

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

操作をこれ以上操作が行えなくなるまで繰り返し行ったときの最終的な文字列 $S$ を出力せよ。

入力例 1

(ab)c

出力例 1

abbac

(ab) を ab $+rev($ ab $)$ である abba に置き換えると、 $S$ は abbac になります。これ以上操作を行うことはできないので、これを出力します。

入力例 2

past

出力例 2

past

括弧が存在しない可能性もあります。

入力例 3

(d(abc)e)()

出力例 3

dabccbaeeabccbad

括弧の中が空文字列である可能性もあります。

Score : $6$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string $S$ consisting of lowercase English letters a through z, (, and ). For strings $a$ and $b$ , let $a+b$ be the concatenation of $a$ and $b$ in this order. Also, for a string $a$ , let $rev(a)$ be the reversal of $a$ . Print the string $S$ after repeating the following operation until it cannot be applied.

If $S$ has a substring of the form ( + $a$ + ) where $a$ is a string that does not contain (s or )s, replace that substring with $a+rev(a)$ .

Here, it is guaranteed that parentheses in $S$ are balanced, that is, the final string will not contain (s or )s. Also, under this condition, it can be shown that the final string is uniquely determined.

Constraints

$S$ is a string of length between $1$ and $1000$ (inclusive) consisting of lowercase English letters a through z, (, and ).
$S$ contains one or more lowercase English letters.
The string $S$ after repeating the operation until it cannot be applied has a length of at most $1000$ and does not contain (s or )s.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the string $S$ after repeating the following operation until it cannot be applied.

Sample Input 1

(ab)c

Sample Output 1

abbac

After replacing (ab) with ab $+rev($ ab $)$ , that is, abba, $S$ is abbac. We can do no more operations, so we should print this string.

Sample Input 2

past

Sample Output 2

past

The input may contain no parentheses.

Sample Input 3

(d(abc)e)()

Sample Output 3

dabccbaeeabccbad

There can be an empty string between parentheses.

K - Parentheses

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

( と ) からなる長さ $N$ の文字列 $S$ が与えられます。 $S$ の $i$ 番目の文字を $S_i$ で表します。

以下の手順で $S$ を 括弧の対応が取れている文字列 (後述) にすることを考えます。

まず、次の操作を $0$ 回以上好きなだけ行います。

$1 \leq i \leq N$ を選ぶ。 $S_i$ が ( ならば ) に、) ならば ( に変更する。この操作のコストは $C_i$ である。

その後、次の操作を行います。

$S$ から $0$ 文字以上選んで削除し (全ての文字を削除しても良い)、削除しなかった文字を元の順序で繋げる。 $S$ の $i$ 文字目を削除するコストは $D_i$ である。

$S$ を括弧の対応が取れている文字列にするための合計コストの最小値を求めてください。

なお、括弧の対応が取れている文字列とは、次のうちいずれかの条件を満たす文字列です。

空文字列
ある括弧の対応が取れている空でない文字列 $A, B$ が存在し、 $A$ , $B$ をこの順に連結した文字列
ある括弧の対応が取れている文字列 $A$ が存在し、 (, $A$ , ) をこの順に連結した文字列

制約

$1 \leq N \leq 3000$
$S$ の長さは $N$
$S$ の各文字は ( または )
$1 \leq C_i \leq 10^9$
$1 \leq D_i \leq 10^9$
$N, C_i, D_i$ は整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $S$ 
 $C_1$   $C_2$   $\cdots$   $C_N$ 
 $D_1$   $D_2$   $\cdots$   $D_N$

出力

$S$ を括弧の対応が取れている文字列にするための合計コストの最小値を出力せよ。

入力例 1

出力例 1

はじめ $S$ は ))( です。例えば次の手順で括弧の対応が取れている文字列にすることができます。

文字を変更する段階で、 $S_1$ を変更する。 $3$ のコストがかかり、 $S$ は ()( となる。
文字を削除する段階で、 $S_3$ を削除する。 $5$ のコストがかかり、 $S$ は () となる。

この場合の合計コストは $3+5=8$ であり、これが最小です。

入力例 2

出力例 2

はじめ $S$ は ( です。これを空文字列に変えるしかありません。

入力例 3

10
))())((()(
13 18 17 3 20 20 6 14 14 2
20 1 19 5 2 19 2 19 9 4

出力例 3

入力例 4

出力例 4

$S$ は既に括弧の対応が取れている文字列です。

Score : $6$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string $S$ of length $N$ consisting of (s and )s. Let $S_i$ denote the $i$ -th character of $S$ .

We want to make $S$ a balanced string (defined below) in the following procedure.

First, we do the operation below zero or more times:

Choose an integer $1 \leq i \leq N$ . If $S_i$ is (, replace it with ); if $S_i$ is ), replace it with (. The cost of this operation is $C_i$ .

Then, we do the operation below:

Choose zero or more (possibly all) characters in $S$ and delete them. Then, concatenate the remaining characters in $S$ without changing the order.

Find the minimum total cost required to make $S$ a balanced string.

A balanced string is a string that is one of the following:

An empty string;
The concatenation of $A$ and $B$ in this order, for some non-empty balanced strings $A$ and $B$ ;
The concatenation of (, $A$ , and ) in this order, for some balanced string $A$ /

Constraints

$1 \leq N \leq 3000$
The length of $S$ is $N$ .
Each character of $S$ is ( or ).
$1 \leq C_i \leq 10^9$
$1 \leq D_i \leq 10^9$
$N$ , $C_i$ , and $D_i$ are integers.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $S$ 
 $C_1$   $C_2$   $\cdots$   $C_N$ 
 $D_1$   $D_2$   $\cdots$   $D_N$

Output

Print the minimum total cost required to make $S$ a balanced string.

Sample Input 1

Sample Output 1

$S$ is initially ))(. One way to make it a balanced string is:

In the "modifying" step, change $S_1$ at the cost of $3$ . $S$ becomes ()(.
In the "deleting" step, delete $S_3$ at the cost of $5$ . $S$ becomes ().

The total cost here is $3+5=8$ , and this is the minimum possible value.

Sample Input 2

Sample Output 2

$S$ is initially (, and the only choice is to make it an empty string.

Sample Input 3

10
))())((()(
13 18 17 3 20 20 6 14 14 2
20 1 19 5 2 19 2 19 9 4

Sample Output 3

Sample Input 4

Sample Output 4

$S$ is already a balanced string.

L - Lexicographically Minimum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

長さ $N$ の整数列 $A_1, A_2, \cdots, A_N$ があります。ここから $K$ 個の要素を選び、それらを相対的な順序を保ったまま並べて新しい数列を作るという操作を考えます。ただし、 $A_i$ と $A_j$ $(i \neq j)$ をともに選べるのは $|i - j| \geq D$ であるときに限ります。

この操作で作ることのできる数列のうち、辞書順で最小である数列を求めてください。そのような操作が不可能である場合は $-1$ を出力してください。

なお、長さ $K$ の数列 $x_1,x_2,\cdots,x_K$ が $y_1,y_2,\cdots,y_K$ より辞書順で小さいとは、二つの数列が異なり、かつ $i$ を $x_i \neq y_i$ であるような最小の整数としたとき $x_i < y_i$ であることをいいます。

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq D \leq N$
$1 \leq K \leq N$
$0 \leq A_i \leq 10^9$
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $K$   $D$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

出力

操作が可能であれば得られる辞書順最小の数列を、不可能であれば $-1$ を出力せよ。

入力例 1

3 2 2
3 1 4

出力例 1

3 4

数列 $A$ は $\{ 3, 1, 4\}$ です。 $D = 2$ の下で、 $K = 2$ 個の要素を選んで数列を作る方法は次の $1$ 通りです。

$A$ の $1, 3$ 番目の要素を選び、 $\{ 3, 4\}$ とする。

よって、 $\{ 3, 4\}$ を出力してください。

入力例 2

3 3 2
3 1 4

出力例 2

-1

数列 $A$ は $\{ 3, 1, 4\}$ です。 $D = 2$ の下で、 $K = 3$ 個の要素を選んで数列を作ることはできません。

よって、 $-1$ を出力してください。

入力例 3

3 2 1
3 1 4

出力例 3

1 4

数列 $A$ は $\{ 3, 1, 4\}$ です。 $D = 1$ の下で、 $K = 2$ 個の要素を選んで数列を作る方法は次の $3$ 通りです。

$A$ の $1, 2$ 番目の要素を選び、 $\{ 3, 1\}$ とする。
$A$ の $1, 3$ 番目の要素を選び、 $\{ 3, 4\}$ とする。
$A$ の $2, 3$ 番目の要素を選び、 $\{ 1, 4\}$ とする。

よって、 $\{ 1, 4\}$ を出力してください。

入力例 4

4 2 2
3 6 5 5

出力例 4

3 5

数列 $A$ は $\{ 3, 6, 5, 5\}$ です。 $D = 2$ の下で、 $K = 2$ 個の要素を選んで数列を作る方法は次の $3$ 通りです。

$A$ の $1, 3$ 番目の要素を選び、 $\{ 3, 5\}$ とする。
$A$ の $1, 4$ 番目の要素を選び、 $\{ 3, 5\}$ とする。
$A$ の $2, 4$ 番目の要素を選び、 $\{ 6, 5\}$ とする。

よって、 $\{ 3, 5\}$ を出力してください。

Score : $6$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have an integer sequence of length $N$ : $A_1, A_2, \cdots, A_N$ . Consider choosing $K$ of its elements and arrange them in a row to form a new sequence without changing the relative order of the elements. Here, choosing $A_i$ and $A_j$ $(i \neq j)$ at the same time is only allowed when $|i - j| \geq D$ .

Find the lexicographically smallest sequence obtained in this way. If it is impossible to obtain a sequence in this way, print $-1$ .

Here, a sequence of length $K$ : $x_1,x_2,\cdots,x_K$ is said to be lexicographically smaller than another sequence $y_1,y_2,\cdots,y_K$ if and only if the sequences are different and $x_i < y_i$ holds for the minimum integer $i$ such that $x_i \neq y_i$ .

Constraints

$2 \leq N \leq 2 \times 10^5$
$1 \leq D \leq N$
$1 \leq K \leq N$
$0 \leq A_i \leq 10^9$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $K$   $D$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

Output

If it is possible to obtain a sequence in the way described in Problem Statement, print the lexicographically smallest such sequence; otherwise, print $-1$ .

Sample Input 1

3 2 2
3 1 4

Sample Output 1

3 4

$A = \{ 3, 1, 4\}$ . Under $D = 2$ , there is one way to choose $K = 2$ elements to form a sequence, as follows:

Choose the $1$ -st and $3$ -rd elements of $A$ to form $\{ 3, 4\}$ .

Thus, we should print $\{ 3, 4\}$ .

Sample Input 2

3 3 2
3 1 4

Sample Output 2

-1

$A = \{ 3, 1, 4\}$ . Under $D = 2$ , there is no way to choose $K = 3$ elements to form a sequence.

Thus, we should print $-1$ .

Sample Input 3

3 2 1
3 1 4

Sample Output 3

1 4

$A = \{ 3, 1, 4\}$ . Under $D = 1$ , there are three ways to choose $K = 2$ elements to form a sequence, as follows:

Choose the $1$ -st and $2$ -nd elements of $A$ to form $\{ 3, 1\}$ .
Choose the $1$ -st and $3$ -rd elements of $A$ to form $\{ 3, 4\}$ .
Choose the $2$ -nd and $3$ -rd elements of $A$ to form $\{ 1, 4\}$ .

Thus, we should print $-1$ .

Sample Input 4

4 2 2
3 6 5 5

Sample Output 4

3 5

$A = \{ 3, 6, 5, 5\}$ . Under $D = 2$ , there are three ways to choose $K = 2$ elements to form a sequence, as follows:

Choose the $1$ -st and $3$ -rd elements of $A$ to form $\{ 3, 5\}$ .
Choose the $1$ -st and $4$ -th elements of $A$ to form $\{ 3, 5\}$ .
Choose the $2$ -nd and $4$ -th elements of $A$ to form $\{ 6, 5\}$ .

Thus, we should print $\{ 3, 5\}$ .

M - Cafeteria

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

ある社員食堂では $D$ 日周期でメニューが組まれています。この食堂の料理は整数で表され、今日を $1$ 日目として $i$ 日目、 $i + D$ 日目、 $i + 2D$ 日目、…、には料理 $C_i$ が提供されます。

$N$ 人の社員はそれぞれ食事にこだわりがあり、社員 $j$ は料理 $K_j$ を好んでいます。各社員は、好みの料理が提供される日には必ず食堂を利用してその料理を食べます。それ以外の料理が提供される日には、前回の利用が $L$ 日前である場合のみ食堂を利用します。ただし、初回の利用についてはこの限りではありません (後述)。

各整数 $1 \leq j \leq N$ について、以下の問題に答えてください。

社員 $j$ が $F_j$ 日目に初めて食堂を利用するとする (この日に限って料理が好みでなくても利用するものとし、またこれより前に好みの料理が提供されていても利用できないものとする)。社員 $j$ が合計で $T_j$ 回食堂を利用するまでに好みの料理を食べる回数を求めよ。

制約

$1 \leq N \leq 10^5$
$1 \leq D \leq 10^5$
$1 \leq L \leq 10^9$
$1 \leq C_i, K_j \leq 10^5$
$1 \leq F_j \leq D$
$1 \leq T_j \leq 10^9$
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $D$   $L$   $N$ 
 $C_1$   $C_2$   $\cdots$   $C_D$ 
 $K_1$   $F_1$   $T_1$ 
 $K_2$   $F_2$   $T_2$ 
 $:$ 
 $K_N$   $F_N$   $T_N$

出力

$N$ 行出力せよ。 $j$ 行目には、社員 $j$ が好みの料理を食べる回数を出力せよ。

入力例 1

出力例 1

1
0
3

食堂のメニューは、 $4$ 日周期で $\{ 2, 3, 1, 3 \}$ が繰り返されています。

社員 $1$ は、料理 $1$ が好みです。はじめに $2$ 日目に料理 $3$ を食べ、次に $3$ 日目は料理 $1$ を食べることができます。よって $1$ 回好みの料理を食べることができるので、 $1$ を出力してください。
社員 $2$ は、料理 $3$ が好みです。 $3$ 日目に料理 $1$ を食べます。好みの料理を一度も食べることができないので、 $0$ を出力してください。
社員 $3$ は、料理 $3$ が好みです。はじめに $4$ 日目に料理 $3$ を、 $6$ 日目に料理 $3$ を、 $8$ 日目に料理 $3$ を食べます。よって $3$ を出力してください。

入力例 2

出力例 2

0
3
3

食堂のメニューは毎日 $1$ です。

社員 $1$ は、料理 $2$ が好みです。はじめに $1$ 日目に料理 $1$ を食べた後、 $L = 1$ であるので $2, 3$ 日目も料理 $1$ を食べます。好みの料理はメニューに含まれないので $0$ を出力してください。
社員 $2, 3$ は料理 $1$ が好きであり、毎日好みの料理を食べます。 $3$ を出力してください。

入力例 3

10 4 4
4 4 4 3 1 1 5 2 2 1
2 5 2
2 9 10
2 3 3
2 7 13

出力例 3

Score : $6$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

The menu in some company cafeteria is based on a $D$ -day cycle. Its dishes are represented by integers, and it serves Dish $C_i$ on Day $i$ , Day $i + D$ , Day $i + 2D$ , and so on, where today is Day $1$ .

The $N$ employees who use this cafeteria are particular about food, and Employee $j$ loves Dish $K_j$ . Each employee always uses the cafeteria on a day when the favorite dish is served and gets it. On the other days, an employee uses the cafeteria only if the last day when he/she used it is $L$ days ago. However, the above does not apply when it is the first time for him/her to use it (described below).

For each integer $1 \leq j \leq N$ , answer the question below:

Assume that Employee $j$ uses the cafeteria on Day $F_j$ for the first time. (For this day only, he/she uses it even if the served dish is not his/her favorite. Also, assume that he/she cannot use the cafeteria before this day even when his/her favorite dish is served.) Find the number of times Employee $j$ gets the favorite dish until he/she uses the cafeteria $T_j$ times in total.

Constraints

$1 \leq N \leq 10^5$
$1 \leq D \leq 10^5$
$1 \leq L \leq 10^9$
$1 \leq C_i, K_j \leq 10^5$
$1 \leq F_j \leq D$
$1 \leq T_j \leq 10^9$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $D$   $L$   $N$ 
 $C_1$   $C_2$   $\cdots$   $C_D$ 
 $K_1$   $F_1$   $T_1$ 
 $K_2$   $F_2$   $T_2$ 
 $:$ 
 $K_N$   $F_N$   $T_N$

Output

Print $N$ lines. The $j$ -th line should contain the number of times Employee $j$ gets the favorite dish.

Sample Input 1

Sample Output 1

1
0
3

The cafeteria serves the dishes with a $4$ -day cycle: $\{ 2, 3, 1, 3 \}$ .

Employee $1$ loves Dish $1$ . He first eats Dish $3$ on Day $2$ , then eats Dish $1$ on Day $3$ . Thus, he gets his favorite dish once, and we should print $1$ .
Employee $2$ loves Dish $3$ . He eats Dish $1$ on Day $3$ , and that is it. Thus, he gets his favorite dish zero times, and we should print $0$ .
Employee $3$ loves Dish $3$ . He first eats Dish $3$ on Day $4$ , then eats Dish $3$ on Day $6$ , then eats Dish $3$ on Day $8$ . Thus, we should print $3$ .

Sample Input 2

Sample Output 2

0
3
3

The cafeteria serves Dish $1$ every day.

Employee $1$ loves Dish $2$ . He first eats Dish $1$ on Day $1$ , then also eats Dish $1$ on Day $2$ and $3$ since $L = 1$ . The cafeteria never offers his favorite, so we should print $0$ .
Employee $2$ and $3$ love Dish $1$ , and they get their favorite every day, so we should print $3$ for each of them.

Sample Input 3

10 4 4
4 4 4 3 1 1 5 2 2 1
2 5 2
2 9 10
2 3 3
2 7 13

Sample Output 3

N - Building Construction

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

$2$ 次元平面上に、各辺が x, y 軸に並行な正方形の敷地が $N$ 個あり、 $i$ 個目の敷地の範囲は領域 $xmin_i \leq x \leq xmin_i + D_i, ymin_i \leq y \leq ymin_i + D_i$ です。各敷地にはコストが定まっており、 $i$ 番目の敷地のコストは $C_i$ です。

今、 $Q$ 件のビル建設計画があり、 $j$ 件目の計画での建設予定地点の座標は $(A_j, B_j)$ です。

各計画のコストは、その計画の建設座標を含む (または境界線上に持つ) すべての敷地のコストの和です。

各計画のコストを求めてください。

制約

$1 \leq N \leq 50000$
$1 \leq Q \leq 100000$
$-10^9 \leq xmin_i, ymin_i \leq 10^9$
$1 \leq D_i \leq 10^9$
$0 \leq C_i \leq 10^9$
$-10^9 \leq A_i, B_i \leq 10^9$
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $Q$ 
 $xmin_1$   $ymin_1$   $D_1$   $C_1$ 
 $xmin_2$   $ymin_2$   $D_2$   $C_2$ 
 $:$ 
 $xmin_N$   $ymin_N$   $D_N$   $C_N$ 
 $A_1$   $B_1$ 
 $:$ 
 $A_Q$   $B_Q$

出力

$Q$ 行出力せよ。 $j$ 行目に $j$ 件目の計画のコストを出力すること。

入力例 1

出力例 1

$1$ 件目の計画の座標は、 $1, 2$ 個目の敷地に含まれるので、 $10 + 20 = 30$ を出力してください。
$2$ 件目の計画の座標は、どちらの敷地にも含まれないので、 $0$ を出力してください。
$3$ 件目の計画の座標は、 $1$ 個目の敷地に含まれるので、 $10$ を出力してください。
$4$ 件目の計画の座標は、どちらの敷地にも含まれないので、 $0$ を出力してください。

入力例 2

出力例 2

130
100
30

$1$ 件目の計画の座標は、 $1, 2$ 個目の敷地に含まれるので、 $100 + 30 = 130$ を出力してください。
$2$ 件目の計画の座標は、 $1$ 個目の敷地に含まれるので、 $100$ を出力してください。
$3$ 件目の計画の座標は、 $2$ 個目の敷地に含まれるので、 $30$ を出力してください。

入力例 3

10 10
17 2 17 1000000000
7 12 12 1000000000
2 12 8 1000000000
2 12 2 1000000000
3 9 16 1000000000
8 13 15 1000000000
8 1 3 1000000000
15 9 17 1000000000
16 5 5 1000000000
13 12 9 1000000000
17 3
4 10
1 9
5 3
17 12
14 19
19 17
17 11
16 17
12 16

出力例 3

Score : $6$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In a two-dimensional plane, there are $N$ square plots of land whose sides are parallel to the x- or y-axis. The $i$ -th plot can be represented as the region $xmin_i \leq x \leq xmin_i + D_i, ymin_i \leq y \leq ymin_i + D_i$ . Each of these plots has a fixed cost, and the cost of the $i$ -th plot is $C_i$ .

Here, $Q$ construction plans are considered. The $j$ -th plan aims to construct a building at coordinates $(A_j, B_j)$ .

The cost of each plan is the sum of the costs of all the plots covering (or touching) the construction point.

Find the cost of each plan.

Constraints

$1 \leq N \leq 50000$
$1 \leq Q \leq 100000$
$-10^9 \leq xmin_i, ymin_i \leq 10^9$
$1 \leq D_i \leq 10^9$
$0 \leq C_i \leq 10^9$
$-10^9 \leq A_i, B_i \leq 10^9$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $Q$ 
 $xmin_1$   $ymin_1$   $D_1$   $C_1$ 
 $xmin_2$   $ymin_2$   $D_2$   $C_2$ 
 $:$ 
 $xmin_N$   $ymin_N$   $D_N$   $C_N$ 
 $A_1$   $B_1$ 
 $:$ 
 $A_Q$   $B_Q$

Output

Print $Q$ lines. The $j$ -th line should contain the cost of the $j$ -th plan.

Sample Input 1

Sample Output 1

For the $1$ -st plan, both plots cover the construction point, so we should print $10 + 20 = 30$ .
For the $2$ -nd plan, neither plot covers the construction point, so we should print $0$ .
For the $3$ -rd plan, the $1$ -st plot covers the construction point, so we should print $10$ .
For the $4$ -th plan, neither plot covers the construction point, so we should print $0$ .

Sample Input 2

Sample Output 2

130
100
30

For the $1$ -st plan, both plots cover the construction point, so we should print $100 + 30 = 130$ .
For the $2$ -nd plan, the $1$ -st plot covers the construction point, so we should print $100$ .
For the $3$ -rd plan, the $2$ -nd plot covers the construction point, so we should print $30$ .

Sample Input 3

10 10
17 2 17 1000000000
7 12 12 1000000000
2 12 8 1000000000
2 12 2 1000000000
3 9 16 1000000000
8 13 15 1000000000
8 1 3 1000000000
15 9 17 1000000000
16 5 5 1000000000
13 12 9 1000000000
17 3
4 10
1 9
5 3
17 12
14 19
19 17
17 11
16 17
12 16

Sample Output 3

O - Variable Spanning Trees

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

$N$ 頂点 $M$ 辺の重みつき単純連結無向グラフが与えられます。頂点には $1$ から $N$ 、辺には $1$ から $M$ までの番号が振られています。

辺 $i$ は頂点 $A_i$ と $B_i$ を結び、その重みは $C_i$ です。

辺 $1$ から辺 $M$ までのそれぞれの辺について、その辺を含む最小の重みの全域木を求め、その重みを出力してください。

注釈

連結無向グラフ $(V, E)$ における全域木とは、ある辺の部分集合 $T \subseteq E$ について $(V, T)$ と書ける木のことである。
全域木 $(V, T)$ の重みは、 $T$ に含まれる全ての辺の重みの和である。

制約

$2 \leq N \leq 10^5$
$N - 1 \leq M \leq \mathrm{min}(10^5, N(N - 1)/2)$
$1 \leq A_i, B_i \leq N$ ( $1 \leq i \leq M$ )
$A_i \neq B_i$ ( $1 \leq i \leq M$ )
$1 \leq C_i \leq 10^9$ ( $1 \leq i \leq M$ )
与えられる無向グラフは単純かつ連結である

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $A_1$   $B_1$   $C_1$ 
 $:$ 
 $A_M$   $B_M$   $C_M$

出力

$M$ 行出力せよ。 $i$ 行目には、辺 $i$ を含む全域木の重みとしてありえる最小値を出力せよ。

入力例 1

出力例 1

5
7
5

入力例 2

出力例 2

入力例 3

8 10
1 2 314159265
2 3 358979323
3 4 846264338
1 3 327950288
1 4 419716939
2 4 937510582
1 5 97494459
1 6 230781640
1 7 628620899
1 8 862803482

出力例 3

答えが 32 ビット整数の範囲内でないこともあるため、注意してください。

Score : $6$ points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a simple connected undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$ , and the edges are numbered $1$ to $M$ .

Edge $i$ connects Vertex $A_i$ and $B_i$ , and the weight of this edge is $C_i$ .

For each edge from $1$ to $M$ , find a minimum-weight spanning tree containing that edge, and print the weight of that tree.

Notes

A spanning tree in a connected undirected graph $(V, E)$ is a tree that can be written as $(V, T)$ for some subset of edges $T \subseteq E$ .
The weight of a spanning tree $(V, T)$ is the sum of the weights of all edges in $T$ .

Constraints

$2 \leq N \leq 10^5$
$N - 1 \leq M \leq \mathrm{min}(10^5, N(N - 1)/2)$
$1 \leq A_i, B_i \leq N$ ( $1 \leq i \leq M$ )
$A_i \neq B_i$ ( $1 \leq i \leq M$ )
$1 \leq C_i \leq 10^9$ ( $1 \leq i \leq M$ )
The given graph is simple and connected.

Input

Input is given from Standard Input in the following format:

 $N$   $M$ 
 $A_1$   $B_1$   $C_1$ 
 $:$ 
 $A_M$   $B_M$   $C_M$

Output

Print $M$ lines. The $i$ -th line should contain the minimum possible weight of a spanning tree containing Edge $i$ .

Sample Input 1

Sample Output 1

5
7
5

Sample Input 2

Sample Output 2

Sample Input 3

8 10
1 2 314159265
2 3 358979323
3 4 846264338
1 3 327950288
1 4 419716939
2 4 937510582
1 5 97494459
1 6 230781640
1 7 628620899
1 8 862803482

Sample Output 3

Note that the answer may not fit into a 32-bit integer type.