Kindergarten Graduation
Time limit1sMemory limit128 MB
Given counts of girls and boys arranged around one empty gap, output a bounded sequence of slide/hop moves that swaps the two groups' positions.
- Level
Medium6 of 10
- Topics
- Simulation, Greedy, Implementation
- Solved
- No attempts yet
Problem
A kindergarten has an unusual graduation ceremony. At first, all girls stand on the left, all boys stand on the right, and one empty space separates the two groups. Using the four moves below, the children must end with all boys on the left, all girls on the right, and one empty space between the two groups again.
After every move, the previous position of the moving child becomes the new empty space. Given the number of girls nGirls and boys nBoys in each class, find a move sequence that transforms the starting arrangement into the target arrangement. The sequence must use at most nGirls * nBoys + nGirls + nBoys moves. This bound is enough because each girl-boy pair must pass each other once, and on average each child must move past the empty space once.
Input
The first line contains the number of problem instances N, where 1 <= N <= 1000. Each of the next N lines has the following form.
nGirls nBoys
nGirls: the number of girlsnBoys: the number of boys
A class has at least 1 child and at most 24 children.
Output
For each problem instance, output the number of moves on one line. On the following line, output the required move codes in order with no spaces.
Hint
The valid move sequence is not unique. Any sequence that reaches the target arrangement and satisfies the move limit is acceptable.