AtCoder Daily Training MEDIUM 2025/04/29 15:30start

C - A Reverse

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 L,R と、英小文字のみからなる文字列 S が与えられます。
S の L 文字目から R 文字目までの部分を反転した(すなわち、 L 文字目から R 文字目までの文字の並びを逆にした)文字列を出力してください。

制約

S は英小文字のみからなる。
1 \le |S| \le 10^5 (|S| は S の長さ)
L,R は整数
1 \le L \le R \le |S|

入力

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

L R
S

出力

問題文の指示通り出力せよ。

入力例 1

3 7
abcdefgh

出力例 1

abgfedch

abcdefgh の 3 文字目から 7 文字目までの部分を反転すると、 abgfedch となります。

入力例 2

1 7
reviver

出力例 2

reviver

操作を行った結果が元の文字列と同一であることもあります。

入力例 3

4 13
merrychristmas

出力例 3

meramtsirhcyrs

Score : 200 points

Problem Statement

You are given integers L, R, and a string S consisting of lowercase English letters.
Print this string after reversing (the order of) the L-th through R-th characters.

Constraints

S consists of lowercase English letters.
1 \le |S| \le 10^5 (|S| is the length of S.)
L and R are integers.
1 \le L \le R \le |S|

Input

Input is given from Standard Input in the following format:

L R
S

Output

Print the specified string.

Sample Input 1

3 7
abcdefgh

Sample Output 1

abgfedch

After reversing the 3-rd through 7-th characters of abcdefgh, we have abgfedch.

Sample Input 2

1 7
reviver

Sample Output 2

reviver

The operation may result in the same string as the original.

Sample Input 3

4 13
merrychristmas

Sample Output 3

meramtsirhcyrs

D - Card Pile

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 0 の書かれたカードが 100 枚積み重なったカードの山があります。

Q 個のクエリを処理してください。それぞれのクエリは以下のいずれかです。

タイプ 1 : 整数 x の書かれたカードを 1 枚カードの山の一番上に積み重ねる。
タイプ 2 : カードの山の一番上のカードを取り除き、取り除いたカードに書かれている整数を出力する。ここで、本問題の制約下では必ず山にカードが存在する。

制約

1\le Q\le 100
1\le x\le 100
タイプ 2 のクエリが 1 つ以上存在する。
入力される値は全て整数

入力

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

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

i 番目のクエリ \text{query}_i では、まずクエリのタイプ c_i （1,2 のいずれか）が与えられる。 c_i=1 の場合はさらに整数 x が追加で与えられる。

すなわち、各クエリは以下に示す 2 つの形式のいずれかである。

1 x

出力

c_i=2 を満たすクエリの回数を q として、 q 行出力せよ。

j (1\le j\le q) 行目では j 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

出力例 1

各クエリを処理した後の山は順に以下のようになります：

カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 0 であるため、 0 を出力する。
- カードの山は 0 の書かれたカードが 99 枚となる。
4 が書かれたカードを山の上に追加する。
- カードの山は上から順に 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
3 が書かれたカードを山の上に追加する。
- カードの山は上から順に 3 の書かれたカードが 1 枚、 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 3 であるため、 3 を出力する。
- カードの山は上から順に 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 4 であるため、 4 を出力する。
- カードの山は 0 の書かれたカードが 99 枚となる。
カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 0 であるため、 0 を出力する。
- カードの山は 0 の書かれたカードが 98 枚となる。

入力例 2

出力例 2

Score : 200 points

Problem Statement

There is a stack of 100 cards, each labeled with the integer 0.

Process Q queries. Each query is of one of the following:

Type 1: Place a card labeled with an integer x on top of the stack.
Type 2: Remove the top card of the stack and output the integer written on that removed card. Under the constraints of this problem, the stack always has at least one card.

Constraints

1 \le Q \le 100
1 \le x \le 100
There is at least one query of type 2.
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 starts with the query type c_i (1 or 2), followed by the integer x if c_i=1.

That is, each query is in one of the following two formats:

1 x

Output

Let q be the number of queries with c_i=2. Print q lines.

The j-th line (1 \le j \le q) should contain the answer to the j-th such query.

Sample Input 1

Sample Output 1

After processing each query, the stack is as follows:

Remove the top card of the stack. The integer on the removed card is 0, so output 0.
- The stack then has 99 cards labeled with 0.
Add a card labeled 4 on top.
- The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
Add a card labeled 3 on top.
- The stack then has 1 card labeled 3, 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
Remove the top card. The integer on that card is 3, so output 3.
- The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
Remove the top card. The integer on that card is 4, so output 4.
- The stack then has 99 cards labeled 0.
Remove the top card. The integer on that card is 0, so output 0.
- The stack then has 98 cards labeled 0.

Sample Input 2

Sample Output 2

E - Merge the balls

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

空の列と、N 個のボールがあります。i 個目 (1\leq i\leq N) のボールの大きさは 2^{A_i} です。

これから N 回の操作を行います。
i 回目の操作では、i 個目のボールを列の一番右に付け加えた後、次の手順を繰り返します。

列にあるボールが 1 つ以下ならば操作を終了する。
列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 異なる ならば操作を終了する。
列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 等しい ならば、2 つのボールを取り除き、「取り除かれた 2 つのボールの大きさの和」の大きさのボール 1 つを列の一番右に付け加える。その後、1. に戻り、手順を繰り返す。

N 回の操作の後で、列にあるボールの数を求めてください。

制約

1\leq N \leq 2\times 10^5
0\leq A_i\leq 10^9
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

N 回の操作の後で、列にあるボールの数を出力せよ。

入力例 1

7
2 1 1 3 5 3 3

出力例 1

操作は次のように行われます。

1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^2 です。
2 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^2, 2^1 です。
3 回目の操作の後、列にあるボールは 1 つで、大きさは 2^3 です。これは次のようにして得ることができます。
- 3 回目の操作において 3 個目のボールを付け加えたとき、列にあるボールの大きさは順に 2^2,2^1,2^1 となります。
- 右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^1+2^1=2^2 のボールが追加されます。このとき、列にあるボールの大きさは 2^2, 2^2 となります。
- さらに、再び右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^2+2^2=2^3 のボールが追加され、列にあるボールの大きさは 2^3 となります。
4 回目の操作の後、列にあるボールは 1 つで、大きさは 2^4 です。
5 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^4, 2^5 です。
6 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^3 です。
7 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^4 です。

よって、最後に列にあるボールの数である 3 を出力します。

入力例 2

5
0 0 0 1 2

出力例 2

操作は次のように行われます。

1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^0 です。
2 回目の操作の後、列にあるボールは 1 つで、大きさは 2^1 です。
3 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^1, 2^0 です。
4 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^1, 2^0, 2^1 です。
5 回目の操作の後、列にあるボールは 4 つで、大きさは順に 2^1, 2^0, 2^1, 2^2 です。

よって、最後に列にあるボールの数である 4 を出力します。

Score: 250 points

Problem Statement

You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.

You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:

If the sequence has one or fewer balls, end the operation.
If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the N operations.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9
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

Output

Print the number of balls in the sequence after the N operations.

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

The operations proceed as follows:

After the first operation, the sequence has one ball, of size 2^2.
After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
- When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
- The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
- Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
After the fourth operation, the sequence has one ball, of size 2^4.
After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.

Therefore, you should print 3, the final number of balls in the sequence.

Sample Input 2

5
0 0 0 1 2

Sample Output 2

The operations proceed as follows:

After the first operation, the sequence has one ball, of size 2^0.
After the second operation, the sequence has one ball, of size 2^1.
After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.

Therefore, you should print 4, the final number of balls in the sequence.

F - Select Mul

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

整数 N が与えられます。N の各桁の数字を取り出して並べ（並べる順序は好きに変えてよい）、2 つの正整数に分離することを考えましょう。

例えば、123 という整数に対しては以下の 6 通りの分離の仕方が考えられます。

12 と 3
21 と 3
13 と 2
31 と 2
23 と 1
32 と 1

なお、ここで分離されたあとの 2 整数に leading zero が含まれていてはなりません。例えば、101 という整数を 1 と 01 の 2 つに分離することはできません。また上述の「正整数に分離する」という条件より、101 を 11 と 0 の 2 つに分離することもできません。

適切に N を分離したとき、分離後の 2 数の積の最大値はいくらになりますか？

制約

N は 1 以上 10^9 以下の整数
N には 0 でない桁が 2 つ以上含まれる

入力

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

出力

分離後の 2 数の積の最大値を出力せよ。

入力例 1

出力例 1

問題文中にある通り、以下の 6 通りの分離の仕方が考えられます。

12 と 3
21 と 3
13 と 2
31 と 2
23 と 1
32 と 1

積はそれぞれ 36, 63, 26, 62, 23, 32 であり、この中の最大値は 63 です。

入力例 2

出力例 2

考えられる分離の仕方は以下の 2 通りです。

100 と 1
10 と 10

いずれの場合にも積は 100 となります。

入力例 3

998244353

出力例 3

939337176

Score : 300 points

Problem Statement

You are given an integer N. Consider permuting the digits in N and separate them into two positive integers.

For example, for the integer 123, there are six ways to separate it, as follows:

12 and 3,
21 and 3,
13 and 2,
31 and 2,
23 and 1,
32 and 1.

Here, the two integers after separation must not contain leading zeros. For example, it is not allowed to separate the integer 101 into 1 and 01. Additionally, since the resulting integers must be positive, it is not allowed to separate 101 into 11 and 0, either.

What is the maximum possible product of the two resulting integers, obtained by the optimal separation?

Constraints

N is an integer between 1 and 10^9 (inclusive).
N contains two or more digits that are not 0.

Input

Input is given from Standard Input in the following format:

Output

Print the maximum possible product of the two integers after separation.

Sample Input 1

Sample Output 1

As described in Problem Statement, there are six ways to separate it:

12 and 3,
21 and 3,
13 and 2,
31 and 2,
23 and 1,
32 and 1.

The products of these pairs, in this order, are 36, 63, 26, 62, 23, 32, with 63 being the maximum.

Sample Input 2

Sample Output 2

There are two ways to separate it:

100 and 1,
10 and 10.

In either case, the product is 100.

Sample Input 3

998244353

Sample Output 3

939337176

G - Sequence Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

空の数列 A があります。
クエリが Q 個与えられるので、与えられた順番に処理してください。
クエリは次の 3 種類のいずれかです。

1 x ： A に x を追加する。
2 x k ： A の x 以下の要素のうち、大きい方から k 番目の値を出力する。(k は \bf{5} 以下)
ただし、A に x 以下の要素が k 個以上存在しないときは -1 と出力する。
3 x k ： A の x 以上の要素のうち、小さい方から k 番目の値を出力する。(k は \bf{5} 以下)
ただし、A に x 以上の要素が k 個以上存在しないときは -1 と出力する。

制約

1\leq Q \leq 2\times 10^5
1\leq x\leq 10^{18}
1\leq k\leq 5
入力は全て整数である

入力

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

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

i 番目のクエリ \text{query}_i では、まずクエリの種類 c_i (1,2,3 のいずれか) が与えられる。
c_i=1 の場合は x が追加で与えられ、c_i=2,3 の場合は x,k が追加で与えられる。

すなわち、各クエリは以下に示す 3 つの形式のいずれかである。

1 x

2 x k

3 x k

出力

c_i=2,3 を満たすクエリの個数を q として q 行出力せよ。
j(1\leq j\leq q) 行目では j 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

出力例 1

\text{query}_{1,2,3,4} が終了した段階で、A=(20,10,30,20) となっています。

\text{query}_{5,6,7} について、A の 15 以上の要素は (20,30,20) です。
このうち小さい方から 1 番目の値は 20 、2 番目の値は 20 、3 番目の値は 30 です。

Score : 400 points

Problem Statement

We have an empty sequence A.
Given Q queries, process them in order.
Each query is of one of the following three types.

1 x : Insert x to A.
2 x k : Among the elements of A that are less than or equal to x, print the k-th largest value. (k is no more than \bf{5})
If there are less than k elements of A that are less than or equal to x, then print -1.
3 x k : Among the elements of A that are greater than or equal to x, print the k-th smallest value. (k is no more than \bf{5})
If there are less than k elements of A that are greater than or equal to x, then print -1.

Constraints

1\leq Q \leq 2\times 10^5
1\leq x\leq 10^{18}
1\leq k\leq 5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

In the i-th query \text{query}_i, the type of query c_i (which is either 1, 2, or 3) is given first.
If c_i=1, then x is additionally given; if c_i=2, 3, then x and k are additionally given.

In other words, each query is given in one of the following three formats:

1 x

2 x k

3 x k

Output

Print q lines, where q is the number of queries such that c_i=2,3.
The j-th line (1\leq j\leq q) should contain the answer for the j-th such query.

Sample Input 1

Sample Output 1

After \text{query}_{1,2,3,4} have been processed, we have A=(20,10,30,20).

For \text{query}_{5,6,7}, the elements of A greater than or equal to 15 are (20,30,20).
The 1-st smallest value of them is 20; the 2-nd is 20; the 3-rd is 30.