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

A - Similar String

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

二つの文字 x と y は以下の 3 つの条件のうちどれか 1 つを満たすとき、似た文字と呼ばれます。

x と y は同じ文字
x と y の片方が 1 で、もう片方が l
x と y の片方が 0 で、もう片方が o

また、長さ N の文字列 S と T は以下の条件を満たすとき、似た文字列と呼ばれます。

任意の i\ (1\leq i\leq N) について、 S の i 番目の文字と T の i 番目の文字は似た文字

英小文字及び数字からなる長さ N の文字列 S,T が与えられます。 S と T が似た文字列か判定してください。

制約

N は 1 以上 100 以下の整数
S,T は英小文字及び数字からなる長さ N の文字列

入力

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

N
S
T

出力

S と T が似た文字列の場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

3
l0w
1ow

出力例 1

Yes

S の 1 文字目は lで、T の 1 文字目は 1です。これらは似た文字です。

S の 2 文字目は 0で、T の 2 文字目は oです。これらは似た文字です。

S の 3 文字目は wで、T の 3 文字目は wです。これらは似た文字です。

よって S と T は似た文字列です。

入力例 2

3
abc
arc

出力例 2

No

S の 2 文字目は bで、T の 2 文字目は rです。これらは似た文字ではありません。

よって S と T は似た文字列ではありません。

入力例 3

4
nok0
n0ko

出力例 3

Yes

Score : 100 points

Problem Statement

Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:

x and y are the same character.
One of x and y is 1 and the other is l.
One of x and y is 0 and the other is o.

Two strings S and T, each of length N, are called similar strings if and only if:

for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.

Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.

Constraints

N is an integer between 1 and 100.
Each of S and T is a string of length N consisting of lowercase English letters and digits.

Input

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

N
S
T

Output

Print Yes if S and T are similar strings, and No otherwise.

Sample Input 1

3
l0w
1ow

Sample Output 1

Yes

The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.

The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.

The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.

Thus, S and T are similar strings.

Sample Input 2

3
abc
arc

Sample Output 2

No

The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.

Thus, S and T are not similar strings.

Sample Input 3

4
nok0
n0ko

Sample Output 3

Yes

B - Humidifier 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

AtCoder社のオフィスには加湿器が 1 つあります。現在は時刻 0 であり、加湿器には水が入っていません。

あなたはこの加湿器にこれから N 回水を追加します。i 回目 (1\leq i \leq N)の水の追加は時刻 T_i に行い、水を V_i リットル追加します。なお、 T_i < T_{i+1} (1 \leq i \leq N-1) を満たすことが保証されます。

ただし、加湿器には穴が空いていて、加湿器に水が入っている間は 1 単位時間につき水が 1 リットル減り続けます。

時刻 T_N に水を追加し終えたとき、加湿器に残っている水の量を求めてください。

制約

1 \leq N \leq 100
1 \leq T_i \leq 100 (1 \leq i \leq N)
1 \leq V_i \leq 100 (1 \leq i \leq N)
T_i < T_{i+1} (1 \leq i \leq N-1)
入力は全て整数

入力

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

N
T_1 V_1
T_2 V_2
\vdots
T_N V_N

出力

答えを出力せよ。

入力例 1

出力例 1

時系列で以下のように水が追加されます。

時刻 1 : 水を追加する前は 0 リットル入っており、3 リットル追加して加湿器には 3 リットルの水が入っています。
時刻 3 : 水を追加する前は 1 リットル入っており、1 リットル追加して加湿器には 2 リットルの水が入っています。
時刻 4 : 水を追加する前は 1 リットル入っており、4 リットル追加して加湿器には 5 リットルの水が入っています。
時刻 7 : 水を追加する前は 2 リットル入っており、1 リットル追加して加湿器には 3 リットルの水が入っています。

時刻 7 に水を追加し終えたとき、加湿器に残っている水の量は 3 リットルです。よって答えは 3 です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 150 points

Problem Statement

There is one humidifier in the AtCoder company office. The current time is 0, and the humidifier has no water inside.

You will add water to this humidifier N times. The i-th addition of water (1 \leq i \leq N) takes place at time T_i, and you add V_i liters of water. It is guaranteed that T_i < T_{i+1} for all 1 \leq i \leq N-1.

However, the humidifier has a leak, and as long as there is water inside, the amount of water decreases by 1 liter per unit time.

Find the amount of water remaining in the humidifier immediately after you finish adding water at time T_N.

Constraints

1 \leq N \leq 100
1 \leq T_i \leq 100 (1 \leq i \leq N)
1 \leq V_i \leq 100 (1 \leq i \leq N)
T_i < T_{i+1} (1 \leq i \leq N-1)
All input values are integers.

Input

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

N
T_1 V_1
T_2 V_2
\vdots
T_N V_N

Output

Print the answer.

Sample Input 1

Sample Output 1

At each point in time, water is added as follows:

Time 1: Before adding, the humidifier has 0 liters. After adding 3 liters, it has 3 liters.
Time 3: Before adding, it has 1 liter. After adding 1 liter, it has 2 liters total.
Time 4: Before adding, it has 1 liter. After adding 4 liters, it has 5 liters total.
Time 7: Before adding, it has 2 liters. After adding 1 liter, it has 3 liters total.

After finishing the addition at time 7, the humidifier contains 3 liters. Thus, the answer is 3.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

C - AtCoder Amusement Park

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 遊園地には K 人乗りのアトラクションがあります。現在、このアトラクションの待機列には N グループが並んでいます。

先頭から i 番目 (1\leq i\leq N) のグループは A _ i 人組です。すべての i (1\leq i\leq N) について、A _ i\leq K です。

高橋君はこのアトラクションのスタッフとして、並んでいるグループを次の手順に従って誘導します。

はじめ、アトラクションには誰も誘導されておらず、空席は K 個あります。

待機列に並んでいるグループがない場合、アトラクションをスタートさせ、誘導を終了する。
アトラクションの空席の数と待機列の先頭に並んでいるグループの人数を比較し、次のどちらかを行う。
- 待機列の先頭に並んでいるグループの人数よりアトラクションの空席の数のほうが少ない場合、アトラクションをスタートさせる。スタートしたのち、アトラクションの空席が K 個になる。
- そうでない場合、待機列の先頭に並んでいるグループを全員アトラクションへ誘導する。先頭のグループが待機列から取り出され、アトラクションの空席がグループの人数ぶんだけ減少する。
1 に戻る。

ただし、誘導を開始したあとに追加でグループが並ぶことはないとします。以上の条件のもとで、この手順が有限回で終了することが示せます。

高橋君が誘導を開始してから誘導を終了するまで、何回アトラクションをスタートさせるか求めてください。

制約

1\leq N\leq100
1\leq K\leq100
1\leq A _ i\leq K\ (1\leq i\leq N)
入力はすべて整数

入力

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

N K
A _ 1 A _ 2 \ldots A _ N

出力

答えを出力せよ。

入力例 1

7 6
2 5 1 4 1 2 3

出力例 1

はじめ、7 つのグループは以下のように並んでいます。

高橋君の誘導の様子の一部を以下の図に示します。

はじめ、先頭に並んでいるグループは 2 人のグループで、空席は 6 個です。よって、高橋君は先頭のグループをアトラクションに誘導し、空席は 4 個になります。
次に、先頭に並んでいるグループは 5 人のグループで、空席の個数 4 より多いため、アトラクションをスタートさせます。
空席が 6 個になったため、先頭のグループをアトラクションに誘導し、空席は 1 個になります。
次に先頭に並んでいるのは 1 人なので、アトラクションに誘導し、空席は 0 個になります。

すべての誘導が終了するまでに、高橋君は 4 回アトラクションをスタートさせることになります。よって、4 を出力してください。

入力例 2

7 10
1 10 1 10 1 10 1

出力例 2

入力例 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

出力例 3

Score: 200 points

Problem Statement

The AtCoder amusement park has an attraction that can accommodate K people. Now, there are N groups lined up in the queue for this attraction.

The i-th group from the front (1\leq i\leq N) consists of A_i people. For all i (1\leq i\leq N), it holds that A_i \leq K.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are K empty seats.

If there are no groups in the queue, start the attraction and end the guidance.
Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
- If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes K again.
- Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

1\leq N\leq 100
1\leq K\leq 100
1\leq A_i\leq K\ (1\leq i\leq N)
All input values are integers.

Input

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

N K
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

Initially, the group at the front has 2 people, and there are 6 empty seats. Thus, he guides the front group to the attraction, leaving 4 empty seats.
Next, the group at the front has 5 people, which is more than the 4 empty seats, so the attraction is started.
After the attraction is started, there are 6 empty seats again, so the front group is guided to the attraction, leaving 1 empty seat.
Next, the group at the front has 1 person, so they are guided to the attraction, leaving 0 empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

D - Digit Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 n の桁和を、 n を十進法で表したときの各桁の和と定めます。例えば 2026 の桁和は 2+0+2+6=10 です。

N 以下の正整数のうち、桁和が K であるものの個数を求めてください。

制約

1\leq N,K \leq 10^5
入力は全て整数

入力

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

N K

出力

答えを出力せよ。

入力例 1

30 4

出力例 1

30 以下の正整数のうち、桁和が 4 であるものは、4,13,22 の 3 個です。

入力例 2

2026 10

出力例 2

入力例 3

99999 45

出力例 3

Score : 200 points

Problem Statement

The digit sum of a positive integer n is defined as the sum of the digits when n is represented in decimal. For example, the digit sum of 2026 is 2+0+2+6=10.

Find the number of positive integers not exceeding N whose digit sum is K.

Constraints

1\leq N,K \leq 10^5
All input values are integers.

Input

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

N K

Output

Output the answer.

Sample Input 1

30 4

Sample Output 1

Among the positive integers not exceeding 30, there are three integers whose digit sum is 4: 4,13,22.

Sample Input 2

2026 10

Sample Output 2

Sample Input 3

99999 45

Sample Output 3

E - Centers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

1,2,\dots,N がちょうど 3 回ずつ現れる長さ 3N の数列 A=(A_1,A_2,\dots,A_{3N}) が与えられます。

i=1,2,\dots,N について、A の中にある i のうち真ん中にあるものの添字を f(i) と定めます。 1,2,\dots,N を f(i) の昇順に並べ替えてください。

f(i) の定義は厳密には以下の通りです。

A_j = i を満たす j が j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma) であるとする。このとき、f(i) = \beta である。

制約

1\leq N \leq 10^5
1 \leq A_j \leq N
i=1,2,\dots,N それぞれについて、A の中に i はちょうど 3 回現れる
入力は全て整数

入力

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

N
A_1 A_2 \dots A_{3N}

出力

1,2,\dots,N を f(i) の昇順に並べ替えてできる長さ N の数列を空白区切りで出力せよ。

入力例 1

3
1 1 3 2 3 2 2 3 1

出力例 1

1 3 2

A の中にある 1 は A_1,A_2,A_9 なので、f(1) = 2 です。
A の中にある 2 は A_4,A_6,A_7 なので、f(2) = 6 です。
A の中にある 3 は A_3,A_5,A_8 なので、f(3) = 5 です。

よって、f(1) < f(3) < f(2) であるため 1,3,2 の順に出力します。

入力例 2

1
1 1 1

出力例 2

入力例 3

4
2 3 4 3 4 1 3 1 1 4 2 2

出力例 3

3 4 1 2

Score : 250 points

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

1\leq N \leq 10^5
1 \leq A_j \leq N
i occurs in A exactly three times, for each i=1,2,\dots,N.
All input values are integers.

Input

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

N
A_1 A_2 \dots A_{3N}

Output

Print the sequence of length N obtained by sorting 1,2,\dots,N in ascending order of f(i), separated by spaces.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

Sample Input 3

4
2 3 4 3 4 1 3 1 1 4 2 2

Sample Output 3

3 4 1 2