Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英小文字からなる長さが奇数の文字列 S が与えられます。
S の中央の文字を出力してください。
中央の文字とは
ある長さが奇数の文字列 T について、 T の長さを |T| として、T の前から \frac{|T|+1}{2} 番目の文字を中央の文字とします。制約
- S は英小文字からなる長さが奇数の文字列
- S の長さは 1 以上 99 以下
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
atcoder
出力例 1
o
atcoder の中央の文字は o です。
入力例 2
a
出力例 2
a
Score : 100 points
Problem Statement
You are given an odd-length string S consisting of lowercase English letters.
Print the central character of S.
What is the central character?
For an odd-length string T, its central character is the \frac{|T|+1}{2}-th character from the beginning, where |T| is the length of T.Constraints
- S is an odd-length string consisting of lowercase English letters.
- The length of S is between 1 and 99 (inclusive).
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
atcoder
Sample Output 1
o
The central character of atcoder is o.
Sample Input 2
a
Sample Output 2
a
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
整数 K が与えられます。
英大文字を A から昇順に K 個繋げて得られる文字列を答えてください。
制約
- K は 1 以上 26 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
K
出力
答えを出力せよ。
入力例 1
3
出力例 1
ABC
英大文字は A から昇順に A, B, C, ... です。
A から昇順に 3 個繋げて得られる文字列は ABC です。
入力例 2
1
出力例 2
A
Score : 100 points
Problem Statement
You are given an integer K.
Print a string that is a concatenation of the first K uppercase English letters in ascending order, starting from A.
Constraints
- K is an integer between 1 and 26, inclusive.
Input
The input is given from Standard Input in the following format:
K
Output
Print the answer.
Sample Input 1
3
Sample Output 1
ABC
The uppercase English letters in ascending order are A, B, C, ...
By concatenating the first three uppercase English letters, we get ABC.
Sample Input 2
1
Sample Output 2
A
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君の家には N 個の食品があり、i 番目の食品のおいしさは A_i です。
また、高橋君には嫌いな食品が K 個あり、具体的には i=1,2,\ldots,K について、B_i 番目の食品が嫌いです。
高橋君は N 個の食品のうち、おいしさが最大の食品から 1 つを選んで食べようと考えています。
高橋君が嫌いな食品を食べる可能性があるならば Yes を、食べる可能性が無いならば No を出力してください。
制約
- 1\leq K\leq N\leq 100
- 1\leq A_i\leq 100
- 1\leq B_i\leq N
- B_i はすべて相異なる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N B_1 B_2 \ldots B_K
出力
高橋君が嫌いな食品を食べる可能性があるならば Yes を、無いならば No を出力せよ。
入力例 1
5 3 6 8 10 7 10 2 3 4
出力例 1
Yes
5 個の食品の中でおいしさが最大の食品は食品 3 と 5 の 2 つであり、この 2 つのいずれかを食べます。
高橋君が嫌いな食品は 2,3,4 の 3 つであり、そのうち食品 3 を食べる可能性があります。
よって、Yes を出力します。
入力例 2
5 2 100 100 100 1 1 5 4
出力例 2
No
おいしさが最大の食品は食品 1,2,3 の 3 つであり、高橋君は嫌いな食品を食べる可能性はありません。
入力例 3
2 1 100 1 2
出力例 3
No
おいしさが最大の食品は食品 1 であり、高橋君は嫌いな食品を食べる可能性はありません。
Score : 200 points
Problem Statement
Takahashi has N foods in his house. The i-th food has the tastiness of A_i.
He dislikes K of these foods: for each i=1,2,\ldots,K, he dislikes the B_i-th food.
Out of the foods with the greatest tastiness among the N foods, Takahashi will randomly choose one and eat it.
If he has a chance to eat something he dislikes, print Yes; otherwise, print No.
Constraints
- 1\leq K\leq N\leq 100
- 1\leq A_i\leq 100
- 1\leq B_i\leq N
- All B_i are distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N B_1 B_2 \ldots B_K
Output
If Takahashi has a chance to eat a food he dislikes, print Yes; otherwise, print No.
Sample Input 1
5 3 6 8 10 7 10 2 3 4
Sample Output 1
Yes
Among the five foods, the ones with the greatest tastiness are Food 3 and 5, of which he eats one.
He dislikes Food 2, 3, and 4, one of which he has a chance to eat: Food 3.
Therefore, the answer is Yes.
Sample Input 2
5 2 100 100 100 1 1 5 4
Sample Output 2
No
The foods with the greatest tastiness are Food 1, 2, and 3, none of which he has a chance to eat.
Sample Input 3
2 1 100 1 2
Sample Output 3
No
The food with the greatest tastiness is Food 1, which he has no chance to eat.
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
配点 : 300 点
問題文
H_1 行 W_1 列の行列 A と、H_2 行 W_2 列の行列 B が与えられます。
- 1 \leq i \leq H_1 かつ 1 \leq j \leq W_1 を満たす整数の組 (i, j) について、行列 A の i 行目 j 列目の要素は A_{i, j} です。
- 1 \leq i \leq H_2 かつ 1 \leq j \leq W_2 を満たす整数の組 (i, j) について、行列 B の i 行目 j 列目の要素は B_{i, j} です。
行列 A に対して、下記の 2 つの操作のうちどちらかを行うことを、好きなだけ（ 0 回でも良い）繰り返すことができます。
- A の行を任意に 1 つ選んで削除する。
- A の列を任意に 1 つ選んで削除する。
行列 A を行列 B に一致させることができるかどうかを判定して下さい。
制約
- 1 \leq H_2 \leq H_1 \leq 10
- 1 \leq W_2 \leq W_1 \leq 10
- 1 \leq A_{i, j} \leq 10^9
- 1 \leq B_{i, j} \leq 10^9
- 入力中の値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}
出力
行列 A を行列 B に一致させることができる場合は Yes を、
一致させることができない場合は No を出力せよ。
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。
入力例 1
4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 3 6 8 9 16 18 19
出力例 1
Yes
初期状態の行列 A から 2 列目を削除すると、行列 A は
1 3 4 5 6 8 9 10 11 13 14 15 16 18 19 20
となります。そこからさらに 3 行目を削除すると、行列 A は
1 3 4 5 6 8 9 10 16 18 19 20
となります。そこからさらに 1 行目を削除すると、行列 A は
6 8 9 10 16 18 19 20
となります。そこからさらに 4 列目を削除すると、行列 A は
6 8 9 16 18 19
となります。これは行列 B と一致します。
操作の繰り返しによって行列 A を行列 B に一致させることができるので Yes を出力します。
入力例 2
3 3 1 1 1 1 1 1 1 1 1 1 1 2
出力例 2
No
どのように操作を行っても、 行列 A を行列 B に一致させることはできません。
よって、No を出力します。
Score : 300 points
Problem Statement
You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.
- For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
- For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.
You may perform the following operations on the matrix A any number of (possibly 0) times in any order:
- Choose an arbitrary row of A and remove it.
- Choose an arbitrary column of A and remove it.
Determine if it is possible to make the matrix A equal the matrix B.
Constraints
- 1 \leq H_2 \leq H_1 \leq 10
- 1 \leq W_2 \leq W_1 \leq 10
- 1 \leq A_{i, j} \leq 10^9
- 1 \leq B_{i, j} \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}
Output
Print Yes if it is possible to make the matrix A equal the matrix B;
print No otherwise.
Note that the judge is case-sensitive.
Sample Input 1
4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 3 6 8 9 16 18 19
Sample Output 1
Yes
Removing the 2-nd column from the initial A results in:
1 3 4 5 6 8 9 10 11 13 14 15 16 18 19 20
Then, removing the 3-rd row from A results in:
1 3 4 5 6 8 9 10 16 18 19 20
Then, removing the 1-st row from A results in:
6 8 9 10 16 18 19 20
Then, removing the 4-th column from A results in:
6 8 9 16 18 19
Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.
Sample Input 2
3 3 1 1 1 1 1 1 1 1 1 1 1 2
Sample Output 2
No
Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B,
so No should be printed.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
高橋君は医者のすぬけ君から N 種類の薬を処方されました。i 種類目の薬は(処方された日を含めて) a_i 日間、毎日 b_i 錠ずつ飲む必要があります。また、高橋君はこれ以外の薬を飲む必要がありません。
薬を処方された日を 1 日目とします。1 日目以降で、初めて高橋君がその日に飲む必要がある薬が K 錠以下になるのは何日目かを求めてください。
制約
- 1 \leq N \leq 3 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq a_i,b_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K a_1 b_1 \vdots a_N b_N
出力
1 日目以降で、初めて高橋君がその日に飲む必要がある薬が K 錠以下になるのが X 日目の時、 X を出力せよ。
入力例 1
4 8 6 3 2 5 1 9 4 2
出力例 1
3
1 日目には、高橋君は 1,2,3,4 種類目の薬をそれぞれ 3,5,9,2 錠飲む必要があります。よってこの日は 19 錠飲む必要があり、K(=8) 錠以下ではありません。
2 日目には、高橋君は 1,2,4 種類目の薬をそれぞれ 3,5,2 錠飲む必要があります。よってこの日は 10 錠飲む必要があり、K(=8) 錠以下ではありません。
3 日目には、高橋君は 1,4 種類目の薬をそれぞれ 3,2 錠飲む必要があります。よってこの日は 5 錠飲む必要があり、初めて K(=8) 錠以下になります。
以上より、3 が答えです。
入力例 2
4 100 6 3 2 5 1 9 4 2
出力例 2
1
入力例 3
15 158260522 877914575 2436426 24979445 61648772 623690081 33933447 476190629 62703497 211047202 71407775 628894325 31963982 822804784 50968417 430302156 82631932 161735902 80895728 923078537 7723857 189330739 10286918 802329211 4539679 303238506 17063340 492686568 73361868 125660016 50287940
出力例 3
492686569
Score : 350 points
Problem Statement
Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.
Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?
Constraints
- 1 \leq N \leq 3 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq a_i,b_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K a_1 b_1 \vdots a_N b_N
Output
If Takahashi has to take K pills or less on day X for the first time on or after day 1, print X.
Sample Input 1
4 8 6 3 2 5 1 9 4 2
Sample Output 1
3
On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.
Thus, the answer is 3.
Sample Input 2
4 100 6 3 2 5 1 9 4 2
Sample Output 2
1
Sample Input 3
15 158260522 877914575 2436426 24979445 61648772 623690081 33933447 476190629 62703497 211047202 71407775 628894325 31963982 822804784 50968417 430302156 82631932 161735902 80895728 923078537 7723857 189330739 10286918 802329211 4539679 303238506 17063340 492686568 73361868 125660016 50287940
Sample Output 3
492686569
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
整数 N が与えられます。以下の条件を満たす N 以下の正整数の組 (i,j) の個数を求めてください。
- i \times j は平方数である。
制約
- 1 \le N \le 2 \times 10^5
- N は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
6
(1,1),(1,4),(2,2),(3,3),(4,1),(4,4) の 6 個が条件を満たします。
(2,3) は 2 \times 3 =6 が平方数でないため条件を満たしません。
入力例 2
254
出力例 2
896
Score : 400 points
Problem Statement
You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:
- i \times j is a square number.
Constraints
- 1 \le N \le 2 \times 10^5
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
6
The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.
On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.
Sample Input 2
254
Sample Output 2
896
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
H 行 W 列の格子状の区画に区切られた街があります。上から i 行目、左から j 列目の区画は、S_{i,j} が . のとき道、# のとき塀です。
高橋君は自分の家から魚屋に買い物に行くことにしました。高橋君の家は街の左上隅の区画にあり、魚屋は街の右下隅の区画にあります。
高橋君は、自分がいる区画から上下左右に隣接する道の区画に移動することができます。街の外に出ることはできません。
塀の区画に移動することはできませんが、高橋君は非常に腕力が強いため、パンチを 1 回繰り出すことで任意の 2\times 2 の区画内の塀を壊して道にすることができます。
高橋君が魚屋にたどり着くためには、最低何回パンチを繰り出せばよいか求めてください。
制約
- 2 \leq H,W \leq 500
- H,W は整数
- S_{i,j} は
.または# - S_{1,1} と S_{H,W} は
.
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1} \ldots S_{1,W}
\vdots
S_{H,1} \ldots S_{H,W}
出力
答えを出力せよ。
入力例 1
5 5 ..#.. #.#.# ##.## #.#.# ..#..
出力例 1
1
例えば、以下の * で表す 2\times 2 の区画にある塀を破壊すると魚屋にたどり着くことができます。
..#.. #.**# ##**# #.#.# ..#..
破壊対象の 2 \times 2 の区画の全てが塀である必要はありません。
入力例 2
5 7 ....... ######. ....... .###### .......
出力例 2
0
遠回りが必要ですが、塀を破壊することなく魚屋にたどり着くことができます。
入力例 3
8 8 .####### ######## ######## ######## ######## ######## ######## #######.
出力例 3
5
Score : 500 points
Problem Statement
There is a town divided into a grid of cells with H rows and W columns. The cell at the i-th row from the top and j-th column from the left is a passable space if S_{i,j} is . and a block if S_{i,j} is #.
Takahashi will go from his house to a fish market. His house is in the cell at the top-left corner, and the fish market is in the cell at the bottom-right corner.
Takahashi can move one cell up, down, left, or right to a passable cell. He cannot leave the town. He cannot enter a block, either. However, his physical strength allows him to destroy all blocks in a square region with 2\times 2 cells of his choice with one punch, making these cells passable.
Find the minimum number of punches needed for Takahashi to reach the fish market.
Constraints
- 2 \leq H,W \leq 500
- H and W are integers.
- S_{i,j} is
.or#. - S_{1,1} and S_{H,W} are
..
Input
Input is given from Standard Input in the following format:
H W
S_{1,1} \ldots S_{1,W}
\vdots
S_{H,1} \ldots S_{H,W}
Output
Print the answer.
Sample Input 1
5 5 ..#.. #.#.# ##.## #.#.# ..#..
Sample Output 1
1
He can reach the fish market by, for example, destroying the blocks in the square region with 2\times 2 cells marked * below.
..#.. #.**# ##**# #.#.# ..#..
It is not required that all of the 2\times 2 cells in the region to punch are blocks.
Sample Input 2
5 7 ....... ######. ....... .###### .......
Sample Output 2
0
He can reach the fish market without destroying blocks, though he has to go a long way around.
Sample Input 3
8 8 .####### ######## ######## ######## ######## ######## ######## #######.
Sample Output 3
5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N+1 頂点の無向グラフが与えられます。
頂点には頂点 0 、頂点 1 、\ldots 、頂点 N と名前がついています。
i=1,2,\ldots,N について、頂点 0 と頂点 i を結ぶ重み A_i の無向辺があります。
また、i=1,2,\ldots,N について、頂点 i と頂点 i+1 を結ぶ重み B_i の無向辺があります。(ただし、頂点 N+1 は頂点 1 とみなします。)
上に述べた 2N 本の辺の他に辺はありません。
このグラフからいくつかの辺を削除して、グラフを二部グラフにします。
削除する辺の重みの総和の最小値はいくつですか？
制約
- 3 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
答えを出力せよ。
入力例 1
5 31 4 159 2 65 5 5 5 5 10
出力例 1
16
頂点 0,2 を結ぶ辺(重み 4 )、頂点 0,4 を結ぶ辺(重み 2 )、頂点 1,5 を結ぶ辺(重み 10 )を削除するとグラフは二部グラフになります。
入力例 2
4 100 100 100 1000000000 1 2 3 4
出力例 2
10
Score : 500 points
Problem Statement
Given is an undirected graph with N+1 vertices.
The vertices are called Vertex 0, Vertex 1, \ldots, Vertex N.
For each i=1,2,\ldots,N, the graph has an undirected edge with a weight of A_i connecting Vertex 0 and Vertex i.
Additionally, for each i=1,2,\ldots,N, the graph has an undirected edge with a weight of B_i connecting Vertex i and Vertex i+1. (Here, Vertex N+1 stands for Vertex 1.)
The graph has no edge other than these 2N edges above.
Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?
Constraints
- 3 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
Print the answer.
Sample Input 1
5 31 4 159 2 65 5 5 5 5 10
Sample Output 1
16
Deleting the edge connecting Vertices 0,2 (weight: 4), the edge connecting Vertices 0,4 (weight: 2), and the edge connecting Vertices 1,5 (weight: 10) makes the graph bipartite.
Sample Input 2
4 100 100 100 1000000000 1 2 3 4
Sample Output 2
10