Lustrzana pułapka
Limit pamięci: 16 MB
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 ).
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 ,
oznaczająca liczbę pułapek do rozpatrzenia. W wierszach opisane są pułapki,
po jednej w wierszu. Opis pułapki składa się z trzech liczb , oddzielonych
pojedynczymi odstępami. Lustrzana pułapka ma wymiary .
Wyjście
Twój program powinien wypisać dokładnie wierszy. W wierszu o numerze powinno
się znaleźć rozwiązanie dla pułapki o numerze : trzy
liczby całkowite , oddzielone pojedynczymi odstępami,
, , ,
.
Liczby te oznaczają, że w -tej pułapce laser powinien być skierowany na punkt o
współrzędnych .
Jeżeli istnieje wiele poprawnych wyników, Twój program powinien
wypisać dowolny z nich.
Przykład
Dla danych wejściowych:
2
5 6 7
5 6 6
poprawną odpowiedzią jest:
4 5 6
4 6 5
Autor zadania: Zbigniew Czech.