AtCoder Daily Training EASY 2024/02/21 16:00start

A - Apple

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

果物屋さんでりんごが売られています。
あなたは次の操作を好きな順で好きなだけ繰り返すことができます。

X 円を払ってりんごを 1 個手に入れる。
Y 円を払ってりんごを 3 個手に入れる。

りんごをちょうど N 個手に入れるには最低何円必要ですか？

制約

1 \leq X \leq Y \leq 100
1 \leq N \leq 100
入力される値はすべて整数

入力

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

X Y N

出力

答えを整数として出力せよ。

入力例 1

10 25 10

出力例 1

25 円払って 3 個のりんごを手に入れる操作を 3 回繰り返した後、10 円払って 1 個のりんごを手に入れると丁度 10 個のりんごを手に入れられます。このときあなたは 85 円を消費します。
これより少ない金額でちょうど 10 個のりんごを手に入れることはできないので、答えは 85 円になります。

入力例 2

10 40 10

出力例 2

10 円払って 1 個のりんごを手に入れる操作を 10 回繰り返すのが最適です。

入力例 3

100 100 2

出力例 3

100 円を払って 1 個のりんごを手に入れる操作を 2 回繰り返す以外に ちょうど 2 個のりんごを手に入れる方法はありません。

入力例 4

100 100 100

出力例 4

Score : 100 points

Problem Statement

A fruit store sells apples.
You may perform the following operations as many times as you want in any order:

Buy one apple for X yen (the currency in Japan).
Buy three apples for Y yen.

How much yen do you need to pay to obtain exactly N apples?

Constraints

1 \leq X \leq Y \leq 100
1 \leq N \leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y N

Output

Print the answer as an integer.

Sample Input 1

10 25 10

Sample Output 1

Buy three apples for 25 yen three times and one apple for 10 yen, and you will obtain exactly 10 apples for a total of 85 yen.
You cannot obtain exactly 10 apples for a lower cost, so the answer is 85 yen.

Sample Input 2

10 40 10

Sample Output 2

It is optimal to buy an apple for 10 yen 10 times.

Sample Input 3

100 100 2

Sample Output 3

The only way to obtain exactly 2 apples is to buy an apple for 100 yen twice.

Sample Input 4

100 100 100

Sample Output 4

B - Similar String

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

二つの文字 x と y は以下の 3 つの条件のうちどれか 1 つを満たすとき、似た文字と呼ばれます。

x と y は同じ文字
x と y の片方が 1 で、もう片方が l
x と y の片方が 0 で、もう片方が o

また、長さ N の文字列 S と T は以下の条件を満たすとき、似た文字列と呼ばれます。

任意の i\ (1\leq i\leq N) について、 S の i 番目の文字と T の i 番目の文字は似た文字

英小文字及び数字からなる長さ N の文字列 S,T が与えられます。 S と T が似た文字列か判定してください。

制約

N は 1 以上 100 以下の整数
S,T は英小文字及び数字からなる長さ N の文字列

入力

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

N
S
T

出力

S と T が似た文字列の場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

3
l0w
1ow

出力例 1

Yes

S の 1 文字目は lで、T の 1 文字目は 1です。これらは似た文字です。

S の 2 文字目は 0で、T の 2 文字目は oです。これらは似た文字です。

S の 3 文字目は wで、T の 3 文字目は wです。これらは似た文字です。

よって S と T は似た文字列です。

入力例 2

3
abc
arc

出力例 2

No

S の 2 文字目は bで、T の 2 文字目は rです。これらは似た文字ではありません。

よって S と T は似た文字列ではありません。

入力例 3

4
nok0
n0ko

出力例 3

Yes

Score : 100 points

Problem Statement

Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:

x and y are the same character.
One of x and y is 1 and the other is l.
One of x and y is 0 and the other is o.

Two strings S and T, each of length N, are called similar strings if and only if:

for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.

Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.

Constraints

N is an integer between 1 and 100.
Each of S and T is a string of length N consisting of lowercase English letters and digits.

Input

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

N
S
T

Output

Print Yes if S and T are similar strings, and No otherwise.

Sample Input 1

3
l0w
1ow

Sample Output 1

Yes

The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.

The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.

The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.

Thus, S and T are similar strings.

Sample Input 2

3
abc
arc

Sample Output 2

No

The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.

Thus, S and T are not similar strings.

Sample Input 3

4
nok0
n0ko

Sample Output 3

Yes

C - Mongeness

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

縦 H 行、横 W 列のマス目があり、各マスには 1 つの整数が書かれています。上から i 行目、左から j 列目のマスに書かれている整数は A_{i, j} です。

マス目が下記の条件を満たすかどうかを判定してください。

1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たすすべての整数の組 (i_1, i_2, j_1, j_2) について、A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立つ。

制約

2 \leq H, W \leq 50
1 \leq A_{i, j} \leq 10^9
入力はすべて整数

入力

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

H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

出力

マス目が問題文中の条件を満たす場合は Yes と出力し、条件を満たさない場合は No と出力せよ。

入力例 1

出力例 1

Yes

1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たす整数の組 (i_1, i_2, j_1, j_2) は 9 個存在し、それらすべてについて A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立ちます。例えば、

(i_1, i_2, j_1, j_2) = (1, 2, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 2, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 2, 2, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 3, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 3, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}

が成り立ちます。残りの (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3) についても同様に確認できます。
よって、Yes を出力します。

入力例 2

2 4
4 3 2 1
5 6 7 8

出力例 2

No

問題文中の条件を満たさないので、No を出力します。
例えば、(i_1, i_2, j_1, j_2) = (1, 2, 1, 4) について、A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} です。

Score : 200 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.

Determine whether the grid satisfies the condition below.

A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.

Constraints

2 \leq H, W \leq 50
1 \leq A_{i, j} \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

Output

If the grid satisfies the condition in the Problem Statement, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.

For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.

We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.

Sample Input 2

2 4
4 3 2 1
5 6 7 8

Sample Output 2

No

We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).

D - Tetrahedral Number

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 150 点

問題文

整数 N が与えられます。

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを辞書順で小さい方から順に全て出力してください。

非負整数の組の辞書順とは？

非負整数の組 (x,y,z) が (x',y',z') より辞書順で小さいとは、下記のいずれかが成り立つことを言います。

x < x' である
x=x' かつ y< y' である
x=x' かつ y=y' かつ z< z' である

制約

0 \leq N \leq 21
N は整数である

入力

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

出力

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを、1 行に 1 組ずつ x,y,z を空白区切りで、辞書順で小さい方から順に全て出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

Score : 150 points

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

What is lexicographical order for non-negative integer triples?

A triple of non-negative integers (x,y,z) is said to be lexicographically smaller than (x',y',z') if and only if one of the following holds:

x < x';
x=x' and y< y';
x=x' and y=y' and z< z'.

Constraints

0 \leq N \leq 21
N is an integer.

Input

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

Output

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order, with x,y,z separated by spaces, one triple per line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

E - Manga

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は全 10^9 巻の漫画『すぬけ君』を読むことにしました。
初め、高橋君は『すぬけ君』の単行本を N 冊持っています。i 番目の単行本は a_i 巻です。

高橋君は『すぬけ君』を読み始める前に限り次の操作を 0 回以上何度でも繰り返せます。

現在持っている単行本が 1 冊以下の場合、何もしない。そうでない場合、現在持っている単行本から 2 冊を選んで売り、代わりに好きな巻を選んで 1 冊買う

その後、高橋君は『すぬけ君』を 1 巻、2 巻、3 巻、\ldots と順番に読みます。ただし、次に読むべき巻を持っていない状態になった場合、(他の巻を持っているかどうかに関わらず)その時点で『すぬけ君』を読むのをやめます。

高橋君が『すぬけ君』を最大で何巻まで読めるかを求めてください。ただし、1 巻を読めない場合の答えは 0 とします。

制約

1 \leq N \leq 3 \times 10^5
1 \leq a_i \leq 10^9
入力はすべて整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。

入力例 1

6
1 2 4 6 7 271

出力例 1

『すぬけ君』を読み始める前に「7 巻と 271 巻を選んで売り、代わりに 3 巻を選んで 1 冊買う」という内容で操作をすると、高橋君は 1 巻、2 巻、3 巻、4 巻、6 巻を 1 冊ずつ持っている状態になります。
この状態から『すぬけ君』を読み始めると、高橋君は 1 巻、2 巻、3 巻、4 巻を読み、続いて 5 巻を読もうとしますが持っていないためこの時点で『すぬけ君』を読むのをやめます。
操作の方法を変えても 5 巻を読むことは出来ないため、4 が答えです。

入力例 2

10
1 1 1 1 1 1 1 1 1 1

出力例 2

高橋君は同じ巻を 2 冊以上持っているかもしれません。
この入力に対しては以下のように 4 回操作をしてから『すぬけ君』を読み始めることで 5 巻まで読むことが出来、これが最大です。

1 巻を 2 冊選んで売り、代わりに 2 巻を選んで 1 冊買う
1 巻を 2 冊選んで売り、代わりに 3 巻を選んで 1 冊買う
1 巻を 2 冊選んで売り、代わりに 4 巻を選んで 1 冊買う
1 巻を 2 冊選んで売り、代わりに 5 巻を選んで 1 冊買う

入力例 3

1
5

出力例 3

高橋君は 1 巻を読めません。

Score : 300 points

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

1 \leq N \leq 3 \times 10^5
1 \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
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

Sell two books of Volume 1 and buy a book of Volume 2 instead.
Sell two books of Volume 1 and buy a book of Volume 3 instead.
Sell two books of Volume 1 and buy a book of Volume 4 instead.
Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

Takahashi cannot read Volume 1.