DMOPC '18 Contest 3 P5 - Bob and Physics Class

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Bob has painstakingly written N pages of solutions for his physics homework. Each page is labelled from 1 to N. He has kept them in a pile, but being very disorganized, he ordered them randomly. In particular, the i^\text{th} page from the top is page P_i. Now that it's time to hand it in, he has to sort the pile!

Bob takes the top page of the first pile and creates a new pile with it. He then takes the new top page of the first pile and chooses to either place it at the top of the second pile or the bottom. He keeps doing this until all the pages are now in the second pile. Bob defines this series of operations as a single restacking. He performs this restacking with the new pile until he has a sorted pile of the N pages.

Given the original pile, can you help Bob sort his physics homework? Bob is busy with other homework, so he asks that your sort takes at most K restackings.

Constraints

For all 1 \le i \le N, 1 \le P_i \le N
Each number from 1 to N will appear exactly once.

Subtask 1 [10%]

2 \le N \le 1\,000
K=2\,000

Subtask 2 [10%]

2 \le N \le 1\,000
K=1\,000

Subtask 3 [80%]

2 \le N \le 100\,000
K=20

Input Specification

The first line will contain two space-separated integers, N and K.
The next line will contain N space-separated integers, P_1, P_2, \dots, P_N.

Output Specification

On the first line, output a single integer J, denoting the number of restackings you use. J must be between 0 and K inclusive.
On the next J lines, output a string of N-1 characters representing instructions for restacking. Remember that the top page becomes the new pile, leaving N-1 pages in the original pile. The i^\text{th} character should be T to move the current top page to the top of the new pile, or B to move it to the bottom of the new pile.
If these specifications are not satisfied or if your instructions do not sort the pile, you will receive a Wrong Answer verdict.

Sample Input 1

8 2000
1 5 2 6 3 7 4 8

Sample Output 1

2
BTBTBTB
TTTBBBB

Explanation for Sample 1

After the first set of instructions, the pile becomes

4 3 2 1 5 6 7 8

After the second set of instructions, the pile becomes

1 2 3 4 5 6 7 8

So the pages have been sorted.

Sample Input 2

2 2000
1 2

Sample Output 2

0

Comments

There are no comments at the moment.