A - Takoyaki

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

たこ焼き器を使うと、1 度に最大で X 個のたこ焼きを作ることができます。これにかかる時間は作る個数によらず T 分です。

N 個のたこ焼きを作るためには何分必要ですか？

制約

• 1 \leq N,X,T \leq 1000
• 入力は全て整数

入力

N X T


出力

N 個のたこ焼きを作るために必要な時間の最小値を整数で出力せよ。

入力例 1

20 12 6


出力例 1

12


6 分で 12 個作れるとは、1 分で 2 個作れるという意味ではないことに注意してください。

入力例 2

1000 1 1000


出力例 2

1000000


Score : 100 points

Problem Statement

Takahashi loves takoyaki - a ball-shaped snack.

With a takoyaki machine, he can make at most X pieces of takoyaki at a time, taking T minutes regardless of the number of pieces to make.

How long does it take to make N takoyaki?

Constraints

• 1 \leq N,X,T \leq 1000
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X T


Output

Print an integer representing the minimum number of minutes needed to make N pieces of takoyaki.

Sample Input 1

20 12 6


Sample Output 1

12


He can make 12 pieces of takoyaki in the first 6 minutes and 8 more in the next 6 minutes, so he can make 20 in a total of 12 minutes.

Note that being able to make 12 in 6 minutes does not mean he can make 2 in 1 minute.

Sample Input 2

1000 1 1000


Sample Output 2

1000000


It seems to take a long time to make this kind of takoyaki.

B - Multiple of 9

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N9 の倍数であるか判定してください。

制約

• 0 \leq N < 10^{200000}
• N は整数

入力

N


出力

N9 の倍数ならば Yes、そうでないなら No を出力せよ。

入力例 1

123456789


出力例 1

Yes


入力例 2

0


出力例 2

Yes


入力例 3

31415926535897932384626433832795028841971693993751058209749445923078164062862089986280


出力例 3

No


Score : 200 points

Problem Statement

An integer N is a multiple of 9 if and only if the sum of the digits in the decimal representation of N is a multiple of 9.

Determine whether N is a multiple of 9.

Constraints

• 0 \leq N < 10^{200000}
• N is an integer.

Input

Input is given from Standard Input in the following format:

N


Output

If N is a multiple of 9, print Yes; otherwise, print No.

Sample Input 1

123456789


Sample Output 1

Yes


The sum of these digits is 1+2+3+4+5+6+7+8+9=45, which is a multiple of 9, so 123456789 is a multiple of 9.

Sample Input 2

0


Sample Output 2

Yes


Sample Input 3

31415926535897932384626433832795028841971693993751058209749445923078164062862089986280


Sample Output 3

No

C - Step

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N 人が 1 列に並んでおり、前から i 番目の人の身長は A_i です。

それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。

この条件を満たす時の、踏み台の高さの合計の最小値を求めてください。

制約

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• 入力は全て整数

入力

N
A_1 \ldots A_N


入力例 1

5
2 1 5 4 3


出力例 1

4


それぞれ、高さ 0,1,0,1,2 の踏み台を与えると、踏み台を込めた身長は 2,2,5,5,5 となり、条件を満たします。

入力例 2

5
3 3 3 3 3


出力例 2

0


Score : 300 points

Problem Statement

N persons are standing in a row. The height of the i-th person from the front is A_i.

We want to have each person stand on a stool of some heights - at least zero - so that the following condition is satisfied for every person:

Condition: Nobody in front of the person is taller than the person. Here, the height of a person includes the stool.

Find the minimum total height of the stools needed to meet this goal.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N


Output

Print the minimum total height of the stools needed to meet the goal.

Sample Input 1

5
2 1 5 4 3


Sample Output 1

4


If the persons stand on stools of heights 0, 1, 0, 1, and 2, respectively, their heights will be 2, 2, 5, 5, and 5, satisfying the condition.

We cannot meet the goal with a smaller total height of the stools.

Sample Input 2

5
3 3 3 3 3


Sample Output 2

0


Giving a stool of height 0 to everyone will work.

D - Wizard in Maze

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

H マス、横 W マスの H\times W マスからなる迷路があります。

マス (C_h,C_w) に魔法使いがいます。魔法使いは次の 2 種類の方法で移動することができます。

• 移動A：現在いるマスと上下左右に隣接する道のマスへ歩いて移動する。
• 移動B：現在いるマスを中心とする 5\times 5 の範囲内にある道のマスへワープ魔法で移動する。

どちらの行動でも、迷路の外へ移動することはできません。

マス (D_h,D_w) まで移動するには、ワープ魔法を最低で何度使う必要があるでしょうか。

制約

• 1 \leq H,W \leq 10^3
• 1 \leq C_h,D_h \leq H
• 1 \leq C_w,D_w \leq W
• S_{ij}#.
• S_{C_h C_w}S_{D_h D_w}.
• (C_h,C_w) \neq (D_h,D_w)

入力

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}


出力

ワープ魔法を使う最小回数を出力せよ。(D_h,D_w) に到達不可能な場合、かわりに -1 と出力せよ。

入力例 1

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


出力例 1

1


入力例 2

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


出力例 2

-1


入力例 3

4 4
2 2
3 3
....
....
....
....


出力例 3

0


ワープ魔法を使う必要はありません。

入力例 4

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


出力例 4

2


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

• Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.
• Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

• 1 \leq H,W \leq 10^3
• 1 \leq C_h,D_h \leq H
• 1 \leq C_w,D_w \leq W
• S_{ij} is # or ..
• S_{C_h C_w} and S_{D_h D_w} are ..
• (C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}


Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

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


Sample Output 1

1


For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

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


Sample Output 2

-1


He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....


Sample Output 3

0


No use of magic is needed.

Sample Input 4

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


Sample Output 4

2

E - Bomber

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

H \times W マスの二次元グリッドがあります。この中には M 個の爆破対象があります。 i 個目の爆破対象の位置は \left(h_i, w_i \right)です。

制約

• 入力は全て整数
• 1 \leq H, W \leq 3 \times 10^5
• 1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)
• 1 \leq h_i \leq H
• 1 \leq w_i \leq W
• \left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)

入力

H W M
h_1 w_1
\vdots
h_M w_M


入力例 1

2 3 3
2 2
1 1
1 3


出力例 1

3


入力例 2

3 3 4
3 3
3 1
1 1
1 2


出力例 2

3


入力例 3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4


出力例 3

6


Score : 500 points

Problem Statement

We have a two-dimensional grid with H \times W squares. There are M targets to destroy in this grid - the position of the i-th target is \left(h_i, w_i \right).

Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.

Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.

Constraints

• All values in input are integers.
• 1 \leq H, W \leq 3 \times 10^5
• 1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)
• 1 \leq h_i \leq H
• 1 \leq w_i \leq W
• \left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M


Sample Input 1

2 3 3
2 2
1 1
1 3


Sample Output 1

3


We can destroy all the targets by placing the bomb at \left(1, 2\right).

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2


Sample Output 2

3


Sample Input 3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4


Sample Output 3

6

F - Brave CHAIN

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

1 以上 N 以下の整数のうち一つが書かれた 3N 枚のカードが左右一列に並んでいます。 左から i 番目のカードに書かれた整数は A_i です。

• 左から 5 枚のカードを好きな順に並び替える。その後、左から 3 枚のカードを取り除く。このとき、その 3 枚のカードに書かれた整数がすべて等しければ 1 点を得る。

N-1 回の操作の後、残った 3 枚のカードに書かれた整数がすべて等しければ追加で 1 点を得ます。

制約

• 1 \leq N \leq 2000
• 1 \leq A_i \leq N

入力

N
A_1 A_2 \cdots A_{3N}


入力例 1

2
1 2 1 2 2 1


出力例 1

2


カードに書かれた整数は左から順に 1\ 1\ 1 となります。

入力例 2

3
1 1 2 2 3 3 3 2 1


出力例 2

1


入力例 3

3
1 1 2 2 2 3 3 3 1


出力例 3

3


Score : 600 points

Problem Statement

We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i-th card from the left is A_i.

You will do the following operation N-1 times:

• Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.

After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.

Find the maximum number of points you can gain.

Constraints

• 1 \leq N \leq 2000
• 1 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_{3N}


Output

Print the maximum number of points you can gain.

Sample Input 1

2
1 2 1 2 2 1


Sample Output 1

2


Let us rearrange the five leftmost cards so that the integers written on the six cards will be 2\ 2\ 2\ 1\ 1\ 1 from left to right.

Then, remove the three leftmost cards, all of which have the same integer 2, gaining 1 point.

Now, the integers written on the remaining cards are 1\ 1\ 1.

Since these three cards have the same integer 1, we gain 1 more point.

In this way, we can gain 2 points - which is the maximum possible.

Sample Input 2

3
1 1 2 2 3 3 3 2 1


Sample Output 2

1


Sample Input 3

3
1 1 2 2 2 3 3 3 1


Sample Output 3

3