Polish version    English version  
  Historia OI -> VII OI 1999/2000 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Zasady organizacji
Wskazówki
Terminarz
Statystyki
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VII Olimpiada Informatyczna 1999/2000

Zadanie: TRO
Autor: Wojciech Rytter
Trójramienny dźwig

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.

Zadanie

Napisz program, który:

  • z pliku tekstowego TRO.IN wczyta charakterystykę dźwigu (liczby p i q) oraz liczbę wagonów do załadowania (n),
  • wygeneruje poprawny program dla dźwigu,
  • zapisze go do pliku tekstowego TRO.OUT.

Wejście

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.

Wyjście

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.

Przykład

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



Wersja do druku