| Historia OI -> XII OI 2004/2005 |  |
Zadanie: Lustrzana pułapka
Lustrzana pułapka to prostopadłościan zbudowany z luster, których powierzchnie odbijające są skierowane do wnętrza prostopadłościanu. Dokładnie w środku prostopadłościanu zawieszony jest miniaturowy laser o rozmiarach punktu. Zadanie polega na takim skierowaniu lasera, aby jego promień przebył jak najdłuższą drogę i trafił w laser. Przy czym przez drogę rozumiemy sumę odległości, jaką przebył promień lasera w każdym z trzech kierunków równoległych do krawędzi luster (czyli mierzymy tzw. metryką miejską).
Wymiary lustrzanej pułapki są parzystymi liczbami całkowitymi. Krawędzie oraz wierzchołki, w których lustra stykają się ze sobą, nie odbijają promieni lasera. Wewnątrz pułapki określamy układ współrzędnych: osie układu są równoległe do krawędzi pułapki, a laser znajduje się w początku układu współrzędnych. Laser można skierować na dowolny punkt wewnątrz pułapki o współrzędnych całkowitych, włączając w to punkty na powierzchni luster (z wyjątkiem samego lasera, czyli punktu (0, 0, 0)).
Zadanie
Napisz program, który:- wczyta ze standardowego wejścia wymiary lustrzanej pułapki,
- wyznaczy kierunek takiego ustawienia lasera, że promień
wystrzelony przez laser:
- będzie odbijał się od luster, choć niekoniecznie od wszystkich,
- nie trafi w krawędź, ani w wierzchołek pułapki,
- trafi ponownie do lasera, choć być może z innego kierunku,
- przebędzie możliwie najdłuższą drogę (w sensie wyżej zdefiniowanej odległości).
- wypisze wynik na standardowe wyjście.
Wejście
Pojedynczy test składa się z wielu lustrzanych pułapek do przeanalizowania. W pierwszym wierszu wejścia podana jest jedna liczba całkowita 1 ≤ K ≤ 1000, oznaczająca liczbę pułapek do rozpatrzenia. W wierszach 2...K + 1 opisane są pułapki, po jednej w wierszu. Opis pułapki składa się z trzech liczb 5 ≤ x, y, z ≤ 1000, oddzielonych pojedynczymi odstępami. Lustrzana pułapka ma wymiary 2x×2y×2z.
Wyjście
Twój program powinien wypisać dokładnie K wierszy. W wierszu o numerze i powinno się znaleźć rozwiązanie dla pułapki o numerze i: trzy liczby całkowite kx, ky, kz, oddzielone pojedynczymi odstępami, - x ≤ kx ≤ x, - y ≤ ky ≤ y, - z ≤ kz ≤ z, (kx, ky, kz) <> (0, 0, 0). Liczby te oznaczają, że w i-tej pułapce laser powinien być skierowany na punkt o współrzędnych (kx, ky, kz).Jeżeli istnieje wiele poprawnych wyników, Twój program powinien wypisać dowolny z nich.
Wersja do druku