In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
W urojonym świecie znajduje się prostokątna wyspa. Ma ona mil szerokości oraz mil długości i jest podzielona na kwadratowych pól. Niektóre pola są niezamieszkałe, a w pozostałych znajdują się wioski różnych istot: elfów, ludzi, krasnoludów oraz hobbitów. Mówimy, że dwie wioski sąsiadują ze sobą, jeśli pola, na których są położone, mają wspólny bok.
Ostatnimi czasy wioski sparaliżował strach przed Bajtozłem. Aby poczuć się bezpieczniej, każda z wiosek chce zawrzeć sojusze militarne z niektórymi ze swych sąsiadów. Sojusz zawierany jest zawsze pomiędzy dwoma sąsiadami i jest porozumieniem obustronnym.
Zależnie od rasy, mieszkańcy wioski nie będą czuli się bezpiecznie, jeśli ich wioska nie zawrze konkretnej konfiguracji sojuszy:
Innymi słowy, nie licząc ludzi, każda wioska potrzebuje konkretnej liczby sojuszników i nie przejmuje się tym, którzy z sąsiadów będą jej sojusznikami. Ludzie natomiast mają dodatkowe wymaganie: sojusznicy nie mogą znajdować się po przeciwległych stronach wioski.
Warunki te muszą być spełnione niezależnie od położenia wioski na mapie. Przykładowo, wioska krasnoludów potrzebuje trzech sojuszników. Jeśli jest położona na brzegu, oznacza to, że musi mieć sojusze ze wszystkimi trzema sąsiadami. Jeśli znajduje się w rogu wyspy, jej mieszkańcy nigdy nie będą czuli się bezpiecznie.
Masz dany opis wyspy. Twoim zadaniem jest ustalić, czy możliwe jest takie utworzenie sojuszy, aby wszyscy mieszkańcy wyspy czuli się bezpiecznie. Jeśli odpowiedź jest pozytywna, powinieneś także znaleźć jakąś poprawną konfigurację sojuszy. W przypadku wielu możliwych konfiguracji wybierz dowolną z nich.
Pierwszy wiersz wejścia zawiera dwie liczby i oznaczające wymiary wyspy. Kolejne wierszy zawiera opis wyspy. Każdy z wierszy zawiera pooddzielanych pojedynczymi odstępami liczb od 0 do 4:
We wszystkich testach zachodzi .
W testach wartych łącznie 55 punktów zachodzi . Wśród nich znajdują się testy warte łącznie 15 punktów, w których zachodzi .
Kolejna grupa testów warta 10 punktów zawiera mapy, w których występują wyłącznie pola niezamieszkałe oraz wioski ludzkie. (Te testy nie są zawarte w testach wartych 55 punktów, o których mowa wyżej).
Jeśli nie istnieje poprawne rozwiązanie, wypisz jeden wiersz z napisem "Impossible!" (bez cudzysłowów). W przeciwnym wypadku wypisz jedną z poprawnych map sojuszy w formacie opisanym poniżej.
Każde pole jest reprezentowane na wyjściu jako macierz znaków. Jeśli jest niezamieszkałe, odpowiadająca macierz powinna być wypełniona znakami '.' (kropka). W przeciwnym wypadku w środku powinien znaleźć się znak 'O' (wielka litera O) reprezentujący samą wioskę oraz znaki 'X' (wielka litera X) oznaczające konfigurację sojuszników. Pozostała część macierzy powinna być wypełniona znakami '.' (kropka).
Wszystkie możliwe konfiguracje sojuszników dla wiosek poszczególnych ras są przedstawione poniżej.
Dla danych wejściowych:
3 4 2 3 2 0 3 4 3 0 2 3 3 1
poprawną odpowiedzią jest:
............ .OXXOXXO.... .X..X..X.... .X..X..X.... .OXXOXXO.... .X..X..X.... .X..X..X.... .OXXOXXOXXO. ............
natomiast dla danych wejściowych:
1 2 2 1
poprawnym wynikiem jest:
Impossible!
Autor zadania: Marek Zeman.