AtCoder Daily Training EASY 2025/02/27 18:30start

A - Five Integers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

与えられる 5 つの整数 A, B, C, D, E の中に何種類の整数があるかを出力してください。

制約

0 \leq A, B, C, D, E \leq 100
入力はすべて整数

入力

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

A B C D E

出力

答えを出力せよ。

入力例 1

31 9 24 31 24

出力例 1

与えられる 5 つの整数 31, 9, 24, 31, 24 の中には、9, 24, 31 という 3 種類の整数があります。よって、3 を出力します。

入力例 2

0 0 0 0 0

出力例 2

Score : 100 points

Problem Statement

Print how many distinct integers there are in given five integers A, B, C, D, and E.

Constraints

0 \leq A, B, C, D, E \leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E

Output

Print the answer.

Sample Input 1

31 9 24 31 24

Sample Output 1

In the given five integers 31, 9, 24, 31, and 24, there are three distinct integers 9, 24, and 31. Thus, 3 should be printed.

Sample Input 2

0 0 0 0 0

Sample Output 2

B - Spoiler

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

英小文字と | のみからなる文字列 S が与えられます。S は | をちょうど 2 個含むことが保証されます。

2 つの | の間にある文字および | を S から削除した文字列を出力してください。

制約

S は英小文字および | のみからなる長さ 2 以上 100 以下の文字列
S は | をちょうど 2 個含む

入力

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

出力

答えを出力せよ。

入力例 1

atcoder|beginner|contest

出力例 1

atcodercontest

2 つの | に挟まれた文字を全て削除して出力してください。

入力例 2

|spoiler|

出力例 2

全ての文字が削除されることもあります。

入力例 3

||xyz

出力例 3

xyz

Score: 150 points

Problem Statement

You are given a string S consisting of lowercase English letters and |. S is guaranteed to contain exactly two |s.

Remove the characters between the two |s, including the |s themselves, and print the resulting string.

Constraints

S is a string of length between 2 and 100, inclusive, consisting of lowercase English letters and |.
S contains exactly two |s.

Input

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

Output

Print the answer.

Sample Input 1

atcoder|beginner|contest

Sample Output 1

atcodercontest

Remove all the characters between the two |s and print the result.

Sample Input 2

|spoiler|

Sample Output 2

It is possible that all characters are removed.

Sample Input 3

||xyz

Sample Output 3

xyz

C - Piano 3

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は、横一列に並んだ 100 個の鍵盤からなるピアノを持っています。このピアノの左から i 個目の鍵盤のことを鍵盤 i と呼びます。

高橋君は今から N 回にわたってこのピアノの鍵盤を一つずつ押すことでとある曲を演奏します。 i 回目に押す鍵盤は鍵盤 A_i であり、それを押す手は S_i= L のとき左手、S_i= R のとき右手です。

演奏を始める前、高橋君は両手をそれぞれ好きな鍵盤の上に置くことができ、この時点での疲労度は 0 です。演奏中、片方の手を鍵盤 x の上から鍵盤 y の上へと動かすと疲労度が |y-x| 増加します（逆に、手の移動以外で疲労度が増加することはありません）。なお、ある手である鍵盤を押すためには、その手がその鍵盤の上に置かれている必要があります。

演奏が終了した時点での疲労度は最小でいくつになるか求めてください。

制約

1\leq N \leq 100
1\leq A_i \leq 100
N,A_i は整数
S_i は L または R

入力

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

出力

演奏が終了した時点での疲労度の最小値を出力せよ。

入力例 1

4
3 L
6 R
9 L
1 R

出力例 1

例えば以下のように演奏することができます。

最初、左手を鍵盤 3 の上に、右手を鍵盤 6 の上に置いておく。
左手で鍵盤 3 を押す。
右手で鍵盤 6 を押す。
左手を鍵盤 3 の上から鍵盤 9 の上へと動かす。疲労度が |9-3|=6 増加する。
右手を鍵盤 6 の上から鍵盤 1 の上へと動かす。疲労度が |1-6|=5 増加する。
左手で鍵盤 9 を押す。
右手で鍵盤 1 を押す。

このとき、演奏が終了した時点での疲労度は 6+5=11 であり、これが最小です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 200 points

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

1 \leq N \leq 100
1 \leq A_i \leq 100
N and A_i are integers.
S_i is L or R.

Input

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

Output

Print the minimum fatigue level at the end of the performance.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

For example, the performance can be done as follows:

Initially, place the left hand on key 3 and the right hand on key 6.
Press key 3 with the left hand.
Press key 6 with the right hand.
Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
Press key 9 with the left hand.
Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

D - Mex

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N) が与えられます。

A_1,\ldots,A_N に含まれない最小の非負整数を求めてください。

制約

1 \leq N \leq 2000
0 \leq A_i \leq 2000
入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

8
0 3 2 6 2 1 0 0

出力例 1

非負整数は 0,1,2,3,4,\ldots と続きます。
0,1,2,3 は A に含まれ、4 は A に含まれないので、答えは 4 です。

入力例 2

3
2000 2000 2000

出力例 2

Score : 200 points

Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

1 \leq N \leq 2000
0 \leq A_i \leq 2000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.

Sample Input 2

3
2000 2000 2000

Sample Output 2

E - Balls and Bag Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

空の袋があります。クエリが Q 個与えられるので、順番に処理してください。

クエリは次の 3 種類です。

1 x : 整数 x が書かれたボールを 1 つ袋に入れる。
2 x : 整数 x が書かれたボールを 1 つ袋の中から取り出して外に捨てる。このクエリが与えられるとき、袋の中に整数 x が書かれたボールが存在することが保証される。
3 : 袋の中にあるボールに書かれている整数の種類数を出力する。

制約

1 \leq Q \leq 2 \times 10^{5}
1 \leq x \leq 10^{6}
2 種類目のクエリが与えられるとき、袋の中に整数 x が書かれたボールが存在する。
3 種類目のクエリが 1 つ以上存在する。
入力はすべて整数

入力

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

i 番目のクエリ \text{query}_i は以下の 3 つの形式のいずれかで与えられる。

1 x

2 x

出力

3 種類目のクエリが K 個あるとき、K 行出力せよ。 i 行目(1 \leq i \leq K) では、i 番目の 3 種類目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

3
2
3

はじめ、袋の中は空です。

1 番目のクエリ 1 3 で袋の中に 3 が書かれたボールが 1 つ入ります。

2 番目のクエリ 1 1 で袋の中に 1 が書かれたボールが 1 つ入ります。

3 番目のクエリ 1 4 で袋の中に 4 が書かれたボールが 1 つ入ります。

4 番目のクエリ 3 で袋の中に 1, 3, 4 の 3 種類のボールが入っているため、3 を出力します。

5 番目のクエリ 2 1 で袋の中から 1 が書かれたボールを 1 つ取り出します。

6 番目のクエリ 3 で袋の中に 3, 4 の 2 種類のボールが入っているため、2 を出力します。

7 番目のクエリ 1 5 で袋の中に 5 が書かれたボールが 1 つ入ります。

8 番目のクエリ 3 で袋の中に 3, 4, 5 の 3 種類のボールが入っているため、3 を出力します。

入力例 2

出力例 2

1
1

Score : 300 points

Problem Statement

You have an empty bag. You are given Q queries, which must be processed in order.

There are three types of queries.

1 x : Put one ball with the integer x written on it into the bag.
2 x : Remove one ball with the integer x written on it from the bag and discard it. It is guaranteed that the bag has a ball with the integer x written on it when this query is given.
3 : Print the number of different integers written on the balls in the bag.

Constraints

1 \leq Q \leq 2 \times 10^{5}
1 \leq x \leq 10^{6}
When a query of the second type is given, the bag has a ball with the integer x written on it.
There is at least one query of the third type.
All input values are integers.

Input

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

The i-th query \text{query}_i is given in one of the following three formats:

1 x

2 x

Output

If there are K queries of the third type, print K lines. The i-th line (1 \leq i \leq K) should contain the answer to the i-th query of the third type.

Sample Input 1

Sample Output 1

3
2
3

Initially, the bag is empty.

For the first query 1 3, a ball with the integer 3 written on it enters the bag.

For the second query 1 1, a ball with the integer 1 written on it enters the bag.

For the third query 1 4, a ball with the integer 4 written on it enters the bag.

For the fourth query 3, the bag has balls with the integers 1, 3, 4, so print 3.

For the fifth query 2 1, a ball with the integer 1 written on it is removed from the bag.

For the sixth query 3, the bag has balls with the integers 3, 4, so print 2.

For the seventh query 1 5, a ball with the integer 5 written on it enters the bag.

For the eighth query 3, the bag has balls with the integers 3, 4, 5, so print 3.

Sample Input 2

Sample Output 2

1
1