AtCoder Daily Training EASY 2025/08/06 16:00start

A - T-shirt

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

配点 : 100 点

問題文

あるプログラミングコンテストでは、以下のルールに従って参加者に T シャツをプレゼントします。

上位 A 位までの参加者は、必ず T シャツが貰える。
加えて、上位 A+1 位から B 位までの参加者のうち C 人が一様ランダムに選ばれ、選ばれた参加者は T シャツを貰える。

コンテストには 1000 人が参加し、全ての参加者が相異なる順位を取りました。
このコンテストの参加者であるいろはちゃんは、X 位を取りました。
このとき、いろはちゃんが T シャツを貰える確率を求めてください。

制約

入力はすべて整数
1 \le A < B \le 1000
1 \le C \le B-A
1 \le X \le 1000

入力

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

A B C X

出力

答えを出力せよ。なお、想定解との絶対誤差または相対誤差が 10^{−6} 以下であれば、正解として扱われる。

入力例 1

30 500 20 103

出力例 1

0.042553191489

いろはちゃんは 103 位を取りました。
31 位から 500 位までの 470 人の参加者の中から 20 人が一様ランダムに選ばれ、ここで選ばれるといろはちゃんは T シャツを貰えます。この確率は \frac{20}{470}=0.04255319\dots です。

入力例 2

50 500 100 1

出力例 2

1.000000000000

いろはちゃんは 1 位を取りました。この入力において、いろはちゃんは確実に T シャツを貰えます。

入力例 3

1 2 1 1000

出力例 3

0.000000000000

いろはちゃんは 1000 位を取りました。この入力において、いろはちゃんが T シャツを貰えることはありません。

Score : 100 points

Problem Statement

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

All participants who ranked A-th or higher get a T-shirt.
Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.

Constraints

All values in input are integers.
1 \le A < B \le 1000
1 \le C \le B-A
1 \le X \le 1000

Input

Input is given from Standard Input in the following format:

A B C X

Output

Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most 10^{−6}.

Sample Input 1

30 500 20 103

Sample Output 1

0.042553191489

Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.

Sample Input 2

50 500 100 1

Sample Output 2

1.000000000000

Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.

Sample Input 3

1 2 1 1000

Sample Output 3

0.000000000000

Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.

B - Find Multiple

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

配点 : 100 点

問題文

A 以上 B 以下であるような C の倍数を、1 つ出力してください。

条件を満たす数が存在しない場合は -1 を出力してください。

制約

1 \leq A \leq B \leq 1000
1 \leq C \leq 1000
入力は全て整数

入力

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

A B C

出力

答えを出力せよ。
条件を満たす数が存在しない場合は -1 を出力せよ。

入力例 1

123 456 100

出力例 1

300 や 400 も正解です。

入力例 2

630 940 314

出力例 2

-1

Score : 100 points

Problem Statement

Print a number between A and B (inclusive) that is a multiple of C.

If there is no such number, print -1.

Constraints

1 \leq A \leq B \leq 1000
1 \leq C \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C

Output

Print the answer.
If there is no number with the desired property, print -1.

Sample Input 1

123 456 100

Sample Output 1

300 or 400 would also be accepted.

Sample Input 2

630 940 314

Sample Output 2

-1

C - Caesar Cipher

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

配点 : 200 点

問題文

高橋君は英小文字からなる文字列 S を持っています。

高橋君は文字列 S に対して、下記の操作をちょうど 1 回行います。

まず、非負整数 K を選ぶ。
その後、S の各文字を K 個後ろの英小文字に変更する。

ただし、

a の 1 個後ろの英小文字は b であり、
b の 1 個後ろの英小文字は c であり、
c の 1 個後ろの英小文字は d であり、
\cdots
y の 1 個後ろの英小文字は z であり、
z の 1 個後ろの英小文字は a です。

例えば、b の 4 個後ろの英小文字は f であり、y の 3 個後ろの英小文字は b です。

文字列 T が与えられます。高橋君が上記の操作によって S を T に一致させることができるかを判定してください。

制約

S と T はそれぞれ英小文字からなる長さ 1 以上 10^5 以下の文字列
S の長さと T の長さは等しい

入力

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

S
T

出力

高橋君が S を T に一致させることができる場合は Yes と出力し、できない場合は No と出力せよ。

入力例 1

abc
ijk

出力例 1

Yes

高橋君が K=8 を選ぶと、

a は 8 個後ろの i に
b は 8 個後ろの j に
c は 8 個後ろの k に

それぞれ変更され、S と T が一致します。
高橋君が S を T に一致させることができるため Yes と出力します。

入力例 2

z
a

出力例 2

Yes

高橋君が K=1 を選ぶと S と T が一致します。
z の 1 個後ろの英小文字は a であることに注意してください。

入力例 3

ppq
qqp

出力例 3

No

高橋君は非負整数 K をどのように選んでも S を T に一致させることができません。よって、No と出力します。

入力例 4

atcoder
atcoder

出力例 4

Yes

高橋君が K=0 を選ぶと S と T が一致します。

Score : 200 points

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

First, choose a non-negative integer K.
Then, shift each character of S to the right by K (see below).

Here,

a shifted to the right by 1 is b;
b shifted to the right by 1 is c;
c shifted to the right by 1 is d;
\cdots
y shifted to the right by 1 is z;
z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
The lengths of S and T are equal.

Input

Input is given from Standard Input in the following format:

S
T

Output

If Takahashi can make S equal T, print Yes; if not, print No.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

a is shifted to the right by 8 and becomes i,
b is shifted to the right by 8 and becomes j,
c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

D - P(X or Y)

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

配点 : 250 点

問題文

1,2,3,4,5,6 の 6 種類の目が出るサイコロを 2 つ振ったときに、次の 2 つの条件の少なくとも一方を満たす確率を求めてください。

2 つの出目の合計が X 以上である。
2 つの出目の差の絶対値が Y 以上である。

ここで、どちらのサイコロについても 6 種類のどの目が出るかは同様に確からしく、それぞれのサイコロの出目は独立であるとします。

制約

2\leq X\leq13
0\leq Y\leq6
入力はすべて整数

入力

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

X Y

出力

2 つのサイコロの出目が 2 つの条件の少なくとも一方を満たす確率を出力せよ。出力された値と真の値との絶対誤差が 10 ^ {-9} 以下のとき、正答と判定される。

入力例 1

9 3

出力例 1

0.555555555555555555555555555555

2 つのサイコロの出目がそれぞれ x と y であることを (x,y) で表すことにすると、それぞれの条件を満たすのは次の場合です。

2 つのサイコロの出目の和が 9 以上になるのは、(3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6) のとき
2 つのサイコロの出目の差が 3 以上になるのは、(1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3) のとき

これらの条件の少なくとも一方を満たすのは (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6) の 20 通りのいずれかのときです。

よって、求める答えは \dfrac{20}{36}=\dfrac59=0.5555555555\ldots です。

絶対誤差が 10 ^ {-9} 以下のとき正答と判定されるので、0.5555555565 や 0.55555555456789 などと出力しても正解となります。

入力例 2

13 6

出力例 2

2 つのサイコロの出目の和が 13 以上になることも、差が 6 以上になることもありません。

よって、求める答えは 0 です。

入力例 3

10 3

出力例 3

0.5

Score : 250 points

Problem Statement

Two dice, each with six faces 1,2,3,4,5,6, are rolled. Find the probability that at least one of the following two conditions holds:

The sum of the two outcomes is at least X.
The absolute difference of the two outcomes is at least Y.

Each face of each die is equally likely, and the two dice are independent.

Constraints

2 \le X \le 13
0 \le Y \le 6
All input values are integers.

Input

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

X Y

Output

Output the probability that the two outcomes satisfy at least one of the two conditions. Your answer is accepted if its absolute error from the true value is at most 10^{-9}.

Sample Input 1

9 3

Sample Output 1

0.555555555555555555555555555555

Let (x,y) denote the event that the dice show x and y.

The sum is at least 9 for (3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6).
The difference is at least 3 for (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3).

At least one of these conditions holds for the following 20 pairs: (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6).

Thus, the answer is \dfrac{20}{36}=\dfrac59=0.5555555555\ldots.

Because an absolute error of at most 10^{-9} is allowed, outputs such as 0.5555555565 or 0.55555555456789 are accepted.

Sample Input 2

13 6

Sample Output 2

Neither the sum of two dice can be 13 or greater, nor can their difference be 6 or greater.

Thus, the answer is 0.

Sample Input 3

10 3

Sample Output 3

0.5

E - Make Them Narrow

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

配点 : 250 点

問題文

長さ N の数列 A が与えられます。
A のうち丁度 K 要素を自由に選んで消し、残った要素を順序を保って連結した数列を B とします。
( B の最大値 ) - ( B の最小値 ) としてありうる最小値を求めてください。

制約

入力は全て整数
1 \le K < N \le 2 \times 10^5
1 \le A_i \le 10^9

入力

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

N K
A_1 A_2 \dots A_N

出力

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

入力例 1

5 2
3 1 5 4 9

出力例 1

A=(3,1,5,4,9) から丁度 2 要素を自由に選んで消すことを考えます。

例えば 2 要素目の 1 、 5 要素目の 9 を消すと、消した後の数列 B=(3,5,4) となります。
- このとき B の最大値は 5 、最小値は 3 なので ( B の最大値 ) - ( B の最小値 ) =2 となり、これは達成可能な最小値です。

入力例 2

6 5
1 1 1 1 1 1

出力例 2

入力例 3

8 3
31 43 26 6 18 36 22 13

出力例 3

Score : 250 points

Problem Statement

You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.

Constraints

All inputs are integers.
1 \le K < N \le 2 \times 10^5
1 \le A_i \le 10^9

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

5 2
3 1 5 4 9

Sample Output 1

Consider removing exactly two elements from A=(3,1,5,4,9).

For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
- In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.

Sample Input 2

6 5
1 1 1 1 1 1

Sample Output 2

Sample Input 3

8 3
31 43 26 6 18 36 22 13