Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 72. (May 2012)

S. 72. Pieces of baggage of airport passengers who just landed are reloaded several times and put onto conveyor belts. However, different pieces of baggage of a given passenger may not be put adjacent to one another on the belt, which is undesirable: passengers would like to see their baggage arriving in one group. Your task is to put the different pieces of baggage of each passenger adjacent to one another on the belt such that the total distance of moving those pieces is minimal.

The conveyor belt is divided into segments of equal length. A segment is either empty or carries exactly one piece of baggage. (The length of a segment was determined in such a way that it can carry any type of luggage.) An airplane carries at most 40 people, and each person can carry at most 40 pieces of luggage. The conveyor belt for a given airplane has 1000 segments. The movement distance of a piece is defined as the difference between the position of the final segment and the initial segment of that piece. In the example, the piece denoted by ``t'' in the 9th position is moved into the 5th position, hence we had a movement distance equal to 4.

Your program should read the standard input: the first line of the input contains the length of the belt, while the second line contains the description of the pieces of baggage on the segments. Your program should rearrange the content of the belt with the minimal movement distance according to the requirement above. Your program should write the required total number of movements in the first line of the standard input, while the second line should contain the rearranged belt. Empty segments on the belt are denoted by dashes (-), while pieces of luggage of a given passenger are denoted by lowercase letters of the English alphabet. The input and output describe the part of the belt carrying pieces.

In the example, ``Példa bemenet'' is the sample input, while ``Példa kimenet'' is the corresponding output.

The source code (s72.pas, s72.cpp, ...) without the .exe or any other auxiliary files generated by the compiler should be submitted in a compressed file, also containing a short documentation (s72.txt, s72.pdf, ...) with a brief description of your solution and the name of the developer environment to use for compiling.

(10 pont)

Deadline expired on June 11, 2012.


3 students sent a solution.
5 points:1 student.
3 points:1 student.
2 points:1 student.

Problems in Information Technology of KöMaL, May 2012