AtCoder Daily Training EASY 2025/01/15 20:00start

A - Lacked Number

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

配点 : 100 点

問題文

数字のみからなる、長さがちょうど 9 の文字列 S が与えられます。
S には 0 から 9 までのうち、ちょうど 1 つの数字を除いた 9 種類の数字が一度ずつ登場します。

S に登場しない唯一の数字を出力してください。

制約

S は数字のみからなる長さ 9 の文字列である。
S の文字はすべて相異なる。

入力

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

出力

S に登場しない唯一の数字を出力せよ。

入力例 1

023456789

出力例 1

文字列 023456789 には 1 のみが登場していません。よって、1 を出力します。

入力例 2

459230781

出力例 2

文字列 459230781 には 6 のみが登場していません。よって、6 を出力します。

文字列に数字が現れる順番は昇順とは限らないので注意してください。

Score : 100 points

Problem Statement

You are given a string S of length exactly 9 consisting of digits. One but all digits from 0 to 9 appear exactly once in S.

Print the only digit missing in S.

Constraints

S is a string of length 9 consisting of digits.
All characters in S are distinct.

Input

Input is given from Standard Input in the following format:

Output

Print the only digit missing in S.

Sample Input 1

023456789

Sample Output 1

The string 023456789 only lacks 1. Thus, 1 should be printed.

Sample Input 2

459230781

Sample Output 2

The string 459230781 only lacks 6. Thus, 6 should be printed.

Note that the digits in the string may not appear in increasing order.

B - Buildings

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

配点 : 100 点

問題文

N 個のビルが横一列に並んでいて、左から i 番目のビルの高さは H_i です。

左から 1 番目のビルより高いビルが存在するか判定し、存在する場合その内最も左のビルは左から何番目か求めてください。

制約

1\leq N\leq 100
1\leq H_i \leq 100
入力される数値は全て整数

入力

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

N 
H_1 H_2 \ldots H_N

出力

左から 1 番目のビルより高いビルが存在しない場合 -1 を出力せよ。

存在する場合、その内最も左のビルは左から何番目か出力せよ。

入力例 1

4
3 2 5 2

出力例 1

左から 1 番目のビルより高いビルは、左から 3 番目のビルです。

入力例 2

3
4 3 2

出力例 2

-1

左から 1 番目のビルより高いビルは存在しません。

入力例 3

7
10 5 10 2 10 13 15

出力例 3

左から 1 番目のビルより高いビルは、左から 6 番目のビルと左から 7 番目のビルです。その内最も左のビルは左から 6 番目のビルです。

Score: 100 points

Problem Statement

There are N buildings aligned in a row. The i-th building from the left has a height of H_i.

Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.

Constraints

1 \leq N \leq 100
1 \leq H_i \leq 100
All input values are integers.

Input

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

N
H_1 H_2 \ldots H_N

Output

If no building is taller than the first one from the left, print -1.

If such a building exists, print the position (index) of the leftmost such building from the left.

Sample Input 1

4
3 2 5 2

Sample Output 1

The building taller than the first one from the left is the third one from the left.

Sample Input 2

3
4 3 2

Sample Output 2

-1

No building is taller than the first one from the left.

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.

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 - Postal Card

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

配点 : 200 点

問題文

数字のみからなる長さ 6 の文字列が N 個与えられます。i \, (i = 1, 2, \dots, N) 番目のものを S_i と表します。

さらに、数字のみからなる長さ 3 の文字列が M 個与えられます。j \, (j = 1, 2, \dots, M) 番目のものを T_j と表します。

S_1, S_2, \dots, S_N のうち、末尾 3 文字が T_1, T_2, \dots, T_M のいずれかに一致するものの個数を求めてください。

制約

1 \leq N, M \leq 1000
N, M は整数
全ての i = 1, 2, \dots, N に対し、S_i は数字のみからなる長さ 6 の文字列
全ての j = 1, 2, \dots, M に対し、T_j は数字のみからなる長さ 3 の文字列

入力

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

N M
S_1
S_2
\vdots
S_N
T_1
T_2
\vdots
T_M

出力

答えを出力せよ。

入力例 1

出力例 1

S_1 の末尾 3 文字は 857 であり、これは T_3 に一致します。
S_2 の末尾 3 文字は 159 であり、これは T_1 に一致します。
S_3 の末尾 3 文字は 028 であり、これは T_1, T_2, T_3 のいずれにも一致しません。

以上から、答えは 2 です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 200 points

Problem Statement

You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.

Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.

Constraints

1 \leq N, M \leq 1000
N and M are integers.
S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.

Input

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

N M
S_1
S_2
\vdots
S_N
T_1
T_2
\vdots
T_M

Output

Print the answer.

Sample Input 1

Sample Output 1

The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.

Thus, the answer is 2.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

E - Doukasen

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

配点 : 300 点

問題文

N 本の導火線を一直線に接着したものがあります。左から i 本目の導火線は長さが A_i cm で、 1 秒あたり B_i cm の一定の速さで燃えます。

この導火線の左端と右端から同時に火をつけるとき、 2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か求めてください。

制約

1 \leq N \leq 10^5
1 \leq A_i,B_i \leq 1000
入力は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か（単位を除いて）出力せよ。

想定解答との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。

入力例 1

出力例 1

3.000000000000000

着火前の導火線の左端から 3 cm の地点で 2 つの火がぶつかります。

入力例 2

出力例 2

3.833333333333333

入力例 3

出力例 3

8.916666666666668

Score : 300 points

Problem Statement

We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.

Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.

Constraints

1 \leq N \leq 10^5
1 \leq A_i,B_i \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the distance between the position where the two flames will meet and the left end of the object, in centimeters (print just the number).

Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-5}.

Sample Input 1

Sample Output 1

3.000000000000000

The two flames will meet at 3 centimeters from the left end of the object.

Sample Input 2

Sample Output 2

3.833333333333333

Sample Input 3

Sample Output 3

8.916666666666668