KOMM - Stacja telefoniczna
Stacja telefoniczna ma 2K wejść, tyle samo wyjść i P warstw komutatorów. Każda warstwa składa się z K komutatorów, które łączą parę linii wejściowych z parą linii wyjściowych. Każdy komutator może się znajdować w jednym z dwóch stanów: X lub =.
W stanie X komutator łączy linie wejściowe z liniami wyjściowymi „na krzyż”. W stanie = zaś równolegle.
Linie wejściowe oraz wyjściowe numerowane są od 1 do 2K.
Na wejściu każdy komutator ma dwie kolejne linie: pierwszy komutator ma linie 1 i 2, drugi 3 i 4 i tak dalej. Wyjścia z komutatorów mogą zostać podpięte do dowolnych linii.
Na rysunku przedstawiona jest trójwarstwowa stacja. Po lewe stronie są linie wejściowe, po prawej — wejściowe. Warstwy komutatorów zaznaczone są na szaro. Komutatory pierwszej warstwy mają odpowiednio stany X, =, X, =. Komutatory drugiej warstwy mają stany =, =, X, X. Stany komutatorów trzeciej warstwy to =, X, X, X. Takie ustawienie komutatorów realizuje połączenia 1-8, 2-1, 3-2, 4-7, 5-6, 6-4, 7-3, 8-5.
Napisz program, który na podstawie pożądanych połączeń określa stany wszystkich komutatorów tak, żeby stacja telefoniczna zrealizowała te połączenia.
Input
W pierwszej linijce wejście jest liczba testów. Dalej, dla każdego testu dane są w blokach: W pierwszej linijce bloku podane są dwie liczby naturalne: P — ilość warstw oraz K — połowa ilości wejść/wyjść. W następnej linijce podane są 2K liczb naturalnych A(1), A(2), ..., A(2K), określających pożądane połączenia: wejście i należy połączyć z wyjściem A(i), i=1,...2K. Kolejne P-1 linii stanowią opisanie poszczególnych warstw. Każda linia zawiera 2K liczb naturalnych: B(1), ... B(2K), co oznacza, że w tej warstwie przy stanie = wszystkich komutatorów wejście i zostanie połączone z wejściem B(i). W ostatniej warstwie wyjściami są linie wejściowe, które są numerowane od 1 do 2K i nie wymagają opisania. Ograniczenia: 0<P≤4, 0<K≤10.
Output
Na wyjściu dla każdego testu trzeba podać stany poszczególnych komutatorów. Każda warstwa w oddzielnej linijce. Jeżeli testowe zadanie nie ma rozwiązań, trzeba wyświetlić "noway" (bez cudzysłowu). Jeżeli zadanie ma wiele rozwiązań, należy wyświetlić tylko jedno.
Example
Pierwszy test ilustruje stację z rysunku.
Input: 2
3 4
8 1 2 7 6 4 3 5
1 5 3 7 2 6 4 8
1 3 2 4 5 7 6 8
3 4
8 1 2 7 6 4 3 5
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 Output: X=X=
==XX
=XXX
noway
Added by: | Aleksander Denisiuk |
Date: | 2014-02-06 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |