Problem description

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Kółko i krzyżyk (kolko-krzyzyk-2) Memory limit: 32 MB Time limit: 0.50 s Gry w kółko i krzyżyk nie trzeba nikomu przedstawiać. Jasio jest kiepski w tę grę, ciągle przegrywa ze swoim tatą. Zaczyna podejrzewać, że jego tata oszukuje (tzn. gra optymalnie). Chciałby również oszukiwać (grać optymalnie), ale nie potrafi. Pomóż mu! Przykładowa sytuacja w grze w kółko i krzyżyk wygląda tak: Pola planszy są numerowane od 1 do 9, z góry na dół, od lewej do prawej (na przykład środkowe górne pole ma numer 2). Jasio niestety zanim wpadł na genialny pomysł poproszenia Cię o pomoc wykonał już kilka posunięć. Chciałby wiedzieć czy pomimo optymalnej gry swojego taty może jeszcze wygrać, a jeśli nie – to czy może chociaż zremisować. Oczywiście przy tym należy wskazać wygrywające/remisujące ruchy. Grę zawsze rozpoczyna kółko. Jasio czasami gra jako kółko, a czasami jako krzyżyk, ale zawsze pyta Cię o pomoc wtedy, gdy jest jego ruch. Optymalna gra taty polega na tym, że jeśli może wygrać niezależnie od ruchów Jasia to zawsze wygra. Jeśli może chociaż zremisować – to zawsze zremisuje. Być może podczas pierwszych ruchów dał Jasiowi trochę “forów” i nie grał optymalnie, ale Jasio nie może zakładać, że tata dalej będzie mu odpuszczał w przyszłych ruchach. Napisz program, który: wczyta sytuację na planszy, wyznaczy czy Jasio może wygrać lub choćby zremisować grę (przy dalszej optymalnej grze jego taty), wyznaczy jaki powinien być następny ruch Jasia, aby to się mogło udać i wypisze wynik na standardowe wyjście. Wejście Wejście składa się z trzech wierszy. Każdy z nich składa się z trzech znaków. Każdy znak to O – oznaczający kółko, X – oznaczający krzyżyk lub . – oznaczające wolne pole. Wyjście Jeśli gra jest już zakończona i Jasio wygrał to w pierwszym i jedynym wierszu wyjścia należy wypisać TAK. Jeśli Jasio może wygrać (ale jeszcze nie wygrał), w pierwszym wierszu wyjścia należy wypisać słowo TAK, a w drugim wierszu wyjścia rosnący ciąg cyfr oznaczający numery pól (zgodnie z numeracją z rysunku powyżej), w których Jasio powinien postawić swój symbol, aby mógł wygrać. Jeśli gra jest już zakończona i Jasio zremisował to w pierwszym i jedynym wierszu wyjścia należy wypisać REMIS. Jeśli Jasio nie może zapewnić sobie zwycięstwa, ale może zapewnić sobie remis (a gra jeszcze trwa) to w pierwszym wierszu wyjścia powinno się znaleźć słowo REMIS, a w drugim wierszu wyjścia rosnący ciąg cyfr oznaczający numery pól, w których Jasio powinien postawić swój symbol, aby zremisować. Jeśli Jasio nie może sobie zapewnić nawet remisu – pierwszy i jedyny wiersz wyjścia powinien zawierać słowo NIE. Cyfry na wyjściu nie powinny być oddzielane żadnymi odstępami. Uwaga Gwarantowane jest, że zawsze przedstawiona będzie “sensowna” sytuacja w grze (być może już zakończonej) w kółko i krzyżyk. Na przykład następujące nie wystąpi w danych wejściowych: OOO XXX ... ponieważ po postawieniu pięciu symboli gra zostanie już zakończona i nie będzie możliwe postawienie szóstego symbolu. Gwarantowane jest również, że liczba symboli O jest równa liczbie symboli X lub jest dokładnie o jeden większa. Przykład Input Output Explanation OX. ... ... TAK 457 Jasio gra kółkiem – jeśli postawi on kółko przykładowo w polu numer 4 to wymusi ruch taty w polu numer 7. Stawiając kółko w polu 5, Jasio zyskuje dwie drogi zwycięstwa (polem 6 lub polem 8). Tata może zablokować co najwyżej jedną z tych dróg, czyli Jasio wygrywa. Input Output Explanation ..X .O. O.. REMIS 19 Jasio gra krzyżykiem – przy bieżącej sytuacji na planszy o zwycięstwie raczej nie ma mowy. Jeśli Jasio nie postawi krzyżyka w polu 1 lub 9 to przegra. Załóżmy na chwilę, że Jasio postawi krzyżyk w polu numer 6, wówczas tata stawia kółko w polu numer 1 i ma teraz dwie drogi zwycięstwa (polem 4 lub polem 8). Jasio może zablokować co najwyżej jedną z tych dróg, czyli tata wygrałby. Jeśli Jasio zagra mądrzej i zablokuje krzyżykiem pole 1 lub pole 9, będzie mógł chociaż uratować remis. Input Output Explanation XXO OOO XOX NIE Gra jest skończona zwycięstwem kółka w ostatnim ruchu. Zgodnie z treścią powyżej teraz miałby grać Jasio, czyli grałby krzyżykiem, a to oznacza, że zwycięskim kółkiem grał tata.

Input	Output	Explanation
`OX. ... ...`	`TAK 457`	Jasio gra kółkiem – jeśli postawi on kółko przykładowo w polu numer 4 to wymusi ruch taty w polu numer 7. Stawiając kółko w polu 5, Jasio zyskuje dwie drogi zwycięstwa (polem 6 lub polem 8). Tata może zablokować co najwyżej jedną z tych dróg, czyli Jasio wygrywa.

Input	Output	Explanation
`XXO OOO XOX`	`NIE`	Gra jest skończona zwycięstwem kółka w ostatnim ruchu. Zgodnie z treścią powyżej teraz miałby grać Jasio, czyli grałby krzyżykiem, a to oznacza, że zwycięskim kółkiem grał tata.