Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
Slovak University of Technology
Masaryk University
acm
cz
acm
cz
CTU Open Contest 2007
Railway Transportation
railway.c, railway.C, railway.p, railway.java
ACM has created a new series of huge billboards. Now, they have to be transported using a train.
Unfortunately, the carriages of the train get somehow mixed, but ACM wants the billboards to
be delivered in an appropriate order.
13524
In a small example, we have 5 carriages approaching a railroad station with 3 parallel tracks.
Each carriage may enter any track, but once it is there, it cannot go back anymore. At the other
end, the tracks are merged back to a single railroad and cannot go back, again. We want the
carriages to leave their tracks in the correct order.
Possible solution is illustrated in the second figure. We may send carriage 4 to the first track,
then the carriage number 2 to the second one, number 5 to the first, number 3 to the second,
and finally, number 1 to the third track, which may immediately leave it to its correct position.
The other carriages will follow as needed.
4
2
5
3
1
Your task is to write a program that sends carriages to correct tracks and merges them at the
other end. You may assume that the tracks are long enough to hold any number of carriages.
Input Specification
The input consists of several scenarios, each of them described on two lines. End of the input is
signalized by two zeros.
The first line of each scenario contains two positive integers N and M , separated with a space,
N . 200000, M . 200000. N is the number of carriages, M is the number of tracks.
The second line will contain N non-negative integers representing carriages and their intended
order on the other end of the station. Some carriages may have identical numbers, in such a case,
their mutual order is not significant.