AtCoder Daily Training EASY 2024/10/09 16:00start

A - On and Off

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

配点 : 100 点

問題文

高橋君は、毎日 S 時 0 分に部屋の電気をつけ、毎日 T 時 0 分に消します。
電気をつけている間に日付が変わることもあります。

X 時 30 分に部屋の電気がついているかどうか判定してください。

制約

0 \leq S, T, X \leq 23
S \neq T
入力は全て整数である。

入力

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

S T X

出力

X 時 30 分に部屋の電気がついているならば Yes と、そうでなければ No と出力せよ。

入力例 1

7 20 12

出力例 1

Yes

部屋の電気がついているのは 7 時 0 分から 20 時 0 分までの間です。12 時 30 分には電気がついているので、Yes と出力します。

入力例 2

20 7 12

出力例 2

No

部屋の電気がついているのは 0 時 0 分から 7 時 0 分までの間と、20 時 0 分から（次の日の）0 時 0 分までの間です。 12 時 30 分には電気がついていないので、No と出力します。

入力例 3

23 0 23

出力例 3

Yes

Score : 100 points

Problem Statement

Takahashi turns on the light of his room at S o'clock (on the 24-hour clock) every day and turns it off at T o'clock every day.
The date may change while the light is on.

Determine whether the light is on at 30 minutes past X o'clock.

Constraints

0 \leq S, T, X \leq 23
S \neq T
All values in input are integers.

Input

Input is given from Standard Input in the following format:

S T X

Output

If the light is on at 30 minutes past X o'clock, print Yes; otherwise, print No.

Sample Input 1

7 20 12

Sample Output 1

Yes

The light is on between 7 o'clock and 20 o'clock. At 30 minutes past 12 o'clock, it is on, so we print Yes.

Sample Input 2

20 7 12

Sample Output 2

No

The light is on between 0 o'clock and 7 o'clock, and between 20 o'clock and 0 o'clock (on the next day). At 30 minutes past 12 o'clock, it is off, so we print No.

Sample Input 3

23 0 23

Sample Output 3

Yes

B - Exact Price

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

配点 : 100 点

問題文

高橋君の財布の中には 100 円硬貨が 1 枚以上入っており、それ以外には何も入っていません。

高橋君の財布の中の合計金額が X 円である可能性はありますか？

制約

0 \leq X \leq 1000
入力は全て整数

入力

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

出力

高橋君の財布の中の合計金額が X 円である可能性がある場合は Yes、そうでない場合は No と出力せよ。

入力例 1

出力例 1

Yes

財布に 100 円硬貨が 5 枚入っているとき、合計金額は 500 円になります。故に財布の中の合計金額は X=500 円になりうるため、Yes を出力します。

入力例 2

出力例 2

No

入力例 3

出力例 3

No

財布の中には 100 円硬貨が 1 枚以上入っていることに注意してください。

Score : 100 points

Problem Statement

Takahashi's purse has one or more 100-yen coins in it and nothing else. (Yen is the Japanese currency.)

Is it possible that the total amount of money in the purse is X yen?

Constraints

0 \leq X \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

If it is possible that the total amount of money in Takahashi's purse is X yen, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

If the purse has five 100-yen coins, the total amount of money is 500 yen. Thus, it is possible that the total amount is X=500 yen, so we should print Yes.

Sample Input 2

Sample Output 2

No

Sample Input 3

Sample Output 3

No

Note that the purse has at least one 100-yen coin.

C - Piano 3

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

配点 : 200 点

問題文

高橋君は、横一列に並んだ 100 個の鍵盤からなるピアノを持っています。このピアノの左から i 個目の鍵盤のことを鍵盤 i と呼びます。

高橋君は今から N 回にわたってこのピアノの鍵盤を一つずつ押すことでとある曲を演奏します。 i 回目に押す鍵盤は鍵盤 A_i であり、それを押す手は S_i= L のとき左手、S_i= R のとき右手です。

演奏を始める前、高橋君は両手をそれぞれ好きな鍵盤の上に置くことができ、この時点での疲労度は 0 です。演奏中、片方の手を鍵盤 x の上から鍵盤 y の上へと動かすと疲労度が |y-x| 増加します（逆に、手の移動以外で疲労度が増加することはありません）。なお、ある手である鍵盤を押すためには、その手がその鍵盤の上に置かれている必要があります。

演奏が終了した時点での疲労度は最小でいくつになるか求めてください。

制約

1\leq N \leq 100
1\leq A_i \leq 100
N,A_i は整数
S_i は L または R

入力

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

出力

演奏が終了した時点での疲労度の最小値を出力せよ。

入力例 1

4
3 L
6 R
9 L
1 R

出力例 1

例えば以下のように演奏することができます。

最初、左手を鍵盤 3 の上に、右手を鍵盤 6 の上に置いておく。
左手で鍵盤 3 を押す。
右手で鍵盤 6 を押す。
左手を鍵盤 3 の上から鍵盤 9 の上へと動かす。疲労度が |9-3|=6 増加する。
右手を鍵盤 6 の上から鍵盤 1 の上へと動かす。疲労度が |1-6|=5 増加する。
左手で鍵盤 9 を押す。
右手で鍵盤 1 を押す。

このとき、演奏が終了した時点での疲労度は 6+5=11 であり、これが最小です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 200 points

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

1 \leq N \leq 100
1 \leq A_i \leq 100
N and A_i are integers.
S_i is L or R.

Input

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

Output

Print the minimum fatigue level at the end of the performance.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

For example, the performance can be done as follows:

Initially, place the left hand on key 3 and the right hand on key 6.
Press key 3 with the left hand.
Press key 6 with the right hand.
Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
Press key 9 with the left hand.
Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

D - Substring

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

配点 : 200 点

問題文

英小文字からなる文字列 S が与えられます。S の空でない部分文字列は何種類ありますか？

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

制約

S は英小文字からなる長さ 1 以上 100 以下の文字列

入力

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

出力

答えを出力せよ。

入力例 1

yay

出力例 1

S の空でない部分文字列は以下の 5 種類です。

a
y
ay
ya
yay

入力例 2

aababc

出力例 2

入力例 3

abracadabra

出力例 3

Score: 200 points

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Input

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

Output

Print the answer.

Sample Input 1

yay

Sample Output 1

S has the following five different non-empty substrings:

a
y
ay
ya
yay

Sample Input 2

aababc

Sample Output 2

Sample Input 3

abracadabra

Sample Output 3

E - Sum = 0

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

配点 : 350 点

問題文

N 個の整数の組 (L_1,R_1),(L_2,R_2),\ldots,(L_N,R_N) が与えられます。

以下の条件を満たす長さ N の整数列 X=(X_1,X_2,\ldots,X_N) が存在するか判定し、存在するならば一つ出力してください。

各 i=1,2,\ldots,N に対して L_i\leq X_i\leq R_i
\displaystyle \sum_{i=1}^N X_i=0

制約

1\leq N\leq 2\times 10^5
-10^9\leq L_i\leq R_i\leq 10^9
入力は全て整数

入力

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

存在しない場合は No を出力せよ。存在する場合は条件を満たす整数列 X を以下の形式で出力せよ。

Yes
X_1 X_2 \ldots X_N

答えが複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

出力例 1

Yes
4 -3 -1

数列 X=(4,-3,-1) は問題の条件をすべて満たします。ほかにも (3,-3,0) や (5,-4,-1) などが条件を満たします。

入力例 2

出力例 2

No

条件を満たす整数列 X は存在しません。

入力例 3

出力例 3

Yes
-66 -57 31 -6 89 9

Score : 350 points

Problem Statement

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).

Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.

L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
\displaystyle \sum_{i=1}^N X_i = 0.

Constraints

1 \leq N \leq 2 \times 10^5
-10^9 \leq L_i \leq R_i \leq 10^9
All input values are integers.

Input

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

If no solution exists, print No. Otherwise, print an integer sequence X that satisfies the conditions in the following format:

Yes
X_1 X_2 \ldots X_N

If multiple solutions exist, any of them will be considered correct.

Sample Input 1

Sample Output 1

Yes
4 -3 -1

The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).

Sample Input 2

Sample Output 2

No

No sequence X satisfies the conditions.

Sample Input 3

Sample Output 3

Yes
-66 -57 31 -6 89 9