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

A - illegal

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

配点 : 100 点

問題文

高橋君の住む AtCoder 国には「長さが 5 の倍数である文字列を書いてはならない」という奇妙な法律があります。

高橋君は文字列 S を書きました。高橋君がこの法律に違反しているかどうか判定してください。

制約

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

入力

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

出力

高橋君が法律に違反しているのであれば Yes を、違反していないのであれば No を出力せよ。

入力例 1

legal

出力例 1

Yes

legal は長さが 5 の文字列です。よって、高橋君は法律に違反しているため Yes と出力してください。

入力例 2

atcoder

出力例 2

No

atcoder は長さが 7 の文字列です。よって、高橋君は法律に違反していないため No と出力してください。

入力例 3

illegal

出力例 3

No

Score : 100 points

Problem Statement

In the country of AtCoder where Takahashi lives, there is a peculiar law: "You must not write a string whose length is a multiple of 5."

Takahashi wrote a string S. Determine whether he is violating this law.

Constraints

S is a string of length between 1 and 10, inclusive.
S consists of lowercase English letters.

Input

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

Output

If Takahashi is violating the law, output Yes; otherwise, output No.

Sample Input 1

legal

Sample Output 1

Yes

legal is a string of length 5. Thus, Takahashi is violating the law, so output Yes.

Sample Input 2

atcoder

Sample Output 2

No

atcoder is a string of length 7. Thus, Takahashi is not violating the law, so output No.

Sample Input 3

illegal

Sample Output 3

No

B - Zero Sum Game

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

配点 : 100 点

問題文

1 から N の番号が付けられた N 人の人がおり、この中で一対一の勝敗のつくゲームを何度か行いました。N 人は最初にそれぞれ持ち点として 0 を持っており、各ゲームでは勝者の持ち点が 1 増え、敗者の持ち点が 1 減ります（持ち点が負になることもあります）。最終的に人 i\ (1\leq i\leq N-1) の持ち点が A_i になったとき、人 N の持ち点を求めてください。なお、ゲームの進行によらず最終的な人 N の持ち点は一意に定まることが示せます。

制約

2\leq N\leq 100
-100\leq A_i\leq 100
入力は全て整数

入力

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

N
A_1 A_2 \ldots A_{N-1}

出力

答えを出力せよ。

入力例 1

4
1 -2 -1

出力例 1

最終的に人 1,2,3 の持ち点が 1,-2,-1 となるような進行として、例えば次のようなものが考えられます。

最初、人 1,2,3,4 の持ち点はそれぞれ 0,0,0,0 である。
人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-1,0,0 である。
人 1 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 0,-1,0,1 である。
人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-2,0,1 である。
人 2 と 3 が対戦して、人 2 が勝利する。4 人の持ち点はそれぞれ 1,-1,-1,1 である。
人 2 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 1,-2,-1,2 である。

この場合、人 4 の持ち点は 2 になります。ほかにも別の進行が考えられますが、どのような進行であっても人 4 の持ち点は 2 になります。

入力例 2

3
0 0

出力例 2

入力例 3

6
10 20 30 40 50

出力例 3

-150

Score: 100 points

Problem Statement

There are N people labeled 1 to N, who have played several one-on-one games without draws. Initially, each person started with 0 points. In each game, the winner's score increased by 1 and the loser's score decreased by 1 (scores can become negative). Determine the final score of person N if the final score of person i\ (1\leq i\leq N-1) is A_i. It can be shown that the final score of person N is uniquely determined regardless of the sequence of games.

Constraints

2 \leq N \leq 100
-100 \leq A_i \leq 100
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_{N-1}

Output

Print the answer.

Sample Input 1

4
1 -2 -1

Sample Output 1

Here is one possible sequence of games where the final scores of persons 1, 2, 3 are 1, -2, -1, respectively.

Initially, persons 1, 2, 3, 4 have 0, 0, 0, 0 points, respectively.
Persons 1 and 2 play, and person 1 wins. The players now have 1, -1, 0, 0 point(s).
Persons 1 and 4 play, and person 4 wins. The players now have 0, -1, 0, 1 point(s).
Persons 1 and 2 play, and person 1 wins. The players now have 1, -2, 0, 1 point(s).
Persons 2 and 3 play, and person 2 wins. The players now have 1, -1, -1, 1 point(s).
Persons 2 and 4 play, and person 4 wins. The players now have 1, -2, -1, 2 point(s).

In this case, the final score of person 4 is 2. Other possible sequences of games exist, but the score of person 4 will always be 2 regardless of the progression.

Sample Input 2

3
0 0

Sample Output 2

Sample Input 3

6
10 20 30 40 50

Sample Output 3

-150

C - Ticket Gate Log

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

配点 : 250 点

問題文

高橋君は改札機の利用履歴を集計しました。しかし、高橋君はうっかりいくつかの入退場記録を消してしまいました。高橋君は消してしまった記録の復元を試みようとしています。

i, o のみからなる文字列 S が与えられます。 S の任意の位置に文字を 0 文字以上挿入することで、変更後の文字列が以下の条件を満たすようにしたいです。

長さが偶数であり、奇数文字目が i で偶数文字目が o である。

挿入する必要のある文字数の最小値を求めて下さい。なお、問題の制約下で、有限個の文字を適切に挿入することで、S が条件をみたすようにできることが証明できます。

制約

S は i, o からなる長さ 1 以上 100 以下の文字列

入力

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

出力

答えを出力せよ。

入力例 1

ioi

出力例 1

3 文字目のあとに o を挿入して ioio とすることで、条件を満たすことができます。0 文字以下の挿入で条件を満たすことはできません。

入力例 2

iioo

出力例 2

1 文字目のあとに o を、3 文字目のあとに i を挿入することで、条件を満たすことができます。1 文字以下の挿入で条件を満たすことはできません。

入力例 3

io

出力例 3

S がすでに条件を満たします。

Score : 250 points

Problem Statement

Takahashi aggregated usage records from ticket gates. However, he accidentally erased some records of entering and exiting stations. He is trying to restore the erased records.

You are given a string S consisting of i and o. We want to insert zero or more characters at arbitrary positions in S so that the resulting string satisfies the following conditions:

Its length is even, and every odd-numbered (1st, 3rd, ...) character is i while every even-numbered (2nd, 4th, ...) character is o.

Find the minimum number of characters that need to be inserted. It can be proved under the constraints of this problem that by inserting an appropriate finite number of characters, S can be made to satisfy the conditions.

Constraints

S is a string of length between 1 and 100, consisting of i and o.

Input

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

Output

Print the answer.

Sample Input 1

ioi

Sample Output 1

We can insert o after the 3rd character to form ioio to satisfy the conditions. The conditions cannot be satisfied by inserting zero or fewer characters.

Sample Input 2

iioo

Sample Output 2

We can insert o after the 1st character and i after the 3rd character to satisfy the conditions. The conditions cannot be satisfied by inserting one or fewer characters.

Sample Input 3

io

Sample Output 3

S already satisfies the conditions.

D - Two Rings

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

配点 : 250 点

問題文

xy 平面上に 2 つの円 C_1, C_2 があります。ただし、本問題において円とは円周のことを指します。
円 C_1 は中心の座標が (X_1, Y_1) で半径が R_1 です。
円 C_2 は中心の座標が (X_2, Y_2) で半径が R_2 です。
円 C_1 と円 C_2 が共有点を持つかどうかを判定してください。言い換えると、点 (X_1, Y_1) からの距離が R_1 であり、かつ点 (X_2, Y_2) からの距離が R_2 であるような点が 1 個以上存在するかどうかを判定してください。

T 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

制約

1 \leq T \leq 100
0 \leq X_1, Y_1, X_2, Y_2 \leq 10^9
1 \leq R_1, R_2 \leq 10^9
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

X_1 Y_1 R_1 X_2 Y_2 R_2

出力

T 行出力せよ。i 行目には i 番目のテストケースの答えを出力せよ。
各テストケースでは、円 C_1 と円 C_2 が共有点を持つ場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

7
0 0 2 2 3 2
0 0 2 2 3 1
1 2 5 3 2 1
5 4 2 8 8 3
2 1 5 5 1 2
0 0 1 0 0 1
0 0 500000000 1 1000000000 500000000

出力例 1

Yes
No
No
Yes
Yes
Yes
No

例えば 1 番目のテストケースでは、C_1 と C_2 の位置関係は以下の図のようになります。

Score : 250 points

Problem Statement

There are two circles C_1 and C_2 on the xy-plane. In this problem, a circle refers to the circumference.
Circle C_1 has its center at (X_1, Y_1) and radius R_1.
Circle C_2 has its center at (X_2, Y_2) and radius R_2.
Determine whether circles C_1 and C_2 have a common point. In other words, determine whether there exists at least one point whose distance from (X_1, Y_1) is R_1 and whose distance from (X_2, Y_2) is R_2.

You are given T test cases; solve each one.

Constraints

1 \leq T \leq 100
0 \leq X_1, Y_1, X_2, Y_2 \leq 10^9
1 \leq R_1, R_2 \leq 10^9
All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

X_1 Y_1 R_1 X_2 Y_2 R_2

Output

Output T lines. The i-th line should contain the answer for the i-th test case.
For each test case, output Yes if circles C_1 and C_2 have a common point, and No otherwise.

Sample Input 1

7
0 0 2 2 3 2
0 0 2 2 3 1
1 2 5 3 2 1
5 4 2 8 8 3
2 1 5 5 1 2
0 0 1 0 0 1
0 0 500000000 1 1000000000 500000000

Sample Output 1

Yes
No
No
Yes
Yes
Yes
No

For example, in the first test case, the relative positions of C_1 and C_2 are as shown in the following figure.

E - digitnum

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

配点 : 300 点

問題文

整数 N が与えられるので、以下の問題を解いてください。

f(x)= ( x 以下の正整数で、 x と桁数が同じものの数) とします。
f(1)+f(2)+\dots+f(N) を 998244353 で割った余りを求めてください。

制約

N は整数
1 \le N < 10^{18}

入力

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

出力

答えを整数として出力せよ。

入力例 1

出力例 1

1 以上 9 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 1,2,\dots,x です。
- これより、 f(1)=1,f(2)=2,...,f(9)=9 となります。
10 以上 16 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 10,11,\dots,x です。
- これより、 f(10)=1,f(11)=2,...,f(16)=7 となります。

結局、求める答えは 73 です。

入力例 2

出力例 2

入力例 3

999999999999999999

出力例 3

762062362

998244353 で割った余りを求めることに注意してください。

Score : 300 points

Problem Statement

Given an integer N, solve the following problem.

Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.

Constraints

N is an integer.
1 \le N < 10^{18}

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
- Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
- Thus, we have f(10)=1,f(11)=2,...,f(16)=7.

The final answer is 73.

Sample Input 2

Sample Output 2

Sample Input 3

999999999999999999

Sample Output 3

762062362

Be sure to find the sum modulo 998244353.