Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

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, - xkxx, - ykyy, - zkzz, (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