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

A - Intersection

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

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個の座席が並んでおり、座席には 1, 2, \ldots, N の番号が付けられています。

座席の状態は #, . からなる長さ N の文字列 S によって与えられます。S の i 文字目が # のとき座席 i には人が座っていることを表し、S の i 文字目が . のとき座席 i には人が座っていないことを表します。

1 以上 N - 2 以下の整数 i であって、以下の条件を満たすものの個数を求めてください。

座席 i, i + 2 には人が座っており、座席 i + 1 には人が座っていない

制約

N は 1 以上 2 \times 10^5 以下の整数
S は #, . からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

6
#.##.#

出力例 1

i = 1, 4 が条件を満たすので、答えは 2 です。

入力例 2

1
#

出力例 2

入力例 3

9
##.#.#.##

出力例 3

Score : 100 points

Problem Statement

There are N seats in a row, numbered 1, 2, \ldots, N.

The state of the seats is given by a string S of length N consisting of # and .. If the i-th character of S is #, it means seat i is occupied; if it is ., seat i is unoccupied.

Find the number of integers i between 1 and N - 2, inclusive, that satisfy the following condition:

Seats i and i + 2 are occupied, and seat i + 1 is unoccupied.

Constraints

N is an integer satisfying 1 \leq N \leq 2 \times 10^5.
S is a string of length N consisting of # and ..

Input

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

N
S

Output

Print the answer.

Sample Input 1

6
#.##.#

Sample Output 1

i = 1 and 4 satisfy the condition, so the answer is 2.

Sample Input 2

1
#

Sample Output 2

Sample Input 3

9
##.#.#.##

Sample Output 3

C - 326-like Numbers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

3 桁の正整数であって、百の位の数と十の位の数の積が一の位の数と等しいものを 326-like number と呼びます。

例えば 326,400,144 は 326-like number であり、623,777,429 は 326-like number ではありません。

整数 N が与えられるので、N 以上の最小の 326-like number を求めてください。なお、制約の条件下で答えは必ず存在します。

制約

100 \leq N \leq 919
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

320,321,322,323,324,325 は 326-like number ではなく、326 は 326-like number です。

入力例 2

出力例 2

144 は 326-like number です。

入力例 3

出力例 3

Score : 200 points

Problem Statement

A 326-like number is a three-digit positive integer where the product of the hundreds and tens digits equals the ones digit.

For example, 326,400,144 are 326-like numbers, while 623,777,429 are not.

Given an integer N, find the smallest 326-like number greater than or equal to N. It always exists under the constraints.

Constraints

100 \leq N \leq 919
N is an integer.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

320,321,322,323,324,325 are not 326-like numbers, while 326 is a 326-like number.

Sample Input 2

Sample Output 2

144 is a 326-like number.

Sample Input 3

Sample Output 3

D - AtCoder Quiz

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder では現在、 ABC , ARC , AGC , AHC の 4 つのコンテストが定期的に開催されています。

AtCoder で現在定期的に開催されているコンテストは S_1 , S_2 , S_3 とあと 1 つは何ですか?

制約

S_1 , S_2 , S_3 はそれぞれ、 ABC , ARC , AGC , AHC のいずれかである。
S_1 , S_2 , S_3 は相異なる。

入力

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

S_1
S_2
S_3

出力

答えを出力せよ。

入力例 1

ARC
AGC
AHC

出力例 1

ABC

ARC , AGC , AHC の 3つが入力として与えられているので、残りの 1 つはABC です。

入力例 2

AGC
ABC
ARC

出力例 2

AHC

Score : 200 points

Problem Statement

AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.

What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?

Constraints

Each of S_1, S_2, and S_3 is ABC, ARC, AGC, or AHC.
S_1, S_2, and S_3 are pairwise different.

Input

Input is given from Standard Input in the following format:

S_1
S_2
S_3

Output

Print the answer.

Sample Input 1

ARC
AGC
AHC

Sample Output 1

ABC

Given in input are ARC, AGC, and AHC. The rest is ABC.

Sample Input 2

AGC
ABC
ARC

Sample Output 2

AHC

E - Divide and Divide

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

黒板に整数 N が 1 個書かれています。
高橋君は黒板に書かれている 2 以上の整数が全て無くなるまで以下の一連の操作を繰り返します。

黒板に書かれている 2 以上の整数を 1 つ選び x とする。
黒板から x を 1 個消す。そして、2 個の整数 \left \lfloor \dfrac{x}{2} \right\rfloor, \left\lceil \dfrac{x}{2} \right\rceil を新たに黒板に書く。
この一連の操作を行うために高橋君は x 円払う必要がある。

ここで \lfloor a \rfloor は a 以下の整数のうち最大のものを、\lceil a \rceil は a 以上の整数のうち最小のものを意味します。

操作を行えなくなった時点で高橋君が払った金額の総和は何円ですか？
なお、どのような順番で操作を行っても高橋君が払う金額の総和は一定であることが証明できます。

制約

2 \leq N \leq 10^{17}

入力

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

出力

高橋君が払った金額の総和が何円であるかを出力せよ。

入力例 1

出力例 1

高橋君が行う操作の一例を挙げると次のようになります。

はじめ、黒板には 3 が 1 個書かれている。
高橋君は 3 を選ぶ。高橋君は 3 円を払い、黒板から 3 を 1 個消して \left \lfloor \dfrac{3}{2} \right\rfloor = 1, \left\lceil \dfrac{3}{2} \right\rceil = 2 を新たに黒板に書く。
黒板には 2 が 1 個と 1 が 1 個書かれている。
高橋君は 2 を選ぶ。高橋君は 2 円を払い、黒板から 2 を 1 個消して \left \lfloor \dfrac{2}{2} \right\rfloor = 1, \left\lceil \dfrac{2}{2} \right\rceil = 1 を新たに黒板に書く。
黒板には 1 が 3 個書かれている。
黒板から 2 以上の整数が全て無くなったので操作を終了する。

操作全体で高橋君は 3 + 2 = 5 円払ったので、5 を出力します。

入力例 2

出力例 2

入力例 3

100000000000000000

出力例 3

5655884811924144128

Score: 300 points

Problem Statement

There is a single integer N written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than 2 are removed from the blackboard:

Choose one integer x not less than 2 written on the blackboard.
Erase one occurrence of x from the blackboard. Then, write two new integers \left \lfloor \dfrac{x}{2} \right\rfloor and \left\lceil \dfrac{x}{2} \right\rceil on the blackboard.
Takahashi must pay x yen to perform this series of operations.

Here, \lfloor a \rfloor denotes the largest integer not greater than a, and \lceil a \rceil denotes the smallest integer not less than a.

What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.

Constraints

2 \leq N \leq 10^{17}

Input

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

Output

Print the total amount of money Takahashi will have paid, in yen.

Sample Input 1

Sample Output 1

Here is an example of how Takahashi performs the operations:

Initially, there is one 3 written on the blackboard.
He chooses 3. He pays 3 yen, erases one 3 from the blackboard, and writes \left \lfloor \dfrac{3}{2} \right\rfloor = 1 and \left\lceil \dfrac{3}{2} \right\rceil = 2 on the blackboard.
There is one 2 and one 1 written on the blackboard.
He chooses 2. He pays 2 yen, erases one 2 from the blackboard, and writes \left \lfloor \dfrac{2}{2} \right\rfloor = 1 and \left\lceil \dfrac{2}{2} \right\rceil = 1 on the blackboard.
There are three 1s written on the blackboard.
Since all integers not less than 2 have been removed from the blackboard, the process is finished.

Takahashi has paid a total of 3 + 2 = 5 yen for the entire process, so print 5.

Sample Input 2

Sample Output 2

Sample Input 3

100000000000000000

Sample Output 3

5655884811924144128