AtCoder Daily Training MEDIUM 2024/11/05 17:30start

C - qwerty

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 以上 26 以下の整数からなる長さ 26 の数列 P=(P_1,P_2, \ldots ,P_{26}) が与えられます。ここで、P の要素は相異なることが保証されます。

以下の条件を満たす長さ 26 の文字列 S を出力してください。

任意の i\, (1 \leq i \leq 26) について、S の i 文字目は辞書順で小さい方から P_i 番目の英小文字である。

制約

1 \leq P_i \leq 26
P_i \neq P_j (i \neq j)
入力は全て整数である。

入力

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

P_1 P_2 \ldots P_{26}

出力

文字列 S を出力せよ。

入力例 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

出力例 1

abcdefghijklmnopqrstuvwxyz

入力例 2

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

出力例 2

bacdefghijklmnopqrstuvwxyz

入力例 3

5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21

出力例 3

eklpyqragjdwtcbxzsnifvhmou

Score : 200 points

Problem Statement

You are given a sequence of 26 integers P=(P_1,P_2, \ldots ,P_{26}) consisting of integers from 1 through 26. It is guaranteed that all elements in P are distinct.

Print a string S of length 26 that satisfies the following condition.

For every i (1 \leq i \leq 26), the i-th character of S is the lowercase English letter that comes P_i-th in alphabetical order.

Constraints

1 \leq P_i \leq 26
P_i \neq P_j (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

P_1 P_2 \ldots P_{26}

Output

Print the string S.

Sample Input 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 1

abcdefghijklmnopqrstuvwxyz

Sample Input 2

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 2

bacdefghijklmnopqrstuvwxyz

Sample Input 3

5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21

Sample Output 3

eklpyqragjdwtcbxzsnifvhmou

D - 3^A

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 M が与えられます。以下の条件を全て満たす正整数 N と非負整数列 A=(A_1,A_2,\ldots,A_N) を一つ求めてください。

1\le N\le 20
0\le A_i\le 10 (1\le i\le N)
\displaystyle \sum_{i=1}^N 3^{A_i}=M

ただし、制約下では条件を満たす N と A の組が必ず存在することが証明できます。

制約

1\le M\le 10^5

入力

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

出力

以下の形式で条件を満たす N と A を出力せよ。

N
A_1 A_2 \ldots A_N

なお、条件を満たす N と A の組が複数存在する場合は、どれを出力しても正答となる。

入力例 1

出力例 1

2
1 1

N=2 、A=(1,1) とすると \displaystyle \sum_{i=1}^N 3^{A_i}=3+3=6 より全ての条件を満たします。

他に N=4 、 A=(0,0,1,0) なども条件を満たします。

入力例 2

出力例 2

4
2 0 2 4

入力例 3

出力例 3

20
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

1\le N\le 20 という制約に注意してください。

Score : 200 points

Problem Statement

You are given a positive integer M. Find a positive integer N and a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) that satisfy all of the following conditions:

1 \le N \le 20
0 \le A_i \le 10 (1 \le i \le N)
\displaystyle \sum_{i=1}^N 3^{A_i} = M

It can be proved that under the constraints, there always exists at least one such pair of N and A satisfying the conditions.

Constraints

1 \le M \le 10^5

Input

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

Output

Print N and A satisfying the conditions in the following format:

N
A_1 A_2 \ldots A_N

If there are multiple valid pairs of N and A, any of them is acceptable.

Sample Input 1

Sample Output 1

2
1 1

For example, with N=2 and A=(1,1), we have \displaystyle \sum_{i=1}^N 3^{A_i} = 3+3=6, satisfying all conditions.

Another example is N=4 and A=(0,0,1,0), which also satisfies the conditions.

Sample Input 2

Sample Output 2

4
2 0 2 4

Sample Input 3

Sample Output 3

20
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

Note the condition 1 \le N \le 20.

E - Reversible

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

ボールがいくつか刺さった棒が N 本あり、各ボールには英小文字が 1 個書かれています。

i = 1, 2, \ldots, N について、i 番目の棒に刺さった各ボールの英小文字は、文字列 S_i によって表されます。具体的には、i 番目の棒には文字列 S_i の長さ |S_i| に等しい個数のボールが刺さっており、刺さっているボールの英小文字を、棒のある端から順に並べたものは文字列 S_i と等しいです。

2 つの棒は、一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列と、もう一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列が一致するとき、同じ棒とみなされます。より形式的には、1 以上 N 以下の整数 i, j について、i 本目の棒と j 本目の棒は、S_i が S_j と一致するか、S_i が S_j を前後反転したものと一致するとき、かつそのときに限り、同じとみなされます。

N 本の棒の中に、何種類の異なる棒があるかを出力してください。

制約

N は整数
2 \leq N \leq 2 \times 10^5
S_i は英小文字のみからなる文字列
|S_i| \geq 1
\sum_{i = 1}^N |S_i| \leq 2 \times 10^5

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

6
a
abc
de
cba
de
abc

出力例 1

S_2 = abc が S_4 = cba を前後反転したものと一致するため、2 番目の棒と 4 番目の棒は同じとみなされます。
S_2 = abc が S_6 = abc と一致するため、2 番目の棒と 6 番目の棒は同じとみなされます。
S_3 = de が S_5 = de と一致するため、3 番目の棒と 5 番目の棒は同じとみなされます。

よって、6 本の棒の中に、1 本目の棒、2 本目の棒（ 4, 6 本目の棒と同じ）、3 本目の棒（ 5 本目の棒と同じ）の 3 種類の異なる棒があります。

Score : 300 points

Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

N is an integer.
2 \leq N \leq 2 \times 10^5
S_i is a string consisting of lowercase English letters.
|S_i| \geq 1
\sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).

F - String Delimiter

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字、,、" からなる長さ N の文字列 S が与えられます。S に含まれる " の個数は偶数であることが保証されています。

S に含まれる " の個数を 2K 個とすると、各 i=1,2,\ldots,K について 2i-1 番目の " から 2i 番目の " までの文字のことを 括られた文字 と呼びます。

あなたの仕事は、 S に含まれる , のうち、括られた文字 でないもの を . で置き換えて得られる文字列を答えることです。

制約

N は 1 以上 2\times 10^5 以下の整数
S は英小文字、,、" からなる長さ N の文字列
S に含まれる " の個数は偶数

入力

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

N
S

出力

答えを出力せよ。

入力例 1

8
"a,b"c,d

出力例 1

"a,b"c.d

S のうち "a,b" が括られた文字であり、c,d は括られた文字ではありません。

S に含まれる , のうち、括られた文字でないのは S の左から 7 番目の文字なので、7 番目の文字を . で置き換えたものが答えとなります。

入力例 2

5
,,,,,

出力例 2

.....

入力例 3

20
a,"t,"c,"o,"d,"e,"r,

出力例 3

a."t,"c."o,"d."e,"r.

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

N is an integer between 1 and 2\times 10^5, inclusive.
S is a string of length N consisting of lowercase English letters, ,, and ".
S contains an even number of ".

Input

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

N
S

Output

Print the answer.

Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.

Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.

G - A Piece of Cake

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

xy -平面上にいくつかのイチゴが載った長方形のケーキがあります。ケーキは、長方形領域 \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace をちょうど占めます。

ケーキには N 個のイチゴが載っており、i = 1, 2, \ldots, N について、i 番目のイチゴの座標は (p_i, q_i) です。 2 個以上のイチゴが同一の座標にあることはありません。

高橋君は、このケーキを包丁で下記の通りにいくつかのピースに切り分けます。

まず、ケーキを通る y 軸に並行な A 本の異なる直線、直線 x = a_1 、直線 x = a_2 、\ldots 、直線 x = a_A のそれぞれにそってケーキを切る。
次に、ケーキを通る x 軸に並行な B 本の異なる直線、直線 y = b_1 、直線 y = b_2 、\ldots 、直線 y = b_B のそれぞれにそってケーキを切る。

その結果、ケーキは (A+1)(B+1) 個の長方形のピースに分割されます。高橋君はそれらのうちのいずれか 1 個だけを選んで食べます。高橋君が選んだピースに載っているイチゴの個数としてあり得る最小値と最大値をそれぞれ出力してください。

ここで、最終的にピースの縁となる位置にはイチゴが存在しないことが保証されます。より形式的な説明は下記の制約を参照してください。

制約

3 \leq W, H \leq 10^9
1 \leq N \leq 2 \times 10^5
0 \lt p_i \lt W
0 \lt q_i \lt H
i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
1 \leq A, B \leq 2 \times 10^5
0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
入力はすべて整数

入力

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

W H
N
p_1 q_1
p_2 q_2
\vdots
p_N q_N
A
a_1 a_2 \ldots a_A
B
b_1 b_2 \ldots b_B

出力

高橋君が選んだピースに載っているイチゴの個数としてあり得る最小値 m と最大値 M をそれぞれ、下記の形式の通り空白区切りで出力せよ。

m M

入力例 1

出力例 1

0 2

全 9 個のピースの内訳は、イチゴが 0 個載ったものが 6 個、イチゴが 1 個載ったものが 1 個、イチゴが 2 個載ったものが 2 個です。よって、それらのうちのいずれか 1 個だけを選んで食べるとき、選んだピースに載っているイチゴの個数としてあり得る最小値は 0 、最大値は 2 です。

入力例 2

出力例 2

1 1

どのピースにもイチゴが 1 個載っています。

Score : 400 points

Problem Statement

There is a rectangular cake with some strawberries on the xy-plane. The cake occupies the rectangular area \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace.

There are N strawberries on the cake, and the coordinates of the i-th strawberry are (p_i, q_i) for i = 1, 2, \ldots, N. No two strawberries have the same coordinates.

Takahashi will cut the cake into several pieces with a knife, as follows.

First, cut the cake along A different lines parallel to the y-axis: lines x = a_1, x = a_2, \ldots, x = a_A.
Next, cut the cake along B different lines parallel to the x-axis: lines y = b_1, y = b_2, \ldots, y = b_B.

As a result, the cake will be divided into (A+1)(B+1) rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece.

Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below.

Constraints

3 \leq W, H \leq 10^9
1 \leq N \leq 2 \times 10^5
0 \lt p_i \lt W
0 \lt q_i \lt H
i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
1 \leq A, B \leq 2 \times 10^5
0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
All input values are integers.

Input

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

W H
N
p_1 q_1
p_2 q_2
\vdots
p_N q_N
A
a_1 a_2 \ldots a_A
B
b_1 b_2 \ldots b_B

Output

Print the minimum possible number of strawberries m and the maximum possible number M on the chosen piece in the following format, separated by a space.

m M

Sample Input 1

Sample Output 1

0 2

There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is 0, and the maximum possible number is 2.

Sample Input 2

Sample Output 2

1 1

Each piece has one strawberry on it.