AtCoder Daily Training EASY 2026/08/24 18:00start

A - π

Time Limit: 2 sec / Memory Limit: 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

B - Good morning

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある日、高橋君は A 時 B 分ちょうどに、青木君は C 時 D 分 1 秒に起きました。
高橋君の起床時刻が青木君より早いならば Takahashi を、そうでないならば Aoki を出力してください。

制約

0 \leq A \leq 23
0 \leq B \leq 59
0 \leq C \leq 23
0 \leq D \leq 59
入力はすべて整数である。

入力

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

A B C D

出力

高橋君の起床時刻が青木君より早いならば Takahashi を、そうでないならば Aoki を出力せよ。

入力例 1

7 0 6 30

出力例 1

Aoki

高橋君は 7 時ちょうどに、青木君は 6 時 30 分 1 秒に起きました。青木君の起床時刻の方が早いため、Aoki を出力します。

入力例 2

7 30 7 30

出力例 2

Takahashi

高橋君は 7 時 30 分ちょうどに、青木君は 7 時 30 分 1 秒に起きました。高橋君の起床時刻の方が 1 秒だけ早いため、Takahashi を出力します。

入力例 3

0 0 23 59

出力例 3

Takahashi

ある日の 0 時 0 分ちょうどはその日の 0 時 1 分の 1 分前であり、その日の 23 時 59 分の 1 分後、すなわちいわゆる 24 時ちょうどのことではありません。よって、高橋君の起床時刻の方が早く、Takahashi を出力します。

Score : 100 points

Problem Statement

One day, Takahashi got up at exactly B minutes past A o'clock (in 24-hour clock), and Aoki got up at exactly D minutes and 1 second past C o'clock.
If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Constraints

0 \leq A \leq 23
0 \leq B \leq 59
0 \leq C \leq 23
0 \leq D \leq 59
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Sample Input 1

7 0 6 30

Sample Output 1

Aoki

Takahashi got up at 7 sharp, and Aoki got up at 30 minutes and 1 second past 6 o'clock. Aoki was the first to get up, so Aoki should be printed.

Sample Input 2

7 30 7 30

Sample Output 2

Takahashi

Takahashi got up at exactly half past 7, and Aoki got up at 30 minutes and 1 second past 7 o'clock. Just by one second, Takahashi was the first to get up, so Takahashi should be printed.

Sample Input 3

0 0 23 59

Sample Output 3

Takahashi

0:00 in a day is one minute before 0:01, not one minute past 23:59 ("24:00"). Thus, Takahashi was the first to get up, so Takahashi should be printed.

C - You're a teapot

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

I begin with T and end with T, and I am full of T. What am I?

文字列 t について、充填率を以下のように定義します。

t の先頭と末尾の文字がともに t であり、かつ |t| \geq 3 である場合: t に含まれる t の個数を x とすると、t の充填率は \displaystyle\frac{x-2}{|t|-2} である。ここで、|t| は t の長さを表す。
そうでない場合: t の充填率は 0 である。

文字列 S が与えられます。S の部分文字列の充填率としてありうる最大値を求めてください。

部分文字列とは

S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。例えば、ab, bc, bcd は abcd の部分文字列ですが、ac, dc, e は abcd の部分文字列ではありません。

制約

1 \leq |S| \leq 100
S は英小文字からなる文字列。

入力

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

出力

S の部分文字列の充填率としてありうる最大値を出力せよ。

出力された値と真の値との絶対誤差が 10^{-9} 以下のとき、正答と判定される。

入力例 1

attitude

出力例 1

0.50000000000000000

ttit は S の部分文字列であり、その充填率は \displaystyle\frac{3-2}{4-2} = \frac{1}{2} です。

充填率が \frac{1}{2} より高い部分文字列は存在しないので、答えは \frac{1}{2} です。

入力例 2

ottottott

出力例 2

0.66666666666666667

ttottott は S の部分文字列であり、その充填率は \displaystyle\frac{6-2}{8-2} = \frac{2}{3} です。

充填率が \frac{2}{3} より高い部分文字列は存在しないので、答えは \frac{2}{3} です。

入力例 3

coffeecup

出力例 3

0.00000000000000000

ff は S の部分文字列であり、その充填率は 0 です。

充填率が 0 より高い部分文字列は存在しないので、答えは 0 です。

Score : 200 points

Problem Statement

I begin with T and end with T, and I am full of T. What am I?

For a string t, define the filling rate as follows:

If the first and last characters of t are both t and |t| \geq 3: Let x be the number of t in t. Then the filling rate of t is \displaystyle\frac{x-2}{|t|-2}, where |t| denotes the length of t.
Otherwise: the filling rate of t is 0.

You are given a string S. Find the maximum possible filling rate of a substring of S.

What is a substring?

A substring of S is a string obtained by removing zero or more characters from the beginning and the end of S. For example, ab, bc, and bcd are substrings of abcd, while ac, dc, and e are not substrings of abcd.

Constraints

1 \leq |S| \leq 100
S is a string consisting of lowercase English letters.

Input

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

Output

Print the maximum possible filling rate of a substring of S.

Your output will be judged as correct when the absolute error from the true value is at most 10^{-9}.

Sample Input 1

attitude

Sample Output 1

0.50000000000000000

ttit is a substring of S, and its filling rate is \displaystyle\frac{3-2}{4-2} = \frac{1}{2}.

There is no substring with a filling rate greater than \frac{1}{2}, so the answer is \frac{1}{2}.

Sample Input 2

ottottott

Sample Output 2

0.66666666666666667

ttottott is a substring of S, and its filling rate is \displaystyle\frac{6-2}{8-2} = \frac{2}{3}.

There is no substring with a filling rate greater than \frac{2}{3}, so the answer is \frac{2}{3}.

Sample Input 3

coffeecup

Sample Output 3

0.00000000000000000

ff is a substring of S, and its filling rate is 0.

There is no substring with a filling rate greater than 0, so the answer is 0.

D - Four Hidden

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

英小文字と ? からなる文字列 T と、英小文字のみからなる文字列 U が与えられます。

T は、英小文字のみからなる文字列 S のちょうど 4 文字を ? で置き換えることで得られた文字列です。

S が U を連続部分文字列として含んでいた可能性があるかどうか判定してください。

制約

T は長さ 4 以上 10 以下の英小文字と ? からなる文字列
T にはちょうど 4 つの ? が含まれる
U は長さ 1 以上 |T| 以下の英小文字からなる文字列

入力

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

T
U

出力

S が U を部分文字列として含んでいた可能性があるならば Yes を、そうでないならば No を出力せよ。

入力例 1

tak??a?h?
nashi

出力例 1

Yes

例えば、S が takanashi である場合、これは nashi を連続部分文字列として含みます。

入力例 2

??e??e
snuke

出力例 2

No

? がどのような文字であっても、S は snuke を連続部分文字列として含むことがありません。

入力例 3

????
aoki

出力例 3

Yes

Score : 250 points

Problem Statement

You are given a string T consisting of lowercase English letters and ?, and a string U consisting of lowercase English letters.

The string T is obtained by taking some lowercase-only string S and replacing exactly four of its characters with ?.

Determine whether it is possible that the original string S contained U as a contiguous substring.

Constraints

T is a string of length between 4 and 10, inclusive, consisting of lowercase letters and ?.
T contains exactly four occurrences of ?.
U is a string of length between 1 and |T|, inclusive, consisting of lowercase letters.

Input

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

T
U

Output

Print Yes if it is possible that the original string S contained U as a contiguous substring; otherwise, print No.

Sample Input 1

tak??a?h?
nashi

Sample Output 1

Yes

For example, if S is takanashi, it contains nashi as a contiguous substring.

Sample Input 2

??e??e
snuke

Sample Output 2

No

No matter what characters replace the ?s in T, S cannot contain snuke as a contiguous substring.

Sample Input 3

????
aoki

Sample Output 3

Yes

E - Merge Sequences

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の狭義単調増加列 A=(A _ 1,A _ 2,\ldots,A _ N) と、長さ M の狭義単調増加列 B=(B _ 1,B _ 2,\ldots,B _ M) が与えられます。ここで、すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j が成り立っています。

長さ N+M の狭義単調増加列 C=(C _ 1,C _ 2,\ldots,C _ {N+M}) を、次の操作を行った結果得られる列として定めます。

C を A と B を連結した列とする。厳密には、i=1,2,\ldots,N について C _ i=A _ i とし、i=N+1,N+2,\ldots,N+M について C _ i=B _ {i-N} とする。
C を昇順にソートする。

A _ 1,A _ 2,\ldots,A _ N と B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるか求めてください。より厳密には、まず i=1,2,\ldots,N について C _ k=A _ i を満たす k を順に求めたのち、j=1,2,\ldots,M について C _ k=B _ j を満たす k を順に求めてください。

制約

1\leq N,M\leq 10^5
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j
入力はすべて整数

入力

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

N M
A _ 1 A _ 2 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

出力

答えを 2 行で出力せよ。
1 行目には A _ 1,A _ 2,\ldots,A _ N がそれぞれ C では何番目にあるかを空白区切りで出力せよ。
2 行目には B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるかを空白区切りで出力せよ。

入力例 1

4 3
3 14 15 92
6 53 58

出力例 1

1 3 4 7
2 5 6

C は (3,6,14,15,53,58,92) となります。 A=(3,14,15,92) の要素はそれぞれ 1,3,4,7 番目にあり、B=(6,53,58) の要素はそれぞれ 2,5,6 番目にあります。

入力例 2

4 4
1 2 3 4
100 200 300 400

出力例 2

1 2 3 4
5 6 7 8

入力例 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

出力例 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

Score : 300 points

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

1\leq N,M\leq 10^5
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
All values in the input are integers.

Input

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

N M
A _ 1 A _ 2 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

Output

Print the answer in two lines.
The first line should contain the positions of A _ 1,A _ 2,\ldots,A _ N in C, with spaces in between.
The second line should contain the positions of B _ 1,B _ 2,\ldots,B _ M in C, with spaces in between.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19