![]() |
||
Wojciech Rytter (treść, opracowanie) Tomasz Waleń (program wzorcowy) Trójramienny dźwig 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 ZadanieNapisz program, który:
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 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,
PrzykładDla pliku wejściowego TRO.IN2 3 10poprawną odpowiedzią jest plik wyjściowy TRO.OUT 4 1 3 6 2 4 7 5 8 10 9 11 14 Rozwiązanie
Opis algorytmuRozwiązanie polega na wykonywaniu tak długo jak to możliwe, ruchów typu 1, a gdy to nie jest możliwe ruchu typu 2. Okazuje się, że takie rozwiązanie zawsze generuje prawidłowy program.
Rys. 1. Przykładowa historia działania dźwigu trójramiennego. W każde pole wpisany jest kolejny numer ruchu, w którym to pole zostaje zajęte. Jedynie 7-my ruch jest typu 2. ![]()
Dowód poprawnościZałóżmy, że dla pewnego wagonu i=s po raz pierwszy nie można wykonać żadnego z ruchów. Łatwo zauważyć, że wagon i+p+q jest wolny. Również s jest wolny, natomiast s+p, s+q są zajęte, ponieważ nie można wykonać ruchu. Wagon s+q został zajęty w czasie wykonywania ruchu typu 2 dla pozycji j =s-p. Ale z tego wynika, że w momencie wykonywania ruchu dla i=j wolne były i, j+p, j+p+q, zatem można było wykonać ruch typu 1, który ma priorytet i zająć pozycje j, s, s+q. Pozycja s nie może być zatem wolna - sprzeczność. ObserwacjaMożna się zastanowić nad podobnym problem dla dźwigu czteroramiennego. Jest to trudne zadanie, ponieważ najpierw dla danego n trzeba sprawdzić, czy w ogóle istnieje odpowiedni program dźwigu - nie każdy ciąg kolejnych n liczb da się wtedy "pokryć". Na przykład nie ma pokrycia dla n=3 i dźwigu o charakterystyce (1, 2, 1), tzn. takiego który zapełnia wagony i, i+1, i+3, i+4. TestyDo sprawdzania rozwiązań zawodników użyto 24 testów, których charakterystyki znajdują się poniżej. ![]() Następujące testy zostały zgrupowane: (1,2 i 3), (4,5 i 6), (7,8 i 9), (10 i 11), (12 i 13), (14 i 15), (16 i 17), (18 i 19), (20 i 21), (22 i 23). |