AtCoder Daily Training EASY 2024/03/13 18:00start

A - Intersection

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

配点 : 100 点

問題文

数直線があり、高橋君はこれを赤色と青色で次のように塗りました。

X=L_1 から X=R_1 までをすべて赤色で塗る。
X=L_2 から X=R_2 までをすべて青色で塗る。

数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。

制約

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
入力はすべて整数

入力

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

L_1 R_1 L_2 R_2

出力

両方の色で塗られている部分の長さを整数で出力せよ。

入力例 1

0 3 1 5

出力例 1

X=0 から X=3 までが赤く、 X=1 から X=5 までが青く塗られています。

よって、両方の色で塗られている部分は X=1 から X=3 までであり、その長さは 2 となります。

入力例 2

0 1 4 5

出力例 2

両方の色で塗られている部分はありません。

入力例 3

0 3 3 7

出力例 3

赤色と青色で塗られている部分が接している場合でも、両方の色で塗られている部分の長さは 0 となります。

Score : 100 points

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

First, he painted the part from X=L_1 to X=R_1 red.
Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

L_1 R_1 L_2 R_2

Output

Print the length of the part of the line painted both red and blue, as an integer.

Sample Input 1

0 3 1 5

Sample Output 1

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

B - Double Click

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

配点 : 100 点

問題文

高橋君は、時刻 0 にパソコンの電源をつけ、それからマウスを N 回クリックしました。i(1 \le i \le N) 回目のクリックは時刻 T_i に行われました。

高橋君が時刻 x_1 と時刻 x_2 (ただし x_1 < x_2)にマウスを連続してクリックしたとき、x_2 - x_1 \le D であれば時刻 x_2 にダブルクリックが成立したと言います。

高橋君が最初にダブルクリックを成立させた時刻を求めてください。ただし、高橋君が 1 回もダブルクリックを成立させていないならば -1 を出力してください。

制約

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
入力はすべて整数

入力

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

N D
T_1 T_2 \dots T_N

出力

高橋君が 1 回でもダブルクリックを成立させたならば最初にダブルクリックが成立した時刻を、そうでないならば -1 を出力せよ。

入力例 1

4 500
300 900 1300 1700

出力例 1

高橋君は時刻 900,1300 にマウスをクリックしていて、1300 - 900 \le 500 であるため時刻 1300 にダブルクリックが成立しています。

時刻 1300 より前にダブルクリックは成立していないため、1300 を出力してください。

入力例 2

5 99
100 200 300 400 500

出力例 2

-1

高橋君は 1 回もダブルクリックを成立させていません。よって、-1 を出力してください。

入力例 3

4 500
100 600 1100 1600

出力例 3

高橋君が複数回ダブルクリックを成立させていても、そのうち最初の時刻のみを出力することに注意してください。

Score : 100 points

Problem Statement

Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.

If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.

What time was a double click fired for the first time? If no double click was fired, print -1 instead.

Constraints

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
All values in the input are integers.

Input

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

N D
T_1 T_2 \dots T_N

Output

If at least one double click was fired, print the time of the first such event; otherwise, print -1.

Sample Input 1

4 500
300 900 1300 1700

Sample Output 1

Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.

A double click had not been fired before time 1300, so 1300 should be printed.

Sample Input 2

5 99
100 200 300 400 500

Sample Output 2

-1

No double click was fired, so print -1.

Sample Input 3

4 500
100 600 1100 1600

Sample Output 3

If multiple double clicks were fired, be sure to print only the first such event.

C - Minimize Abs 1

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

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。

i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。

L\leq X_i \leq R
L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす

制約

1\leq N\leq 2\times 10^5
1\leq L\leq R \leq 10^9
1\leq A_i\leq 10^9
入力は全て整数

入力

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

N L R
A_1 \ldots A_N

出力

i=1,2,\ldots,N について X_i を空白区切りで出力せよ。

入力例 1

5 4 7
3 1 4 9 7

出力例 1

4 4 4 7 7

i=1 では、

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

より X_i = 4 です。

入力例 2

3 10 10
11 10 9

出力例 2

10 10 10

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

L\leq X_i \leq R.
For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

1\leq N\leq 2\times 10^5
1\leq L\leq R \leq 10^9
1\leq A_i\leq 10^9
All input values are integers.

Input

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

N L R
A_1 \ldots A_N

Output

Print X_i for i=1,2,\ldots,N, separated by spaces.

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10

D - Extended ABC

実行時間制限: 2 sec / メモリ制限: 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 - One More aab aba baa

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

配点 : 300 点

問題文

文字列 S の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から K 番目にくる文字列を求めてください。

「各文字を並べ替えて作ることが可能な文字列」とは？

「文字列 A が文字列 B の各文字を並べ替えて作ることが可能な文字列である」とは、任意の文字が文字列 A と文字列 B に同数含まれるということを指します。

制約

1 \le |S| \le 8
S は英小文字のみからなる
S の各文字を並べ替えてできる文字列は K 種類以上存在する

入力

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

S K

出力

答えを出力せよ。

入力例 1

aab 2

出力例 1

aba

文字列 aab の各文字を並べ替えて作ることが可能な文字列は \{ aab, aba, baa \} の 3 つですが、このうち辞書順で前から 2 番目にくるものは aba です。

入力例 2

baba 4

出力例 2

baab

入力例 3

ydxwacbz 40320

出力例 3

zyxwdcba

Score : 300 points

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

What is a permutation of a string?

A string A is said to be a permutation of a string B when any character occurs the same number of times in A and B.

Constraints

1 \le |S| \le 8
S consists of lowercase English letters.
There are at least K distinct strings that are permutations of S.

Input

Input is given from Standard Input in the following format:

S K

Output

Print the answer.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba