E - Sort

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

配点 : 300 点

問題文

(1,2,\ldots,N) の並び替えである数列 A=(A_1,\ldots,A_N) が与えられます。
次の操作を 0 回以上 N-1 回以下行うことで、A を (1,2,\ldots,N) にしてください。

  • 操作：1\leq i < j \leq N を満たす整数の組 (i,j) を自由に選ぶ。A の i 番目と j 番目の要素を入れ替える。

なお、制約の条件下で必ず A を (1,2,\ldots,N) にできることが証明できます。

制約

  • 2 \leq N \leq 2\times 10^5
  • (A_1,\ldots,A_N) は (1,2,\ldots,N) の並び替えである
  • 入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

操作回数を K として、K+1 行出力せよ。
1 行目には K を出力せよ。
l+1 行目 (1\leq l \leq K) には l 回目の操作で選ぶ整数 i,j を空白区切りで出力せよ。
問題文中の条件を満たすどのような出力も正解とみなされる。

入力例 1

5
3 4 1 2 5

出力例 1

2
1 3
2 4

操作により数列は次のように変化します。

  • 最初 A=(3,4,1,2,5) である。
  • 1 回目の操作で 1 番目の要素と 3 番目の要素を入れ替える。A=(1,4,3,2,5) になる。
  • 2 回目の操作で 2 番目の要素と 4 番目の要素を入れ替える。A=(1,2,3,4,5) になる。

この他、次のような出力でも正解とみなされます。

4
2 3
3 4
1 2
2 3

入力例 2

4
1 2 3 4

出力例 2

0

入力例 3

3
3 1 2

出力例 3

2
1 2
2 3

Score: 300 points

Problem Statement

You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:

  • Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.

It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).

Constraints

  • 2 \leq N \leq 2\times 10^5
  • (A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
  • All input values are integers.

Input

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

N
A_1 \ldots A_N

Output

Let K be the number of operations. Print K+1 lines.
The first line should contain K.
The (l+1)-th line (1\leq l \leq K) should contain the integers i and j chosen for the l-th operation, separated by a space.
Any output that satisfies the conditions in the problem statement will be considered correct.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

  • Initially, A=(3,4,1,2,5).
  • The first operation swaps the first and third elements, making A=(1,4,3,2,5).
  • The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).

Other outputs such as the following are also considered correct:

4
2 3
3 4
1 2
2 3

Sample Input 2

4
1 2 3 4

Sample Output 2

0

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3
F - Extra Character

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

配点 : 300 点

問題文

文字列 S,T が与えられます。S は英小文字からなり、T は S に英小文字を 1 つ挿入して作られたことがわかっています。

挿入された文字は T の先頭から何番目の文字であるか求めてください。
複数の候補が考えられる場合はいずれか 1 つを求めてください。

制約

  • 1 \leq |S| \leq 5\times 10^5
  • S は英小文字からなる
  • T は S に英小文字を 1 つ挿入して作られた文字列である

入力

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

S
T

出力

答えを出力せよ。なお、答えが複数考えられる場合はどれを出力しても正解となる。

入力例 1

atcoder
atcorder

出力例 1

5

T の先頭から 5 番目の文字 r が挿入された文字です。

入力例 2

million
milllion

出力例 2

5

T の先頭から 3,4,5 番目の文字のいずれかが挿入された文字です。
よって、3,4,5 のいずれかを出力すると正解となります。

入力例 3

vvwvw
vvvwvw

出力例 3

3

Score : 300 points

Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

  • 1 \leq |S| \leq 5\times 10^5
  • S consists of lowercase English letters.
  • T is obtained by inserting a lowercase English letter into S.

Input

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

S
T

Output

Print an integer i, representing that the inserted character is the i-th character from the beginning of T. If there are multiple possible answers, printing any of them is accepted.

Sample Input 1

atcoder
atcorder

Sample Output 1

5

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

5

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

3
G - LR insertion

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

配点 : 400 点

問題文

1 個の 0 のみからなる数列 A=(0) があります。
また、L と R のみからなる長さ N の文字列 S=s_1s_2\ldots s_N が与えられます。

i=1,2,\ldots ,N の順番で、次の操作を行います。

  • s_i が L のとき、A 内にある i-1 のすぐ左に i を挿入する
  • s_i が R のとき、A 内にある i-1 のすぐ右に i を挿入する

最終的な A を求めてください。

制約

  • 1\leq N \leq 5\times 10^5
  • N は整数である
  • |S| = N
  • s_i は L か R のいずれかである

入力

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

N
S

出力

最終的な A を空白区切りで出力せよ。

入力例 1

5
LRRLR

出力例 1

1 2 4 5 3 0

はじめ、A=(0) です。
s_1 が L なので、A=(1,0) となります。
s_2 が R なので、A=(1,2,0) となります。
s_3 が R なので、A=(1,2,3,0) となります。
s_4 が L なので、A=(1,2,4,3,0) となります。
s_5 が R なので、A=(1,2,4,5,3,0) となります。

入力例 2

7
LLLLLLL

出力例 2

7 6 5 4 3 2 1 0

Score : 400 points

Problem Statement

There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.

For each i=1, 2, \ldots, N in this order, the following will be done.

  • If s_i is L, insert i to the immediate left of i-1 in A.
  • If s_i is R, insert i to the immediate right of i-1 in A.

Find the final contents of A.

Constraints

  • 1\leq N \leq 5\times 10^5
  • N is an integer.
  • |S| = N
  • s_i is L or R.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the final contents of A, separated by spaces.

Sample Input 1

5
LRRLR

Sample Output 1

1 2 4 5 3 0

Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).

Sample Input 2

7
LLLLLLL

Sample Output 2

7 6 5 4 3 2 1 0
H - Swap

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

配点 : 500 点

問題文

K, E, Y のみからなる文字列 S が与えられます。

S の隣接する 2 文字を入れ替える操作を K 回まで行えるとき、作ることができる文字列は何種類ありますか？

制約

  • 2 \leq |S| \leq 30
  • 0 \leq K \leq 10^9
  • S は K, E, Y のみからなる

入力

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

S
K

出力

答えを出力せよ。

入力例 1

KEY
1

出力例 1

3

KEY に対して 1 回以下の操作を行うことで得られる文字列は KEY, EKY, KYE の 3 種類です。

入力例 2

KKEE
2

出力例 2

4

KKEE に対して 2 回以下の操作を行うことで得られる文字列は KKEE, KEKE, EKKE, KEEK の 4 種類です。

入力例 3

KKEEYY
1000000000

出力例 3

90

Score : 500 points

Problem Statement

Given is a string S consisting of K, E, Y.

How many strings are there that can be obtained with at most K swaps of two adjacent characters in S?

Constraints

  • 2 \leq |S| \leq 30
  • 0 \leq K \leq 10^9
  • S consists of K, E, Y.

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the answer.

Sample Input 1

KEY
1

Sample Output 1

3

With at most one swap, there are three strings that can be obtained: KEY, EKY, KYE.

Sample Input 2

KKEE
2

Sample Output 2

4

With at most two swaps, there are four strings that can be obtained: KKEE, KEKE, EKKE, KEEK.

Sample Input 3

KKEEYY
1000000000

Sample Output 3

90
I - Pre-order and In-order

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

配点 : 500 点

問題文

1, 2, \ldots, N と番号づけられた N 個の頂点を持つ二分木を考えます。 ここで、二分木とは各頂点が高々 2 個の子を持つ根付き木です。より具体的には、二分木の各頂点は高々 1 個の左の子と高々 1 個の右の子を持ちます。

頂点 1 を根とする二分木であって、下記の条件を満たすものが存在するかを判定し、存在する場合はその一例を示してください。

  • すべての頂点を深さ優先探索における行きがけ順（pre-order）で並べた列が (P_1, P_2, \ldots, P_N) である。
  • すべての頂点を深さ優先探索における通りがけ順（in-order）で並べた列が (I_1, I_2, \ldots, I_N) である。

制約

  • 2 \leq N \leq 2 \times 10^5
  • N は整数
  • (P_1, P_2, \ldots, P_N) は (1, 2, \ldots, N) の順列
  • (I_1, I_2, \ldots, I_N) は (1, 2, \ldots, N) の順列

入力

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

N
P_1 P_2 \ldots P_N
I_1 I_2 \ldots I_N

出力

問題文中の条件を満たすような頂点 1 を根とする二分木が存在しない場合は -1 を出力せよ。
存在する場合は、条件を満たす二分木の一例を下記の形式にしたがって N 行にわたって出力せよ。 すなわち、i = 1, 2, \ldots, N について、i 行目には頂点 i の左の子の番号 L_i と右の子の番号 R_i を出力せよ。 ただし、左の子（または右の子）を持たない場合は L_i（または R_i ）として 0 を出力せよ。
条件を満たすような頂点 1 を根とする二分木が複数存在する場合は、そのうちどれを出力しても正解となる。

L_1 R_1
L_2 R_2
\vdots
L_N R_N

入力例 1

6
1 3 5 6 4 2
3 5 1 4 6 2

出力例 1

3 6
0 0
0 5
0 0
0 0
4 2

次の画像に示す、頂点 1 を根とする二分木が問題文中の条件を満たします。

入力例 2

2
2 1
1 2

出力例 2

-1

問題文中の条件を満たすような頂点 1 を根とする二分木は存在しません。よって -1 を出力します。

Score : 500 points

Problem Statement

Consider a binary tree with N vertices numbered 1, 2, \ldots, N. Here, a binary tree is a rooted tree where each vertex has at most two children. Specifically, each vertex in a binary tree has at most one left child and at most one right child.

Determine whether there exists a binary tree rooted at Vertex 1 satisfying the conditions below, and present such a tree if it exists.

  • The depth-first traversal of the tree in pre-order is (P_1, P_2, \ldots, P_N).
  • The depth-first traversal of the tree in in-order is (I_1, I_2, \ldots, I_N).

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • N is an integer.
  • (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
  • (I_1, I_2, \ldots, I_N) is a permutation of (1, 2, \ldots, N).

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N
I_1 I_2 \ldots I_N

Output

If there is no binary tree rooted at Vertex 1 satisfying the conditions in Problem Statement, print -1.
Otherwise, print one such tree in N lines as follows. For each i = 1, 2, \ldots, N, the i-th line should contain L_i and R_i, the indices of the left and right children of Vertex i, respectively. Here, if Vertex i has no left (right) child, L_i (R_i) should be 0.
If there are multiple binary trees rooted at Vertex 1 satisfying the conditions, any of them will be accepted.

L_1 R_1
L_2 R_2
\vdots
L_N R_N

Sample Input 1

6
1 3 5 6 4 2
3 5 1 4 6 2

Sample Output 1

3 6
0 0
0 5
0 0
0 0
4 2

The binary tree rooted at Vertex 1 shown in the following image satisfies the conditions.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

No binary tree rooted at Vertex 1 satisfies the conditions, so -1 should be printed.