C - ARC Division

Time Limit: 2 sec / Memory Limit: 1024 MiB



配点 : 200 点

問題文

AtCoder では、ARC が 2 つの division に分けられています。

  • ARC Div. 1 では、コンテスト開始時のレーティングが 1600 以上 2799 以下の参加者がレーティング更新の対象です。
  • ARC Div. 2 では、コンテスト開始時のレーティングが 1200 以上 2399 以下の参加者がレーティング更新の対象です。

高橋くんは、これから N 回の ARC に参加することにしました。

はじめ、高橋くんのレーティングは R です。

i 回目 (1\leq i\leq N) の ARC は Div. D _ i で、高橋くんが取った成績は整数 A _ i で表されます。

i 回目の ARC において高橋くんがレーティング更新の対象ならば、コンテスト開始時の高橋くんのレーティングを T として、更新後の高橋くんのレーティングは T+A _ i になります。 高橋くんがレーティング更新の対象でなければ、高橋くんのレーティングは変化しません。

ARC でのレーティングの更新はコンテストが終了したあと直ちに行われ、次のコンテストのレーティング更新の対象であるかは更新後のレーティングをもとに判定されます。

N 回の ARC を終えたとき、高橋くんのレーティングがいくつになっているか求めてください。

ただし、高橋くんはこの N 回の ARC 以外のコンテストには参加せず、ARC 以外でレーティングが変動することはありません。

制約

  • 1\leq N\leq 100
  • 0\leq R\leq 4229
  • 1\leq D _ i\leq 2\ (1\leq i\leq N)
  • -1000\leq A _ i\leq 1000\ (1\leq i\leq N)
  • 入力はすべて整数

入力

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

N R
D _ 1 A _ 1
D _ 2 A _ 2
\vdots
D _ N A _ N

出力

N 回の ARC を終えた後の、高橋くんのレーティングを出力せよ。


入力例 1

4 1255
2 900
1 521
2 600
1 52

出力例 1

2728

はじめ、高橋くんのレーティングは 1255 です。

それぞれのコンテストで、高橋くんのレーティングは次のように変化します。

  • 1 回目の ARC は Div. 2 です。高橋くんはレーティング更新の対象なので、高橋くんのレーティングは 1255+900=2155 になります。
  • 2 回目の ARC は Div. 1 です。高橋くんはレーティング更新の対象なので、高橋くんのレーティングは 2155+521=2676 になります。
  • 3 回目の ARC は Div. 2 です。高橋くんはレーティング更新の対象ではないので、高橋くんのレーティングは変化しません。
  • 4 回目の ARC は Div. 1 です。高橋くんはレーティング更新の対象なので、高橋くんのレーティングは 2676+52=2728 になります。

4 回の ARC を終えた後、高橋くんのレーティングは 2728 となっているので、2728 を出力してください。


入力例 2

2 3031
1 1000
2 -1000

出力例 2

3031

高橋くんはレッドコーダーなので、ARC でどのような成績を取ってもレーティングは変動しません。


入力例 3

15 2352
2 -889
2 420
2 -275
1 957
1 -411
1 -363
1 151
2 -193
2 289
2 -770
2 109
1 345
2 551
1 -702
1 355

出力例 3

1226

Score : 200 points

Problem Statement

AtCoder Regular Contest (ARC) is divided into two divisions.

  • In ARC Div. 1, participants whose rating at the start of the contest is between 1600 and 2799, inclusive, are subject to rating updates.
  • In ARC Div. 2, participants whose rating at the start of the contest is between 1200 and 2399, inclusive, are subject to rating updates.

Takahashi decided to participate in N ARCs.

Initially, his rating is R.

The i-th (1\leq i\leq N) ARC is Div. D _ i, and his performance in that contest is represented by an integer A _ i.

If he is subject to a rating update in the i-th ARC, let T be his rating at the start of that contest. Then, after the contest, his rating becomes T+A _ i.

If his is not subject to a rating update, his rating does not change.

Rating updates for ARCs are performed immediately after the contest ends, and whether he is subject to rating updates in the next contest is determined based on his rating after the update.

Find his rating after finishing the N ARCs.

He does not participate in any contests other than these N ARCs, and his rating does not change in other ways.

Constraints

  • 1\leq N\leq 100
  • 0\leq R\leq 4229
  • 1\leq D _ i\leq 2\ (1\leq i\leq N)
  • -1000\leq A _ i\leq 1000\ (1\leq i\leq N)
  • All input values are integers.

Input

The input is given in the following format from Standard Input:

N R
D _ 1 A _ 1
D _ 2 A _ 2
\vdots
D _ N A _ N

Output

Print Takahashi's rating after finishing the N ARCs.


Sample Input 1

4 1255
2 900
1 521
2 600
1 52

Sample Output 1

2728

Initially, Takahashi's rating is 1255.

For each contest, Takahashi's rating changes as follows:

  • The 1st ARC is Div. 2. He is subject to rating updates, so his rating becomes 1255+900=2155.
  • The 2nd ARC is Div. 1. He is subject to rating updates, so his rating becomes 2155+521=2676.
  • The 3rd ARC is Div. 2. He is not subject to rating updates, so his rating does not change.
  • The 4th ARC is Div. 1. He is subject to rating updates, so his rating becomes 2676+52=2728.

After the four ARCs, his rating is 2728, so print 2728.


Sample Input 2

2 3031
1 1000
2 -1000

Sample Output 2

3031

He is a Red coder, so his rating does not change upon his performance in ARC.


Sample Input 3

15 2352
2 -889
2 420
2 -275
1 957
1 -411
1 -363
1 151
2 -193
2 289
2 -770
2 109
1 345
2 551
1 -702
1 355

Sample Output 3

1226
D - Bombs

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

縦 R 行横 C 列の盤面があります。上から i 行目、左から j 列目のマスを (i,j) と表します。

(i,j) の現在の状態が文字 B_{i,j} として与えられます。 . は空きマス、# は壁があるマスを表し、 1, 2,\dots, 9 はそれぞれ威力 1,2,\dots,9 の爆弾があるマスを表します。

次の瞬間に、全ての爆弾が同時に爆発します。 爆弾が爆発すると、爆弾があるマスからのマンハッタン距離がその爆弾の威力以下であるような全てのマス(その爆弾があるマス自体を含む)が空きマスに変わります。 ここで、(r_1,c_1) から (r_2,c_2) までのマンハッタン距離は |r_1-r_2|+|c_1-c_2| です。

爆発後の盤面を出力してください。

制約

  • 1\leq R,C \leq 20
  • R,C は整数
  • B_{i,j} は ., #, 1, 2,\dots, 9 のいずれかである

入力

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

R C
B_{1,1}B_{1,2}\dots B_{1,C}
\vdots
B_{R,1}B_{R,2}\dots B_{R,C}

出力

爆発後の盤面を R 行で出力せよ。盤面の表し方は入力と同じ形式を用いること (R と C を出力する必要はない)。


入力例 1

4 4
.1.#
###.
.#2.
#.##

出力例 1

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

爆弾の効果範囲を表す図

  • (1,2) にある爆弾の爆発によって、上図の青いマスと紫のマスが空きマスに変わります。
  • (3,3) にある爆弾の爆発によって、上図の赤いマスと紫のマスが空きマスに変わります。

この例のように、爆弾が効果を及ぼす範囲に被りがあることもあります。


入力例 2

2 5
..#.#
###.#

出力例 2

..#.#
###.#

爆弾が 1 つもないこともあります。


入力例 3

2 3
11#
###

出力例 3

...
..#

入力例 4

4 6
#.#3#.
###.#.
##.###
#1..#.

出力例 4

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

Score : 200 points

Problem Statement

We have a board with R rows running horizontally and C columns running vertically. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

You are given characters B_{i,j} representing the current states of (i,j). . represents an empty square; # represents a square with a wall; 1, 2,\dots, 9 represent a square with a bomb of power 1,2,\dots,9, respectively.

At the next moment, all bombs will explode simultaneously. When a bomb explodes, every square whose Manhattan distance from the square with the bomb is not greater than the power of the bomb will turn into an empty square. Here, the Manhattan distance from (r_1,c_1) to (r_2,c_2) is |r_1-r_2|+|c_1-c_2|.

Print the board after the explosions.

Constraints

  • 1\leq R,C \leq 20
  • R and C are integers.
  • Each B_{i,j} is one of ., #, 1, 2, \dots, 9.

Input

The input is given from Standard Input in the following format:

R C
B_{1,1}B_{1,2}\dots B_{1,C}
\vdots
B_{R,1}B_{R,2}\dots B_{R,C}

Output

Print R lines representing the board after the explosions. Use the format used in the input (do not print R or C).


Sample Input 1

4 4
.1.#
###.
.#2.
#.##

Sample Output 1

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

Figure representing the explosion ranges of bombs

  • The explosion of the bomb at (1,2) will turn the blue squares and purple squares in the above figure into empty squares.
  • The explosion of the bomb at (3,3) will turn the red squares and purple squares in the above figure into empty squares.

As seen in this sample, the explosion ranges of bombs may overlap.


Sample Input 2

2 5
..#.#
###.#

Sample Output 2

..#.#
###.#

There may be no bombs.


Sample Input 3

2 3
11#
###

Sample Output 3

...
..#

Sample Input 4

4 6
#.#3#.
###.#.
##.###
#1..#.

Sample Output 4

......
#.....
#....#
....#.
E - Takahashi Gets Lost

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

H 行 W 列のグリッドがあります。

グリッドの各マスは陸か海のどちらかであり、 その情報は H 個の長さ W の文字列 S_1, S_2, \ldots, S_H で与えられます。 上から i 行目、左から j 列目のマスを (i, j) で表すと、 S_i の j 文字目が . のときマス (i, j) は陸であり、# のときマス (i, j) は海です。

ここで、グリッドの外周のマス(すなわち、i = 1 、i = H 、j = 1 、j = W のうち少なくとも 1 個以上を満たすマス (i, j) )については、すべて海であることが制約として保証されます。

高橋君が乗った宇宙船が、グリッド上のあるマスに不時着してしまいました。 その後、高橋君は L 、R 、U 、D のみからなる長さ N の文字列 T で表される手順に沿って、グリッド上を N 回移動しました。 i = 1, 2, \ldots, N について、T の i 文字目は i 回目の移動の内容を下記の通り表します。

  • L のとき、左に 1 マス移動したことを表す。すなわち、移動前のマスを (i, j) とするとき、移動後のマスは (i, j-1) である。
  • R のとき、右に 1 マス移動したことを表す。すなわち、移動前のマスを (i, j) とするとき、移動後のマスは (i, j+1) である。
  • U のとき、上に 1 マス移動したことを表す。すなわち、移動前のマスを (i, j) とするとき、移動後のマスは (i-1, j) である。
  • D のとき、下に 1 マス移動したことを表す。すなわち、移動前のマスを (i, j) とするとき、移動後のマスは (i+1, j) である。

高橋君の移動経路上のマス(不時着したマスおよび現在いるマスを含む)はいずれも海でないことがわかっています。 高橋君が現在いるマスとしてあり得るものの個数を出力してください。

制約

  • H, W, N は整数
  • 3 \leq H, W \leq 500
  • 1 \leq N \leq 500
  • T は L 、R 、U 、D のみからなる長さ N の文字列
  • S_i は . と # のみからなる長さ W の文字列
  • 高橋君が現在いるマスとしてあり得るものが少なくとも 1 個存在する。
  • グリッドの外周のマスはすべて海である。

入力

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

H W N
T
S_1
S_2
\vdots
S_H

出力

答えを出力せよ。


入力例 1

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

出力例 1

2

下記の 2 つの場合がありえるため、高橋君が現在いるマスとしてあり得るものは (3, 4) と (4, 5) の 2 個です。

  • マス (3, 5) に不時着し、(3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4) と移動した場合
  • マス (4, 6) に不時着し、(4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5) と移動した場合

入力例 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

出力例 2

6

Score: 250 points

Problem Statement

There is a grid with H rows and W columns.

Each cell of the grid is land or sea, which is represented by H strings S_1, S_2, \ldots, S_H of length W. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left, and (i, j) is land if the j-th character of S_i is ., and (i, j) is sea if the character is #.

The constraints guarantee that all cells on the perimeter of the grid (that is, the cells (i, j) that satisfy at least one of i = 1, i = H, j = 1, j = W) are sea.

Takahashi's spaceship has crash-landed on a cell in the grid. Afterward, he moved N times on the grid following the instructions represented by a string T of length N consisting of L, R, U, and D. For i = 1, 2, \ldots, N, the i-th character of T describes the i-th move as follows:

  • L indicates a move of one cell to the left. That is, if he is at (i, j) before the move, he will be at (i, j-1) after the move.
  • R indicates a move of one cell to the right. That is, if he is at (i, j) before the move, he will be at (i, j+1) after the move.
  • U indicates a move of one cell up. That is, if he is at (i, j) before the move, he will be at (i-1, j) after the move.
  • D indicates a move of one cell down. That is, if he is at (i, j) before the move, he will be at (i+1, j) after the move.

It is known that all cells along his path (including the cell where he crash-landed and the cell he is currently on) are not sea. Print the number of cells that could be his current position.

Constraints

  • H, W, and N are integers.
  • 3 \leq H, W \leq 500
  • 1 \leq N \leq 500
  • T is a string of length N consisting of L, R, U, and D.
  • S_i is a string of length W consisting of . and #.
  • There is at least one cell that could be Takahashi's current position.
  • All cells on the perimeter of the grid are sea.

Input

The input is given from Standard Input in the following format:

H W N
T
S_1
S_2
\vdots
S_H

Output

Print the answer.


Sample Input 1

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

Sample Output 1

2

The following two cases are possible, so there are two cells that could be Takahashi's current position: (3, 4) and (4, 5).

  • He crash-landed on cell (3, 5) and moved (3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4).
  • He crash-landed on cell (4, 6) and moved (4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5).

Sample Input 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

Sample Output 2

6
F - Simple path

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 頂点の木 T があり、 i (1\leq i\leq N-1) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

T 上の相異なる 2 頂点 X,Y が与えられるので、 頂点 X から頂点 Y への単純パス上の頂点(端点含む)を順に列挙してください。

ただし、木上の任意の相異なる 2 頂点 a,b について、a から b への単純パスがただ一つ存在することが証明できます。

単純パスとは? グラフ G 上の頂点 X,Y に対して、頂点列 v_1,v_2, \ldots, v_k であって、 v_1=X, v_k=Y かつ、1\leq i\leq k-1 に対して v_i と v_{i+1} が辺で結ばれているようなものを頂点 X から頂点 Y への パス と呼びます。 さらに、v_1,v_2, \ldots, v_k がすべて異なるようなものを頂点 X から頂点 Y への 単純パス と呼びます。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq X,Y\leq N
  • X\neq Y
  • 1\leq U_i,V_i\leq N
  • 入力はすべて整数
  • 与えられるグラフは木

入力

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

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

頂点 X から頂点 Y への単純パス上の頂点番号を順に空白区切りで出力せよ。


入力例 1

5 2 5
1 2
1 3
3 4
3 5

出力例 1

2 1 3 5

木 T は以下のような形であり、頂点 2 から頂点 5への単純パスは 頂点 2 \to 頂点 1 \to 頂点 3 \to 頂点 5 となります。
よって、2,1,3,5 をこの順に空白区切りで出力します。


入力例 2

6 1 2
3 1
2 5
1 2
4 1
2 6

出力例 2

1 2

木 T は以下のような形です。

Score : 300 points

Problem Statement

There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.

You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.

It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.

What is a simple path? For vertices X and Y in a graph G, a path from vertex X to vertex Y is a sequence of vertices v_1,v_2, \ldots, v_k such that v_1=X, v_k=Y, and v_i and v_{i+1} are connected by an edge for each 1\leq i\leq k-1. Additionally, if all of v_1,v_2, \ldots, v_k are distinct, the path is said to be a simple path from vertex X to vertex Y.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq X,Y\leq N
  • X\neq Y
  • 1\leq U_i,V_i\leq N
  • All values in the input are integers.
  • The given graph is a tree.

Input

The input is given from Standard Input in the following format:

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

Output

Print the indices of all vertices along the simple path from vertex X to vertex Y in order, with spaces in between.


Sample Input 1

5 2 5
1 2
1 3
3 4
3 5

Sample Output 1

2 1 3 5

The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.


Sample Input 2

6 1 2
3 1
2 5
1 2
4 1
2 6

Sample Output 2

1 2

The tree T is shown below.

G - Max Multiple

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

非負整数列 A=(a_1,a_2,\ldots,a_N) が与えられます。

A の(添え字が相異なる) K 個の項の和として考えられる非負整数の集合を S とします。

S に含まれる D の倍数の最大値を求めてください。ただし、S に D の倍数が含まれない場合、代わりに -1 と出力してください。

制約

  • 1 \leq K \leq N \leq 100
  • 1 \leq D \leq 100
  • 0 \leq a_i \leq 10^9
  • 入力はすべて整数

入力

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

N K D
a_1 \ldots a_N

出力

答えを出力せよ。


入力例 1

4 2 2
1 2 3 4

出力例 1

6

A から 2 個の項を選ぶ方法を列挙すると

  • a_1 と a_2 を選ぶ。選ばれた項の和は 1+2=3 となる。
  • a_1 と a_3 を選ぶ。選ばれた項の和は 1+3=4 となる。
  • a_1 と a_4 を選ぶ。選ばれた項の和は 1+4=5 となる。
  • a_2 と a_3 を選ぶ。選ばれた項の和は 2+3=5 となる。
  • a_2 と a_4 を選ぶ。選ばれた項の和は 2+4=6 となる。
  • a_3 と a_4 を選ぶ。選ばれた項の和は 3+4=7 となる。

となり、S=\{3,4,5,6,7\} となります。S に含まれる 2 の倍数のうち最大のものは 6 なので、6 と出力します。


入力例 2

3 1 2
1 3 5

出力例 2

-1

この例では S=\{1,3,5\} です。S に含まれる非負整数はいずれも 2 の倍数でないため、-1 と出力します。

Score : 400 points

Problem Statement

You are given a sequence of non-negative integers A=(a_1,a_2,\ldots,a_N).

Let S be the set of non-negative integers that can be the sum of K terms in A (with distinct indices).

Find the greatest multiple of D in S. If there is no multiple of D in S, print -1 instead.

Constraints

  • 1 \leq K \leq N \leq 100
  • 1 \leq D \leq 100
  • 0 \leq a_i \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N K D
a_1 \ldots a_N

Output

Print the answer.


Sample Input 1

4 2 2
1 2 3 4

Sample Output 1

6

Here are all the ways to choose two terms in A.

  • Choose a_1 and a_2, whose sum is 1+2=3.
  • Choose a_1 and a_3, whose sum is 1+3=4.
  • Choose a_1 and a_4, whose sum is 1+4=5.
  • Choose a_2 and a_3, whose sum is 2+3=5.
  • Choose a_2 and a_4, whose sum is 2+4=6.
  • Choose a_3 and a_4, whose sum is 3+4=7.

Thus, we have S=\{3,4,5,6,7\}. The greatest multiple of 2 in S is 6, so you should print 6.


Sample Input 2

3 1 2
1 3 5

Sample Output 2

-1

In this example, we have S=\{1,3,5\}. Nothing in S is a multiple of 2, so you should print -1.