VII Olimpiada Informatyczna 1999/2000
|
Zadanie: TRO
|
Autor: Wojciech Rytter
|
Zawody II stopnia, dzień pierwszy | 9 lutego 2000 |
Plik źródłowy: | TRO.??? (np. pas, c, cpp) |
Plik wykonywalny: | TRO.exe |
Plik wejściowy: | TRO.in |
Plik wyjściowy: | TRO.out |
Trójramienny dźwig ustawia kontenery na wagonach kolejowych. Wagony są ponumerowane kolejno 1, 2, ... . Na każdym wagonie można postawić co najwyżej jeden kontener. W jednym ruchu dźwig pobiera ze składowiska trzy kontenery i ustawia je na wagonach o numerach i, i+p oraz i+p+q, albo na wagonach o numerach i, i+q oraz i+p+q (dla pewnych stałych p,q>=1). Dźwig trzeba zaprogramować tak, żeby załadował kontenerami pierwsze n wagonów pociągu (pociąg ma n+p+q wagonów). Program składa się z ciągu instrukcji. Każda z instrukcji opisuje jeden ruch dźwigu. Instrukcja programu ma postać trójki (x,y,z), gdzie 1 < x < y < z < n+p+q, i określa numery wagonów, na które dźwig ma ustawić kontenery. Jeżeli po wykonaniu programu na każdym spośród n pierwszych wagonów pociągu znajduje się dokładnie jeden kontener, to mówimy, że program jest poprawny.
Napisz program, który:
W pierwszym i jedynym wierszu pliku tekstowego TRO.IN znajdują się dokładnie trzy dodatnie liczby całkowite pooddzielane pojedynczymi odstępami. Są to odpowiednio: liczby p i q określające parametry dźwigu oraz liczba n, będąca liczbą początkowych wagonów pociągu do załadowania. Liczby te spełniają nierówności 1 <= n <= 300000, 2 <= p+q <= 60000.
W pierwszym wierszu pliku tekstowego TRO.OUT powinna znajdować się dokładnie jedna liczba całkowita m będąca liczbą instrukcji w wygenerowanym programie. W każdym z kolejnych m wierszy powinny znajdować się dokładnie trzy liczby naturalne x, y, z pooddzielane pojedynczymi odstępami, 1 <= x < y < z <= n+p+q, x <= n, y należy do {x+p, x+q}, z = x+p+q. Są to numery wagonów, na które dźwig ma położyć kontenery w kolejnym ruchu.
Dla pliku wejściowego TRO.IN
2 3 10
poprawną odpowiedzią jest plik wyjściowy TRO.OUT
4 1 3 6 2 4 7 5 8 10 9 11 14