Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋君はたこ焼きが好きです。
たこ焼き器を使うと、1 度に最大で X 個のたこ焼きを作ることができます。これにかかる時間は作る個数によらず T 分です。
N 個のたこ焼きを作るためには何分必要ですか？
制約
- 1 \leq N,X,T \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X T
出力
N 個のたこ焼きを作るために必要な時間の最小値を整数で出力せよ。
入力例 1
20 12 6
出力例 1
12
最初の 6 分で 12 個のたこ焼きを作れ、次の 6 分でさらに 8 個のたこ焼きを作れるので、計 12 分で 20 個のたこ焼きを作ることができます。
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.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 N が 9 の倍数であることと、N を十進法で表したときの各桁の数の和が 9 の倍数であることは同値です。
N が 9 の倍数であるか判定してください。
制約
- 0 \leq N < 10^{200000}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N が 9 の倍数ならば Yes、そうでないなら No を出力せよ。
入力例 1
123456789
出力例 1
Yes
各桁の数の和は 1+2+3+4+5+6+7+8+9=45 であり、45 は 9 の倍数なので、123456789 は 9 の倍数です。
入力例 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
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
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
全員に高さ 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.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
縦 H マス、横 W マスの H\times W マスからなる迷路があります。
上から i 行目、左から j 列目のマス (i,j) は、S_{ij} が # のとき壁であり、.のとき道です。
マス (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,2) まで歩いて移動し、(2,2) から (4,4) へワープ魔法で移動することで、ワープ魔法の使用回数を 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
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
H \times W マスの二次元グリッドがあります。この中には M 個の爆破対象があります。 i 個目の爆破対象の位置は \left(h_i, w_i \right)です。
高橋君は 1 つのマスを選び、そのマスに爆弾を設置し、起爆します。爆弾と同じ行または同じ列に存在する爆破対象が爆破されます。爆破対象が存在するマスに爆弾を設置することも出来ます。
高橋君は、爆破する爆破対象の数を最大化しようとしています。最大でいくつの爆破対象を爆破出来るか答えてください。
制約
- 入力は全て整数
- 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
爆弾を \left(1, 2\right) に設置することで、全ての爆破対象を爆破することが出来ます。
入力例 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
Output
Print the answer.
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
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 以上 N 以下の整数のうち一つが書かれた 3N 枚のカードが左右一列に並んでいます。 左から i 番目のカードに書かれた整数は A_i です。
以下の操作を N-1 回繰り返します。
- 左から 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
左から 5 枚のカードを並べ替え、カードに書かれた整数が左から順に 2\ 2\ 2\ 1\ 1\ 1 となるようにします。
左から 3 枚のカードを取り除き、このときこれら 3 枚のカードに書かれた整数はすべて 2 で等しいので 1 点を得ます。
カードに書かれた整数は左から順に 1\ 1\ 1 となります。
残った 3 枚のカードに書かれた整数はすべて 1 でこれも等しいので 1 点を得ます。
合計得点は 2 点となり、これが最高です。
入力例 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