Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
スーパーマーケットで卵のパックが売られています。
卵 6 個入りのパックは S 円、卵 8 個入りのパックは M 円、卵 12 個入りのパックは L 円です。
どのパックも何パックでも購入できるとき、N 個以上の卵を買うために必要な最小の金額を求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq S,M,L \leq 10^4
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N S M L
出力
答えを出力せよ。
入力例 1
16 120 150 200
出力例 1
300
8 個入りのパックを 2 個買うのが最適です。
入力例 2
10 100 50 10
出力例 2
10
12 個入りのパックを 1 個買うのが最適です。
入力例 3
99 600 800 1200
出力例 3
10000
8 個入りのパックと 12 個入りのパックを 5 個ずつ買うのが最適です。
Score : 200 points
Problem Statement
A supermarket sells egg packs.
A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.
When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.
Constraints
- 1 \leq N \leq 100
- 1 \leq S,M,L \leq 10^4
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S M L
Output
Print the answer.
Sample Input 1
16 120 150 200
Sample Output 1
300
It is optimal to buy two 8-egg packs.
Sample Input 2
10 100 50 10
Sample Output 2
10
It is optimal to buy one 12-egg pack.
Sample Input 3
99 600 800 1200
Sample Output 3
10000
It is optimal to buy five 8-egg packs and five 12-egg packs.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 8 マス、横 8 マスの 64 マスからなるマス目があります。 上から i 行目 (1\leq i\leq8) 、左から j 列目 (1\leq j\leq8) のマスをマス (i,j) と呼ぶことにします。
それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。
マスの状態は長さ 8 の文字列からなる長さ 8 の列 (S _ 1,S _ 2,S _ 3,\ldots,S _ 8) で表されます。
マス (i,j) (1\leq i\leq8,1\leq j\leq8) は、S _ i の j 文字目が . のとき空マスで、# のときコマが置かれています。
あなたは、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。
マス (i,j) に置かれているコマは、次のどちらかの条件を満たすコマを取ることができます。
- i 行目のマスに置かれている
- j 列目のマスに置かれている
たとえば、マス (4,4) に置かれているコマは、以下の図で青く示されたマスに置かれているコマを取ることができます。
あなたがコマを置くことができるマスがいくつあるか求めてください。
制約
- S _ i は
.,#からなる長さ 8 の文字列 (1\leq i\leq 8)
入力
入力は以下の形式で標準入力から与えられる。
S _ 1 S _ 2 S _ 3 S _ 4 S _ 5 S _ 6 S _ 7 S _ 8
出力
すでに置かれているコマに取られずに自分のコマを置くことができる空マスの個数を出力せよ。
入力例 1
...#.... #....... .......# ....#... .#...... ........ ........ ..#.....
出力例 1
4
すでに置かれているコマは、以下の図で青く示されたマスに置かれたコマを取ることができます。
よって、あなたがすでに置かれているコマに取られないように自分のコマを置くことができるマスはマス (6,6), マス (6,7), マス (7,6), マス (7,7) の 4 マスです。
入力例 2
........ ........ ........ ........ ........ ........ ........ ........
出力例 2
64
コマがひとつも置かれていないこともあります。
入力例 3
.#...... ..#..#.. ....#... ........ ..#....# ........ ...#.... ....#...
出力例 3
4
Score : 200 points
Problem Statement
There is a grid of 64 squares with 8 rows and 8 columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq8) and j-th column from the left (1\leq j\leq8).
Each square is either empty or has a piece placed on it.
The state of the squares is represented by a sequence (S_1,S_2,S_3,\ldots,S_8) of 8 strings of length 8.
Square (i,j) (1\leq i\leq8,1\leq j\leq8) is empty if the j-th character of S_i is ., and has a piece if it is #.
You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.
A piece placed on square (i,j) can capture pieces that satisfy either of the following conditions:
- Placed on a square in row i
- Placed on a square in column j
For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:
How many squares can you place your piece on?
Constraints
- Each S_i is a string of length 8 consisting of
.and#(1\leq i\leq 8).
Input
The input is given from Standard Input in the following format:
S_1 S_2 S_3 S_4 S_5 S_6 S_7 S_8
Output
Print the number of empty squares where you can place your piece without it being captured by any existing pieces.
Sample Input 1
...#.... #....... .......# ....#... .#...... ........ ........ ..#.....
Sample Output 1
4
The existing pieces can capture pieces placed on the squares shown in blue in the following figure:
Therefore, you can place your piece without it being captured on 4 squares: square (6,6), square (6,7), square (7,6), and square (7,7).
Sample Input 2
........ ........ ........ ........ ........ ........ ........ ........
Sample Output 2
64
There may be no pieces on the grid.
Sample Input 3
.#...... ..#..#.. ....#... ........ ..#....# ........ ...#.... ....#...
Sample Output 3
4
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個の餅が小さいほうから順に並んでいます。 i 番目 (1\leq i\leq N) の餅の大きさは A _ i です。
2 つの餅 A,B の大きさをそれぞれ a,b としたとき、a が b の半分以下であるとき、かつそのときに限り、餅 A を餅 B の上に乗せて鏡餅を 1 つ作ることができます。
N 個の餅から 2 つの餅を選び、一方をもう一方の上に乗せることで鏡餅を 1 つ作ります。
何種類の鏡餅を作ることができるか求めてください。
ただし、鏡餅を構成する餅の大きさが同じでも、少なくとも一方が異なる餅であれば別の種類の鏡餅として数えます。
制約
- 2\leq N\leq 5\times 10 ^ 5
- 1\leq A _ i\leq 10 ^ 9\ (1\leq i\leq N)
- A _ i\leq A _ {i+1}\ (1\leq i\lt N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \cdots A _ N
出力
作ることができる鏡餅の種類数を出力せよ。
入力例 1
6 2 3 4 4 7 10
出力例 1
8
与えられた餅の大きさは以下のようになっています。
このとき、以下の 8 種類の鏡餅を作ることができます。
大きさ 4 の餅の上に大きさ 2 の餅を乗せた鏡餅や、大きさ 10 の餅の上に大きさ 4 の餅を乗せた鏡餅は 2 種類あることに注意してください。
入力例 2
3 387 388 389
出力例 2
0
鏡餅を 1 種類も作ることができない場合もあります。
入力例 3
32 1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641
出力例 3
388
Score : 300 points
Problem Statement
There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.
Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.
You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.
Find how many different kinds of kagamimochi can be made.
Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.
Constraints
- 2 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
- A_i \leq A_{i+1} \ (1 \leq i < N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the number of different kinds of kagamimochi that can be made.
Sample Input 1
6 2 3 4 4 7 10
Sample Output 1
8
The sizes of the given mochi are as follows:
In this case, you can make the following eight kinds of kagamimochi:
Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.
Sample Input 2
3 387 388 389
Sample Output 2
0
It is possible that you cannot make any kagamimochi.
Sample Input 3
32 1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641
Sample Output 3
388
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個の黒色のボールと M 個の白色のボールがあります。
ボールにはそれぞれ価値がつけられており、i\ (1\leq i\leq N) 個目の黒色のボールの価値は B_i、j\ (1\leq j\leq M) 個目の白色のボールの価値は W_j です。
黒色のボールの個数が白色のボールの個数以上になるようにボールを 0 個以上選ぶとき、選んだボールの価値の総和としてありうる最大値を求めてください。
制約
- 1\leq N,M\leq 2\times 10^5
- -10^9\leq B_i,W_j\leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M B_1 B_2 \ldots B_N W_1 W_2 \ldots W_M
出力
答えを出力せよ。
入力例 1
4 3 8 5 -1 3 3 -2 -4
出力例 1
19
1,2,4 個目の黒色のボールと 1 個目の白色のボールを選ぶとき、選んだボールの価値の総和は 8+5+3+3=19 となりこれが最大です。
入力例 2
4 3 5 -10 -2 -5 8 1 4
出力例 2
15
1,3 個目の黒色のボールと 1,3 個目の白色のボールを選ぶとき、選んだボールの価値の総和は 5+(-2)+8+4=15 となりこれが最大です。
入力例 3
3 5 -36 -33 -31 12 12 28 24 27
出力例 3
0
ボールを 1 つも選ばないことも可能です。
Score : 300 points
Problem Statement
There are N black balls and M white balls.
Each ball has a value. The value of the i-th black ball (1 \le i \le N) is B_i, and the value of the j-th white ball (1 \le j \le M) is W_j.
Choose zero or more balls so that the number of black balls chosen is at least the number of white balls chosen. Among all such choices, find the maximum possible sum of the values of the chosen balls.
Constraints
- 1 \leq N,M \leq 2\times 10^5
- -10^9 \leq B_i, W_j \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M B_1 B_2 \ldots B_N W_1 W_2 \ldots W_M
Output
Print the answer.
Sample Input 1
4 3 8 5 -1 3 3 -2 -4
Sample Output 1
19
If you choose the 1st, 2nd, and 4th black balls, and the 1st white ball, the sum of their values is 8+5+3+3=19, which is the maximum.
Sample Input 2
4 3 5 -10 -2 -5 8 1 4
Sample Output 2
15
If you choose the 1st and 3rd black balls, and the 1st and 3rd white balls, the sum of their values is 5+(-2)+8+4=15, which is the maximum.
Sample Input 3
3 5 -36 -33 -31 12 12 28 24 27
Sample Output 3
0
It is possible to choose no balls.
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N 行 N 列のグリッドがあり、各マスは空きマスか障害物のあるマスのいずれかです。グリッドの上から i 行目、左から j 列目のマスを (i, j) と表記します。
また、2 人のプレイヤーがグリッド上の相異なる空きマス上におり、各マスの情報は N 個の長さ N の文字列 S_1, S_2, \ldots, S_N として以下の形式で与えられます。
-
S_i の j 文字目が
Pであるとき、(i, j) は空きマスであり、プレイヤーがいる -
S_i の j 文字目が
.であるとき、(i, j) は空きマスであり、プレイヤーがいない -
S_i の j 文字目が
#であるとき、(i, j) は障害物のあるマスである
以下の操作を繰り返し 2 人のプレイヤーを同じマスに集めるために必要な操作回数の最小値を求めてください。ただし、操作の繰り返しにより 2 人のプレイヤーを同じマスに集めることができない場合には -1 を出力してください。
- 上下左右のいずれかの方向を決める。そして各プレイヤーはともにその方向に隣接するマスへの移動を試みる。各プレイヤーは移動先のマスが存在し、かつ空きマスであるならば移動し、そうでないならば移動しない。
制約
- N は 2 以上 60 以下の整数
- S_i は長さ N の
P,.,#からなる文字列 - S_i の j 文字目が
Pであるような組 (i, j) の個数はちょうど 2 つ
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
5 ....# #..#. .P... ..P.. ....#
出力例 1
3
はじめに (3, 2) にいるプレイヤーをプレイヤー 1、(4, 3) にいるプレイヤーをプレイヤー 2 とします。
例えば以下のようにすることで、3 回の操作で 2 人のプレイヤーが同じマスに集まります。
-
左を選択する。プレイヤー 1 は (3, 1) に移動し、プレイヤー 2 は (4, 2) に移動する。
-
上を選択する。プレイヤー 1 は移動せず、プレイヤー 2 は (3, 2) に移動する。
-
左を選択する。プレイヤー 1 は移動せず、プレイヤー 2 は (3, 1) に移動する。
入力例 2
2 P# #P
出力例 2
-1
入力例 3
10 .......... .......... .......... .......... ....P..... .....P.... .......... .......... .......... ..........
出力例 3
10
Score: 400 points
Problem Statement
There is an N \times N grid, where each cell is either empty or contains an obstacle. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.
There are also two players on distinct empty cells of the grid. The information about each cell is given as N strings S_1, S_2, \ldots, S_N of length N, in the following format:
-
If the j-th character of S_i is
P, then (i, j) is an empty cell with a player on it. -
If the j-th character of S_i is
., then (i, j) is an empty cell without a player. -
If the j-th character of S_i is
#, then (i, j) contains an obstacle.
Find the minimum number of moves required to bring the two players to the same cell by repeating the following operation. If it is impossible to bring the two players to the same cell by repeating the operation, print -1.
- Choose one of the four directions: up, down, left, or right. Then, each player attempts to move to the adjacent cell in that direction. Each player moves if the destination cell exists and is empty, and does not move otherwise.
Constraints
- N is an integer between 2 and 60, inclusive.
- S_i is a string of length N consisting of
P,., and#. - There are exactly two pairs (i, j) where the j-th character of S_i is
P.
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
5 ....# #..#. .P... ..P.. ....#
Sample Output 1
3
Let us call the player starting at (3, 2) Player 1 and the player starting at (4, 3) Player 2.
For example, doing the following brings the two players to the same cell in three moves:
-
Choose left. Player 1 moves to (3, 1), and Player 2 moves to (4, 2).
-
Choose up. Player 1 does not move, and Player 2 moves to (3, 2).
-
Choose left. Player 1 does not move, and Player 2 moves to (3, 1).
Sample Input 2
2 P# #P
Sample Output 2
-1
Sample Input 3
10 .......... .......... .......... .......... ....P..... .....P.... .......... .......... .......... ..........
Sample Output 3
10