AtCoder Daily Training EASY 2025/07/02 20:00start

A - Approximation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

正整数 A と正の奇数 B が与えられます。

実数 \dfrac AB との差が最小となる整数を出力してください。

ただし、制約のもとでそのような整数がただ一つ存在することが証明できます。

制約

1\leq A\leq407
1\leq B\leq407
B は奇数
入力はすべて整数

入力

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

A B

出力

\dfrac AB との差が最小となる整数を出力せよ。

入力例 1

4 7

出力例 1

\dfrac AB=\dfrac47=0.5714\ldots です。 \dfrac AB と 1 との差は \dfrac37=0.4285\ldots で、これより差が小さい整数はありません。

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

入力例 2

407 29

出力例 2

\dfrac AB=\dfrac{407}{29}=14.0344\ldots です。 \dfrac AB と 14 との差は \dfrac1{29}=0.0344\ldots で、これより差が小さい整数はありません。

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

入力例 3

22 11

出力例 3

\dfrac AB が整数である場合もあります。

Score : 150 points

Problem Statement

You are given a positive integer A and a positive odd integer B.

Output the integer whose difference from the real number \dfrac AB is the smallest.

It can be proved that, under the constraints, such an integer is unique.

Constraints

1 \le A \le 407
1 \le B \le 407
B is odd.
All input values are integers.

Input

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

A B

Output

Output the integer that minimizes the difference from \dfrac AB.

Sample Input 1

4 7

Sample Output 1

We have \dfrac AB = \dfrac47 = 0.5714\ldots. The difference between \dfrac AB and 1 is \dfrac37 = 0.4285\ldots, and no integer has a smaller difference.

Thus, print 1.

Sample Input 2

407 29

Sample Output 2

We have \dfrac AB = \dfrac{407}{29} = 14.0344\ldots. The difference between \dfrac AB and 14 is \dfrac1{29} = 0.0344\ldots, and no integer has a smaller difference.

Thus, print 14.

Sample Input 3

22 11

Sample Output 3

\dfrac AB may itself be an integer.

B - Full House

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

5 枚のカードがあり、それぞれのカードには整数 A,B,C,D,E が書かれています。

この 5 枚組は以下の条件を満たすとき、またそのときに限って、フルハウスであると呼ばれます。

同じ数が書かれたカード 3 枚と、別の同じ数が書かれたカード 2 枚からなる。

5 枚組がフルハウスであるか判定してください。

制約

1 \leq A,B,C,D,E\leq 13
A,B,C,D,E 全てが同じ値ではない
入力は全て整数

入力

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

A B C D E

出力

フルハウスである場合 Yes を、そうでないとき No を出力せよ。

入力例 1

1 2 1 2 1

出力例 1

Yes

1 が書かれたカード 3 枚と、2 が書かれたカード 2 枚からなるため、これはフルハウスです。

入力例 2

12 12 11 1 2

出力例 2

No

フルハウスの条件を満たしません。

Score : 100 points

Problem Statement

We have five cards with integers A, B, C, D, and E written on them, one on each card.

This set of five cards is called a Full house if and only if the following condition is satisfied:

the set has three cards with a same number written on them, and two cards with another same number written on them.

Determine whether the set is a Full house.

Constraints

1 \leq A,B,C,D,E\leq 13
Not all of A, B, C, D, and E are the same.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E

Output

If the set is a Full house, print Yes; otherwise, print No.

Sample Input 1

1 2 1 2 1

Sample Output 1

Yes

The set has three cards with 1 written on them and two cards with 2 written on them, so it is a Full house.

Sample Input 2

12 12 11 1 2

Sample Output 2

No

The condition is not satisfied.

C - Who is Missing?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ M の整数列 A=(A_1,A_2,\dots,A_M) が与えられます。
A の各要素は 1 以上 N 以下で、全ての要素は相異なります。

A の要素として含まれない 1 以上 N 以下の整数を、昇順に全て列挙してください。

制約

入力は全て整数
1 \le M \le N \le 1000
1 \le A_i \le N
A の要素は相異なる

入力

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

N M
A_1 A_2 \dots A_M

出力

A の要素として含まれない 1 以上 N 以下の整数を昇順に全て挙げた列が (X_1,X_2,\dots,X_C) であるとき、以下の形式で出力せよ。

C
X_1 X_2 \dots X_C

入力例 1

10 3
3 9 2

出力例 1

7
1 4 5 6 7 8 10

A=(3,9,2) です。
A の要素として含まれない 1 以上 10 以下の整数を昇順に全て挙げると、 1,4,5,6,7,8,10 となります。

入力例 2

6 6
1 3 5 2 4 6

出力例 2

A の要素として含まれない 1 以上 6 以下の整数がひとつもありません。
この場合、 1 行目に 0 と出力し、 2 行目は空行としてください。

入力例 3

9 1
9

出力例 3

8
1 2 3 4 5 6 7 8

Score : 200 points

Problem Statement

You are given a sequence of M integers A = (A_1, A_2, \dots, A_M).
Each element of A is an integer between 1 and N, inclusive, and all elements are distinct.

List all integers between 1 and N that do not appear in A in ascending order.

Constraints

All input values are integers.
1 \le M \le N \le 1000
1 \le A_i \le N
The elements of A are distinct.

Input

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

N M
A_1 A_2 \dots A_M

Output

Let (X_1, X_2, \dots, X_C) be the sequence of all integers between 1 and N, inclusive, that do not appear in A, listed in ascending order. The output should be in the following format:

C
X_1 X_2 \dots X_C

Sample Input 1

10 3
3 9 2

Sample Output 1

7
1 4 5 6 7 8 10

Here, A=(3,9,2).
The integers between 1 and 10 that do not appear in A, listed in ascending order, are 1,4,5,6,7,8,10.

Sample Input 2

6 6
1 3 5 2 4 6

Sample Output 2

No integer between 1 and 6 is missing from A.
In this case, print 0 on the first line and leave the second line empty.

Sample Input 3

9 1
9

Sample Output 3

8
1 2 3 4 5 6 7 8

D - Integer Division

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

-10^{18} 以上 10^{18} 以下の整数 X が与えられるので、\left\lfloor \dfrac{X}{10} \right\rfloor を出力してください。

注記

実数 x に対して、「x 以下の整数の中で最大の整数」を \left\lfloor x \right\rfloor と表します。たとえば \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, \left\lfloor 5 \right\rfloor = 5 のようになります。(詳しくは入出力例にある説明を参考にしてください。)

制約

-10^{18} \leq X \leq 10^{18}
入力はすべて整数である。

入力

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

出力

\left\lfloor \frac{X}{10} \right\rfloor を出力せよ。整数として出力する必要があることに注意せよ。

入力例 1

出力例 1

\frac{47}{10} = 4.7 以下の整数は、すべての負の整数および 0, 1, 2, 3, 4 です。この中で一番大きい整数は 4 なので、\left\lfloor \frac{47}{10} \right\rfloor = 4 となります。

入力例 2

-24

出力例 2

-3

\frac{-24}{10} = -2.4 以下の整数の中で一番大きい整数は -3 なので、 \left\lfloor \frac{-24}{10} \right\rfloor = -3 となります。
-2 は -2.4 よりも大きいので、条件を満たさないことに注意してください。

入力例 3

出力例 3

\frac{50}{10} = 5 以下の整数の中で一番大きい整数は 5 自身です。よって \left\lfloor \frac{50}{10} \right\rfloor = 5 となります。

入力例 4

-30

出力例 4

-3

上の例と同様に \left\lfloor \frac{-30}{10} \right\rfloor = -3 となります。

入力例 5

987654321987654321

出力例 5

98765432198765432

答えは 98765432198765432 となります。すべての桁が正しく合っているか確認しましょう。

なお、もしも自分で書いたプログラムが想定通りの挙動をしない場合は、使用しているプログラミング言語の仕様を調べてみることを推奨します。
また、自分の書いたコードがどのように動作するかを確認したい場合は問題文上部の「コードテスト」をご利用ください。

Score : 200 points

Problem Statement

Given an integer X between -10^{18} and 10^{18} (inclusive), print \left\lfloor \dfrac{X}{10} \right\rfloor.

Notes

For a real number x, \left\lfloor x \right\rfloor denotes "the maximum integer not exceeding x". For example, we have \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, and \left\lfloor 5 \right\rfloor = 5. (For more details, please refer to the description in the Sample Input and Output.)

Constraints

-10^{18} \leq X \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

Print \left\lfloor \frac{X}{10} \right\rfloor. Note that it should be output as an integer.

Sample Input 1

Sample Output 1

The integers that do not exceed \frac{47}{10} = 4.7 are all the negative integers, 0, 1, 2, 3, and 4. The maximum integer among them is 4, so we have \left\lfloor \frac{47}{10} \right\rfloor = 4.

Sample Input 2

-24

Sample Output 2

-3

Since the maximum integer not exceeding \frac{-24}{10} = -2.4 is -3, we have \left\lfloor \frac{-24}{10} \right\rfloor = -3.
Note that -2 does not satisfy the condition, as -2 exceeds -2.4.

Sample Input 3

Sample Output 3

The maximum integer that does not exceed \frac{50}{10} = 5 is 5 itself. Thus, we have \left\lfloor \frac{50}{10} \right\rfloor = 5.

Sample Input 4

-30

Sample Output 4

-3

Just like the previous example, \left\lfloor \frac{-30}{10} \right\rfloor = -3.

Sample Input 5

987654321987654321

Sample Output 5

98765432198765432

The answer is 98765432198765432. Make sure that all the digits match.

If your program does not behave as intended, we recommend you checking the specification of the programming language you use.
If you want to check how your code works, you may use "Custom Test" above the Problem Statement.

E - LRUD Instructions 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

二次元平面上に高橋君がいます。高橋君は原点から移動を N 回行いました。

N 回の移動は長さ N の文字列で表され、意味は次の通りです。

i 回目の高橋君の移動後の座標は、移動前の座標を (x,y) として、
- S の i 文字目が R であるとき (x+1,y)
- S の i 文字目が L であるとき (x-1,y)
- S の i 文字目が U であるとき (x,y+1)
- S の i 文字目が D であるとき (x,y-1)

N 回の移動 (始点と終点を含む) で、高橋君が同じ座標にいたことがあるかどうかを判定してください。

制約

1 \leq N \leq 2\times 10^5
N は整数
S は R, L, U, D のみからなる長さ N の文字列

入力

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

N
S

出力

N 回の移動 (始点と終点を含む) で、高橋君が同じ座標にいたことがあれば Yes、なければ No と出力せよ。

入力例 1

5
RLURU

出力例 1

Yes

高橋君のいる座標は (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2) と変化します。

入力例 2

20
URDDLLUUURRRDDDDLLLL

出力例 2

No

Score : 300 points

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

Takahashi's coordinates after the i-th move are:
- (x+1,y) if the i-th character of S is R;
- (x-1,y) if the i-th character of S is L;
- (x,y+1) if the i-th character of S is U; and
- (x,y-1) if the i-th character of S is D,
where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

1 \leq N \leq 2\times 10^5
N is an integer.
S is a string of length N consisting of R, L, U, and D.

Input

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

N
S

Output

Print Yes if Takahashi visited the same coordinates multiple times in the course of the N moves; print No otherwise.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No