AtCoder Daily Training EASY 2026/10/23 16:00start

A - 123233

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

配点 : 100 点

問題文

6 桁の正整数 N が与えられます。
この整数が以下の条件を全て満たすか判定してください。

N の各桁のうち、 1 は丁度 1 つである。
N の各桁のうち、 2 は丁度 2 つである。
N の各桁のうち、 3 は丁度 3 つである。

制約

N は 100000 \le N \le 999999 を満たす整数

入力

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

出力

N が問題文中の条件を全て満たすなら Yes 、そうでないなら No と 1 行に出力せよ。

入力例 1

出力例 1

Yes

123233 は問題文中の条件を満たすので、 Yes と出力します。

入力例 2

出力例 2

No

123234 は問題文中の条件を満たさないので、 No と出力します。

入力例 3

出力例 3

Yes

入力例 4

出力例 4

No

Score : 100 points

Problem Statement

You are given a 6-digit positive integer N.
Determine whether N satisfies all of the following conditions.

Among the digits of N, the digit 1 appears exactly once.
Among the digits of N, the digit 2 appears exactly twice.
Among the digits of N, the digit 3 appears exactly three times.

Constraints

N is an integer satisfying 100000 \le N \le 999999.

Input

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

Output

Print Yes if N satisfies all the conditions described in the problem statement, and No otherwise, in one line.

Sample Input 1

Sample Output 1

Yes

123233 satisfies the conditions in the problem statement, so print Yes.

Sample Input 2

Sample Output 2

No

123234 does not satisfy the conditions in the problem statement, so print No.

Sample Input 3

Sample Output 3

Yes

Sample Input 4

Sample Output 4

No

B - π

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

配点 : 100 点

問題文

正整数 D が与えられます。

直径が D の円の面積を求めて下さい。

制約

1\le D\le 100
入力される値は整数

入力

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

出力

答えを出力せよ。

真の解との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。

入力例 1

出力例 1

3.141592653589793

直径が 2 の円の面積は 3.141592653589793\ldots です。

入力例 2

出力例 2

38.48451000647496

入力例 3

出力例 3

7542.9639612690935

Score : 100 points

Problem Statement

You are given a positive integer D.

Find the area of a circle with diameter D.

Constraints

1\le D\le 100
The input value is an integer.

Input

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

Output

Output the answer.

Your answer is considered correct if the absolute or relative error from the true answer is at most 10^{-6}.

Sample Input 1

Sample Output 1

3.141592653589793

The area of a circle with diameter 2 is 3.141592653589793\ldots.

Sample Input 2

Sample Output 2

38.48451000647496

Sample Input 3

Sample Output 3

7542.9639612690935

C - Foreign Exchange

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

配点 : 150 点

問題文

1 から N までの番号がつけられた N 個の国があり、i = 1, 2, \ldots, N について、高橋君は国 i の通貨を A_i 単位持っています。

高橋君は、下記の操作を好きな回数（ 0 回でも良い）繰り返します。

まず、1 以上 N-1 以下の整数 i を選ぶ。
その後、国 i の通貨を S_i 単位以上持っているなら、下記の行動を 1 回行う。
- 国 i の通貨を S_i 単位だけ支払い、国 (i+1) の通貨を T_i 単位だけ獲得する。

最終的に高橋君が持っている国 N の通貨の単位数としてあり得る最大値を出力してください。

制約

入力される値はすべて整数
2 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9
1 \leq T_i \leq S_i \leq 10^9

入力

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

出力

答えを出力せよ。

入力例 1

出力例 1

以下の説明では、高橋君が持っている各国の通貨の単位数を、数列 A = (A_1, A_2, A_3, A_4) として表します。はじめ、A = (5, 7, 0, 3) です。

下記の通りに 4 回操作を行うことを考えます。

i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (5, 3, 3, 3) となる。
i = 1 を選び、国 1 の通貨 2 単位を支払って、国 2 の通貨 2 単位を獲得する。その結果、A = (3, 5, 3, 3) となる。
i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (3, 1, 6, 3) となる。
i = 3 を選び、国 3 の通貨 5 単位を支払って、国 4 の通貨 2 単位を獲得する。その結果、A = (3, 1, 1, 5) となる。

このとき、最終的に高橋君が持っている国 4 の通貨の単位数は 5 であり、これが考えられる最大値です。

入力例 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

出力例 2

Score: 150 points

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

First, choose an integer i between 1 and N-1, inclusive.
Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
- Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

All input values are integers.
2 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9
1 \leq T_i \leq S_i \leq 10^9

Input

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

Output

Print the answer.

Sample Input 1

Sample Output 1

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

D - Keep the Change

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

配点 : 200 点

問題文

高橋君は N 軒の店で買い物をしました。はじめ、高橋君は 10000 円持っていました。
i 軒目の店では A_i 円の商品を買って B_i 円支払いました。ここで A_i \leq B_i が成り立ちます。そして、S_i = keep の時、高橋君はお釣りを受け取らず、S_i = take の場合、お釣りを受け取りました。
高橋君が全ての店でお釣りを受け取っていた場合に比べて損した金額を求めてください。厳密に述べると、

高橋君の最終的な所持金を X 円、
高橋君が全ての店でお釣りを受け取っていた場合の最終的な所持金を Y 円

とした時、Y - X を求めてください。

制約

1 \leq N \leq 100
1 \leq A_i \leq B_i \leq 100
S_i は keep または take
N, A_i, B_i は全て整数

入力

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

N
A_1 B_1 S_1
A_2 B_2 S_2
\vdots
A_N B_N S_N

出力

高橋君が全ての店でお釣りを受け取っていた場合に比べて損した金額を出力せよ。

入力例 1

3
1 2 keep
3 6 take
5 9 keep

出力例 1

高橋君の行動を説明すると次の通りです。

1 番目の店で 1 円の商品を買い、2 円支払い、お釣りを受け取らなかった。
2 番目の店で 3 円の商品を買い、6 円支払い、お釣りを受け取った。
3 番目の店で 5 円の商品を買い、9 円支払い、お釣りを受け取らなかった。

入力例 2

8
36 49 take
38 73 keep
27 85 take
65 71 take
52 86 keep
48 60 keep
37 98 keep
5 38 keep

出力例 2

Score : 200 points

Problem Statement

Takahashi made purchases at N stores. Initially, he had 10000 yen.
At the i-th store, he bought an item worth A_i yen and paid B_i yen. Here, A_i \leq B_i holds. If S_i = keep, he did not receive the change, and if S_i = take, he received the change.
Find the amount of money he lost compared to the case where he received the change at every store. To be precise,

let X yen be Takahashi's final amount of money, and
let Y yen be Takahashi's final amount of money in the case where he received the change at every store.

Find Y - X.

Constraints

1 \leq N \leq 100
1 \leq A_i \leq B_i \leq 100
S_i is keep or take.
N, A_i, B_i are all integers.

Input

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

N
A_1 B_1 S_1
A_2 B_2 S_2
\vdots
A_N B_N S_N

Output

Output the amount of money Takahashi lost compared to the case where he received the change at every store.

Sample Input 1

3
1 2 keep
3 6 take
5 9 keep

Sample Output 1

Takahashi's actions are as follows.

At the first store, he bought an item worth 1 yen, paid 2 yen, and did not receive the change.
At the second store, he bought an item worth 3 yen, paid 6 yen, and received the change.
At the third store, he bought an item worth 5 yen, paid 9 yen, and did not receive the change.

Sample Input 2

8
36 49 take
38 73 keep
27 85 take
65 71 take
52 86 keep
48 60 keep
37 98 keep
5 38 keep

Sample Output 2

E - Dango

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

配点 : 300 点

問題文

正の整数 L に対して、レベル L のダンゴ文字列とは、以下の条件を満たす文字列です。

o と - からなる長さ L+1 の文字列である。
先頭の文字と末尾の文字のうちちょうど一方が - であり、そのほかの L 文字はすべて o である。

例えば、ooo- はレベル 3 のダンゴ文字列ですが、-ooo- や oo や o-oo- などはダンゴ文字列ではありません（より正確には、どのような正の整数 L に対してもレベル L のダンゴ文字列ではありません）。

2 種類の文字 o - からなる、長さ N の文字列 S が与えられます。次の条件を満たすような正整数 X のうち、最大のものを求めてください。

S の連続する部分文字列であって、レベル X のダンゴ文字列であるものが存在する。

ただし、そのような整数が存在しない場合、-1 と出力してください。

制約

1\leq N\leq 2\times10^5
S は o - からなる長さ N の文字列

入力

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

N
S

出力

S にレベル X のダンゴ文字列が含まれるような最大の X の値を 1 行で出力せよ。そのような値が存在しない場合、-1 を出力せよ。

入力例 1

10
o-oooo---o

出力例 1

たとえば、S の 3 文字目から 7 文字目までに対応する部分文字列 oooo- は、レベル 4 のダンゴ文字列です。 S の部分文字列であってレベル 5 以上のダンゴ文字列であるようなものは存在しないため、4 と出力してください。

入力例 2

1
-

出力例 2

-1

S の連続する部分文字列は空文字列と - の 2 種類だけです。これらはダンゴ文字列ではないため、-1 と出力してください。

入力例 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

出力例 3

Score : 300 points

Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

It is a string of length L+1 consisting of o and -.
Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

1\leq N\leq 2\times10^5
S is a string of length N consisting of o and -.

Input

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

N
S

Output

Print the greatest positive integer X such that S contains a level-X dango string, or -1 if there is no such integer.

Sample Input 1

10
o-oooo---o

Sample Output 1

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.

Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.

Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o