Hello! I was curious about the International Olympiad in Informatics and I found out it was first held in 1989 in Pravetz, Bulgaria. Looking at the problem given in the competition, I found it very interesting and challenging. Maybe you could help me with an idea for the solution or some code.
PROBLEM
Given 2*N boxes in line side by side (N<=5). Two adjacent boxes are empty, and the other boxes contain N-1 symbols "A" and N-1 symbols "B".
Example for N=5: | A | B | B | A | | | A | B | A | B |
Exchanging rule:
The content of any two adjacent non-empty boxes can be moved into the two empty ones, preserving their order.
Aim:
Obtain a configuration where all A's are placed to the left of all B's, no matter where the empty boxes are.
Problem:
Write a program that:
Models the exchanging of boxes, where the number of boxes and the initial state are to be input from the keyboard. Each exchange is input by the number (from 1 to N-1) of the first of the two neighboring boxes which are to be exchanged with the empty ones. The program must find the state of the boxes after the exchange and display it.
Given an initial state finds at least one exchanging plan, which reaches the aim (if there is such a plan). A plan includes the initial state and the intermediate states for each step.
Finds the minimal exchanging plan which reaches the aim.
