AtCoder Daily Training EASY 2024/03/14 20:30start

A - wwwvvvvvv

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

配点 : 100 点

問題文

v と w のみからなる文字列 S が与えられます。

S の中に、下に尖っている部分が何箇所あるかを出力してください（入出力例にある図もご参照ください）。

制約

S は v と w のみからなる文字列
S の長さは 1 以上 100 以下

入力

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

出力

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

入力例 1

vvwvw

出力例 1

vvwvw

上の画像のように、vvwvw という文字列には下に尖った部分が 7 箇所あります。

入力例 2

出力例 2

入力例 3

wwwvvvvvv

出力例 3

Score : 100 points

Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

S is a string consisting of v and w.
The length of S is between 1 and 100, inclusive.

Input

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

Output

Print the answer as an integer.

Sample Input 1

vvwvw

Sample Output 1

vvwvw

The image above shows the seven "bottoms" in the string vvwvw.

Sample Input 2

Sample Output 2

Sample Input 3

wwwvvvvvv

Sample Output 3

B - Edge Checker

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

配点 : 100 点

問題文

下の画像で示す図において、a 番の点と b 番の点が線で直接結ばれているかを答えてください。

制約

1 \leq a \lt b \leq 10
a, b は整数

入力

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

a b

出力

a 番の点と b 番の点が線で直接結ばれている場合は Yes を出力し、結ばれていない場合は No を出力せよ。
ジャッジは英大文字と英小文字を厳密に区別することに注意せよ。

入力例 1

4 5

出力例 1

Yes

問題文で示した図において、4 番の点と 5 番の点は線で直接結ばれています。よって、Yes を出力します。

入力例 2

3 5

出力例 2

No

問題文で示した図において、3 番の点と 5 番の点は線で直接結ばれていません。よって、No を出力します。

入力例 3

1 10

出力例 3

Yes

Score : 100 points

Problem Statement

In the figure shown in the image below, are the points numbered a and b directly connected by a line segment?

Constraints

1 \leq a \lt b \leq 10
a and b are integers.

Input

Input is given from Standard Input in the following format:

a b

Output

If the points numbered a and b are directly connected by a line segment, print Yes; otherwise, print No.
The judge is case-sensitive: be sure to print uppercase and lowercase letters correctly.

Sample Input 1

4 5

Sample Output 1

Yes

In the figure shown in the Problem Statement, the points numbered 4 and 5 are directly connected by a line segment.
Thus, Yes should be printed.

Sample Input 2

3 5

Sample Output 2

No

In the figure shown in the Problem Statement, the points numbered 3 and 5 are not directly connected by a line segment.
Thus, No should be printed.

Sample Input 3

1 10

Sample Output 3

Yes

C - Matrix Transposition

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

配点 : 200 点

問題文

H 行 W 列の行列 A が与えられます。
A の上から i 行目、左から j 列目の要素は A_{i,j} です。

ここで、W 行 H 列の行列 B を、上から i 行目、左から j 列目の要素が A_{j,i} と一致するような行列として定めます。
すなわち、B は A の転置行列です。

B を出力してください。

制約

1\leq H,W \leq 10^5
H \times W \leq 10^5
1 \leq A_{i,j} \leq 10^9
入力は全て整数である

入力

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

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

出力

B を以下の形式で出力せよ。

B_{1,1} B_{1,2} \ldots B_{1,H}
B_{2,1} B_{2,2} \ldots B_{2,H}
\vdots
B_{W,1} B_{W,2} \ldots B_{W,H}

入力例 1

出力例 1

1 4 7 10
2 5 8 11
3 6 9 12

たとえば A_{2,1}=4 なので、転置行列 B の上から 1 行目、左から 2 列目の要素は 4 になります。

入力例 2

2 2
1000000000 1000000000
1000000000 1000000000

出力例 2

1000000000 1000000000
1000000000 1000000000

Score : 200 points

Problem Statement

You are given an H-by-W matrix A.
The element at the i-th row from the top and j-th column from the left of A is A_{i,j}.

Let B be a W-by-H matrix whose element at the i-th row from the top and j-th column from the left equals A_{j, i}.
That is, B is the transpose of A.

Print B.

Constraints

1\leq H,W \leq 10^5
H \times W \leq 10^5
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} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}

Output

Print B in the following format:

B_{1,1} B_{1,2} \ldots B_{1,H}
B_{2,1} B_{2,2} \ldots B_{2,H}
\vdots
B_{W,1} B_{W,2} \ldots B_{W,H}

Sample Input 1

Sample Output 1

1 4 7 10
2 5 8 11
3 6 9 12

For example, we have A_{2,1}=4, so the element at the 1-st row from the top and 2-nd column from the left of the transpose B is 4.

Sample Input 2

2 2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

1000000000 1000000000
1000000000 1000000000

D - MissingNo.

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

配点 : 200 点

問題文

ナオヒロ君は N+1 個の連続する整数を 1 個ずつ持っていましたが、そのうち 1 個をなくしてしまいました。

残っている N 個の整数が順不同で A_1,\ldots,A_N として与えられるので、なくした整数を求めてください。

なお、なくした整数が一意に定まるような入力のみが与えられます。

制約

2 \leq N \leq 100
1 \leq A_i \leq 1000
入力は全て整数である
なくした整数は一意に定まる

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
2 3 5

出力例 1

ナオヒロ君は初め 2,3,4,5 の 4 個の整数を持っており、4 をなくし、2,3,5 が残っていました。

なくした整数である 4 を出力します。

入力例 2

8
3 1 4 5 9 2 6 8

出力例 2

入力例 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

出力例 3

Score : 200 points

Problem Statement

Naohiro had N+1 consecutive integers, one of each, but he lost one of them.

The remaining N integers are given in arbitrary order as A_1,\ldots,A_N. Find the lost integer.

The given input guarantees that the lost integer is uniquely determined.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 1000
All input values are integers.
The lost integer is uniquely determined.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

3
2 3 5

Sample Output 1

Naohiro originally had four integers, 2,3,4,5, then lost 4, and now has 2,3,5.

Print the lost integer, 4.

Sample Input 2

8
3 1 4 5 9 2 6 8

Sample Output 2

Sample Input 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

Sample Output 3

E - Changing Jewels

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

配点 : 300 点

問題文

高橋君はレベル N の赤い宝石を 1 個持っています。(他に宝石は持っていません。)
高橋君は次の操作を好きなだけ行うことができます。

レベル n の赤い宝石 (n は 2 以上) を「レベル n-1 の赤い宝石 1 個と、レベル n の青い宝石 X 個」に変換する。
レベル n の青い宝石 (n は 2 以上) を「レベル n-1 の赤い宝石 1 個と、レベル n-1 の青い宝石 Y 個」に変換する。

高橋君はレベル 1 の青い宝石ができるだけたくさんほしいです。操作によって高橋君はレベル 1 の青い宝石を最大何個入手できますか？

制約

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

入力

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

N X Y

出力

答えを出力せよ。

入力例 1

2 3 4

出力例 1

次のような変換を行うことで、高橋君はレベル 1 の青い宝石を 12 個手に入れることができます。

まず、レベル 2 の赤い宝石 1 個を、レベル 1 の赤い宝石 1 個とレベル 2 の青い宝石 3 個に変換します。
- 操作後の高橋君は、レベル 1 の赤い宝石 1 個とレベル 2 の青い宝石 3 個を持っています。
次に、レベル 2 の青い宝石 1 個を、レベル 1 の赤い宝石 1 個とレベル 1 の青い宝石 4 個に変換します。この変換を 3 回繰り返します。
- 操作後の高橋君は、レベル 1 の赤い宝石 4 個とレベル 1 の青い宝石 12 個を持っています。
これ以上変換を行うことはできません。

12 個より多くレベル 1 の青い宝石を手に入れることはできないので、答えは 12 になります。

入力例 2

1 5 5

出力例 2

高橋君がレベル 1 の青い宝石を 1 個も手に入れられない場合もあります。

入力例 3

10 5 5

出力例 3

3942349900

答えが 32 bit 整数に収まらない場合があることに注意してください。

Score : 300 points

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

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

Input

Input is given from Standard Input in the following format:

N X Y

Output

Print the answer.

Sample Input 1

2 3 4

Sample Output 1

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
- After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
- After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

Note that the answer may not fit into a 32-bit integer type.