AtCoder Daily Training EASY 2025/10/09 18:30start

A - Four Points

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

xy 平面上に長方形があります。この長方形の各辺は x 軸または y 軸に平行であり、面積は 0 ではありません。

この長方形の 4 つの頂点のうち異なる 3 つの頂点の座標 (x_1, y_1), (x_2, y_2), (x_3, y_3) が与えられるので、残る 1 つの頂点の座標を求めてください。

制約

-100 \leq x_i, y_i \leq 100
(x_1, y_1), (x_2, y_2), (x_3, y_3) のすべてを頂点に持つ長方形がただ一つ存在し、その各辺は x 軸または y 軸に平行であり、面積は 0 ではない。
入力はすべて整数

入力

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

x_1 y_1
x_2 y_2
x_3 y_3

出力

答えとなる頂点の座標 (x, y) を下記の形式にしたがい空白区切りで出力せよ。

x y

入力例 1

-1 -1
-1 2
3 2

出力例 1

3 -1

(-1, -1), (-1, 2), (3, 2) を頂点とする長方形の残る 1 つの頂点は (3, -1) です。

入力例 2

-60 -40
-60 -80
-20 -80

出力例 2

-20 -40

Score : 100 points

Problem Statement

There is a rectangle in the xy-plane. Each edge of this rectangle is parallel to the x- or y-axis, and its area is not zero.

Given the coordinates of three of the four vertices of this rectangle, (x_1, y_1), (x_2, y_2), and (x_3, y_3), find the coordinates of the other vertex.

Constraints

-100 \leq x_i, y_i \leq 100
There uniquely exists a rectangle with all of (x_1, y_1), (x_2, y_2), (x_3, y_3) as vertices, edges parallel to the x- or y-axis, and a non-zero area.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

x_1 y_1
x_2 y_2
x_3 y_3

Output

Print the sought coordinates (x, y) separated by a space in the following format:

x y

Sample Input 1

-1 -1
-1 2
3 2

Sample Output 1

3 -1

The other vertex of the rectangle with vertices (-1, -1), (-1, 2), (3, 2) is (3, -1).

Sample Input 2

-60 -40
-60 -80
-20 -80

Sample Output 2

-20 -40

B - Digit Machine

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 桁の数字が表示される画面と、ボタンからなる機械があります。

画面に数字 k が表示されているとき、ボタンを 1 回押すと画面の数字が a_k に変わります。

0 が表示されている状態からボタンを 3 回押すと、画面には何が表示されますか？

制約

0\leq a_i \leq 9
入力は全て整数である

入力

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

a_0 a_1 \dots a_9

出力

答えを出力せよ。

入力例 1

9 0 1 2 3 4 5 6 7 8

出力例 1

画面に表示される数字は、0 \rightarrow 9 \rightarrow 8 \rightarrow 7 と変化します。

入力例 2

4 8 8 8 0 8 8 8 8 8

出力例 2

画面に表示される数字は、0 \rightarrow 4 \rightarrow 0 \rightarrow 4 と変化します。

入力例 3

0 0 0 0 0 0 0 0 0 0

出力例 3

Score : 100 points

Problem Statement

There is a device with a screen that shows a single-digit number, and a button.

When the screen is showing a number k, pressing the button once changes the number on the screen to a_k.

The device currently shows 0. After pressing the button 3 times, what will be shown on the screen?

Constraints

0\leq a_i \leq 9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

a_0 a_1 \dots a_9

Output

Print the answer.

Sample Input 1

9 0 1 2 3 4 5 6 7 8

Sample Output 1

The number on the screen transitions as 0 \rightarrow 9 \rightarrow 8 \rightarrow 7.

Sample Input 2

4 8 8 8 0 8 8 8 8 8

Sample Output 2

The number on the screen transitions as 0 \rightarrow 4 \rightarrow 0 \rightarrow 4.

Sample Input 3

0 0 0 0 0 0 0 0 0 0

Sample Output 3

C - Grid Walk

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

H 行 W 列のグリッドがあります。グリッドの上から i 番目、左から j 番目のマスをマス (i, j) と表記します。

マス (i, j) は C_{i, j} が . のとき空きマスであり、# のとき空きマスではありません。

高橋君は現在マス (S_i, S_j) におり、i = 1, 2, \ldots, |X| の順に以下のルールに従って行動します。

X の i 文字目が L のとき、高橋君が現在いるマスの 1 つ左のマスが存在し、そのマスが空きマスならば 1 つ左のマスに移動する。そうでないならば、現在いるマスに留まる。
X の i 文字目が R のとき、高橋君が現在いるマスの 1 つ右のマスが存在し、そのマスが空きマスならば 1 つ右のマスに移動する。そうでないならば、現在いるマスに留まる。
X の i 文字目が U のとき、高橋君が現在いるマスの 1 つ上のマスが存在し、そのマスが空きマスならば 1 つ上のマスに移動する。そうでないならば、現在いるマスに留まる。
X の i 文字目が D のとき、高橋君が現在いるマスの 1 つ下のマスが存在し、そのマスが空きマスならば 1 つ下のマスに移動する。そうでないならば、現在いるマスに留まる。

一連の行動を終えた後高橋君がどのマスにいるか出力してください。

制約

1 \leq H, W \leq 50
1 \leq S_i \leq H
1 \leq S_j \leq W
H, W, S_i, S_j は整数
C_{i, j} は . または #
C_{S_i, S_j} = .
X は L, R, U, D からなる長さ 1 以上 50 以下の文字列

入力

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

H W
S_i S_j
C_{1, 1}C_{1, 2}\ldotsC_{1, W}
C_{2, 1}C_{2, 2}\ldotsC_{2, W}
\vdots
C_{H, 1}C_{H, 2}\ldotsC_{H, W}
X

出力

高橋君が一連の行動を終えた後にいるマスをマス (x, y) として、x と y をこの順に空白区切りで出力せよ。

入力例 1

2 3
2 1
.#.
...
ULDRU

出力例 1

2 2

高橋君ははじめマス (2, 1) にいます。高橋君の一連の行動は以下のようになります。

X の 1 文字目は U であり、マス (2, 1) の 1 つ上のマスは存在し、そのマスは空きマスであるため 1 つ上のマスであるマス (1, 1) に移動する。
X の 2 文字目は L であり、マス (1, 1) の 1 つ左のマスは存在しないためマス (1, 1) に留まる。
X の 3 文字目は D であり、マス (1, 1) の 1 つ下のマスは存在し、そのマスは空きマスであるため 1 つ下のマスであるマス (2, 1) に移動する。
X の 4 文字目は R であり、マス (2, 1) の 1 つ右のマスは存在し、そのマスは空きマスであるため 1 つ右のマスであるマス (2, 2) に移動する。
X の 5 文字目は U であり、マス (2, 2) の 1 つ上のマスは存在するが、そのマスは空きマスではないためマス (2, 2) に留まる。

したがって一連の行動を終えた後に高橋君がいるマスはマス (2, 2) です。

入力例 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

出力例 2

2 4

入力例 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

出力例 3

1 1

Score : 200 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Cell (i, j) is empty if C_{i, j} is ., and not empty if C_{i, j} is #.

Takahashi is currently at cell (S_i, S_j), and he will act according to the following rules for i = 1, 2, \ldots, |X| in order.

If the i-th character of X is L, and the cell to the left of his current cell exists and is empty, he moves to the cell to the left. Otherwise, he stays in the current cell.
If the i-th character of X is R, and the cell to the right of his current cell exists and is empty, he moves to the cell to the right. Otherwise, he stays in the current cell.
If the i-th character of X is U, and the cell above his current cell exists and is empty, he moves to the cell above. Otherwise, he stays in the current cell.
If the i-th character of X is D, and the cell below his current cell exists and is empty, he moves to the cell below. Otherwise, he stays in the current cell.

Print the cell where he is after completing the series of actions.

Constraints

1 \leq H, W \leq 50
1 \leq S_i \leq H
1 \leq S_j \leq W
H, W, S_i, S_j are integers.
C_{i, j} is . or #.
C_{S_i, S_j} = .
X is a string of length between 1 and 50, inclusive, consisting of L, R, U, D.

Input

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

H W
S_i S_j
C_{1, 1}C_{1, 2}\ldotsC_{1, W}
C_{2, 1}C_{2, 2}\ldotsC_{2, W}
\vdots
C_{H, 1}C_{H, 2}\ldotsC_{H, W}
X

Output

Let (x, y) be the cell where Takahashi is after completing the series of actions. Print x and y, separated by a space.

Sample Input 1

2 3
2 1
.#.
...
ULDRU

Sample Output 1

2 2

Takahashi starts at cell (2, 1). His series of actions are as follows:

The 1st character of X is U, and the cell above (2, 1) exists and is an empty cell, so he moves to the cell above, which is (1, 1).
The 2nd character of X is L, and the cell to the left of (1, 1) does not exist, so he stays at (1, 1).
The 3rd character of X is D, and the cell below (1, 1) exists and is an empty cell, so he moves to the cell below, which is (2, 1).
The 4th character of X is R, and the cell to the right of (2, 1) exists and is an empty cell, so he moves to the cell to the right, which is (2, 2).
The 5th character of X is U, and the cell above (2, 2) exists but is not an empty cell, so he stays at (2, 2).

Therefore, after completing the series of actions, he is at cell (2, 2).

Sample Input 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

Sample Output 2

2 4

Sample Input 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

Sample Output 3

1 1

D - Extended ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

拡張 A 文字列、拡張 B 文字列、拡張 C 文字列および拡張 ABC 文字列を以下のように定義します。

文字列 S が拡張 A 文字列であるとは、S のすべての文字が A であることをいいます。
文字列 S が拡張 B 文字列であるとは、S のすべての文字が B であることをいいます。
文字列 S が拡張 C 文字列であるとは、S のすべての文字が C であることをいいます。
文字列 S が拡張 ABC 文字列であるとは、ある拡張 A 文字列 S _ A 、拡張 B 文字列 S _ B 、拡張 C 文字列 S _ C が存在して、S _ A,S _ B,S _ C をこの順に連結した文字列が S と等しいことをいいます。

例えば、ABC や A 、AAABBBCCCCCCC などは拡張 ABC 文字列ですが、ABBAAAC 、BBBCCCCCCCAAA などは拡張 ABC 文字列ではありません。空文字列は拡張 A 文字列でも拡張 B 文字列でも拡張 C 文字列でもあることに注意してください。

A, B, C からなる文字列 S が与えられます。 S が拡張 ABC 文字列ならば Yes を、そうでなければ No を出力してください。

制約

S は A, B, C からなる文字列
1\leq|S|\leq 100\ (|S| は文字列 S の長さ)

入力

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

出力

S が拡張 ABC 文字列ならば Yes を、そうでなければ No を出力せよ。

入力例 1

AAABBBCCCCCCC

出力例 1

Yes

AAABBBCCCCCCC は長さ 3 の拡張 A 文字列 AAA 、長さ 3 の拡張 B 文字列 BBB 、長さ 7 の拡張 C 文字列 CCCCCCC をこの順に連結した文字列なので、拡張 ABC 文字列です。

よって、Yes を出力してください。

入力例 2

ACABABCBC

出力例 2

No

どのような拡張 A 文字列 S _ A, 拡張 B 文字列 S _ B, 拡張 C 文字列 S _ C についても、S _ A,S _ B,S _ C をこの順に連結した文字列が ACABABCBC と等しくなることはありません。

よって、No を出力してください。

入力例 3

出力例 3

Yes

入力例 4

ABBBBBBBBBBBBBCCCCCC

出力例 4

Yes

Score: 200 points

Problem Statement

We define Extended A strings, Extended B strings, Extended C strings, and Extended ABC strings as follows:

A string S is an Extended A string if all characters in S are A.
A string S is an Extended B string if all characters in S are B.
A string S is an Extended C string if all characters in S are C.
A string S is an Extended ABC string if there is an Extended A string S_A, an Extended B string S_B, and an Extended C string S_C such that the string obtained by concatenating S_A, S_B, S_C in this order equals S.

For example, ABC, A, and AAABBBCCCCCCC are Extended ABC strings, but ABBAAAC and BBBCCCCCCCAAA are not. Note that the empty string is an Extended A string, an Extended B string, and an Extended C string.

You are given a string S consisting of A, B, and C. If S is an Extended ABC string, print Yes; otherwise, print No.

Constraints

S is a string consisting of A, B, and C.
1\leq|S|\leq 100 (|S| is the length of the string S.)

Input

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

Output

If S is an Extended ABC string, print Yes; otherwise, print No.

Sample Input 1

AAABBBCCCCCCC

Sample Output 1

Yes

AAABBBCCCCCCC is an Extended ABC string because it is a concatenation of an Extended A string of length 3, AAA, an Extended B string of length 3, BBB, and an Extended C string of length 7, CCCCCCC, in this order.

Thus, print Yes.

Sample Input 2

ACABABCBC

Sample Output 2

No

There is no triple of Extended A string S_A, Extended B string S_B, and Extended C string S_C such that the string obtained by concatenating S_A, S_B, and S_C in this order equals ACABABCBC.

Therefore, print No.

Sample Input 3

Sample Output 3

Yes

Sample Input 4

ABBBBBBBBBBBBBCCCCCC

Sample Output 4

Yes

E - Invisible Hand

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

りんご市場に N 人の売り手と M 人の買い手がいます。

i 番目の売り手は、A_i 円以上でならりんごを売ってもよいと考えています。

i 番目の買い手は、B_i 円以下でならりんごを買ってもよいと考えています。

次の条件を満たすような最小の整数 X を求めてください。

条件：りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。

制約

1 \leq N,M \leq 2\times 10^5
1\leq A_i,B_i \leq 10^9
入力は全て整数である

入力

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

N M
A_1 \ldots A_N
B_1 \ldots B_M

出力

答えを出力せよ。

入力例 1

3 4
110 90 120
100 80 120 10000

出力例 1

りんごを 110 円で売ってもよいと考える売り手は 1,2 番目の 2 人であり、りんごを 110 円で買ってもよいと考える買い手は 3,4 番目の 2 人であるため、110 は条件を満たします。

110 未満の整数が条件を満たすことはないため、これが答えです。

入力例 2

5 2
100000 100000 100000 100000 100000
100 200

出力例 2

入力例 3

3 2
100 100 100
80 120

出力例 3

Score : 300 points

Problem Statement

There are N sellers and M buyers in an apple market.

The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).

The i-th buyer may buy an apple for B_i yen or less.

Find the minimum integer X that satisfies the following condition.

Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.

Constraints

1 \leq N,M \leq 2\times 10^5
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 M
A_1 \ldots A_N
B_1 \ldots B_M

Output

Print the answer.

Sample Input 1

3 4
110 90 120
100 80 120 10000

Sample Output 1

Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.

Since an integer less than 110 does not satisfy the condition, this is the answer.

Sample Input 2

5 2
100000 100000 100000 100000 100000
100 200

Sample Output 2

Sample Input 3

3 2
100 100 100
80 120