Twoja postać w D'a'D (Demolka and Demolka) rozwija się jako zarówno Wojownik jak i Czarodziej. W każdej z tych klas może osiągnąć poziom 0, 1, ..., n. Na początku Twoja postać ma zerowy poziom w każdej z tych klas. Awans polega na tym, że w jednej z klas Twoja postać osiąga kolejny poziom (oczywiście, może awansować tylko do poziomu n, i kiedyś wcześniej w tej klasie musiała uzyskać poprzedni poziom).
Przy tym, awanse mają pewne ograniczenia. Jeśli Twój poprzedni awans był w tej samej klasie co nowy planowany awans, to możesz bez przeszkód awansować. Natomiast, jeśli chcesz awansować w drugiej z klas, to Twoje możliwości limituje Magiczna Tabelka Awansów.
Tabelka ta jest tabelką n x n zer i jedynek. Jeśli w i-tym rzędzie i w j-tej kolumnie jest 1, oznacza to, że po tym, jak Twoim poprzednim awansem był awans na i-ty stopień Wojownika, to następnym awansem może być awans na j-ty stopień czarodzieja, jeśli 0 - taki awans nie może mieć miejsca. Z drugiej strony, jeśli tam w tabelce jest 0, to jeśli Twoim poprzednim awansem był j-ty stopień Czarodzieja, to następnym może być i-ty stopień Wojownika, a jeśli tam jest 1, to taki awans nie może mieć miejsca.
Na początku Twoja postać może awansować na pierwszy poziom Wojownika lub Czarodzieja. Zaplanuj rozwój Twojej postaci tak, by osiągnęła n-ty poziom w obu klasach, zgodnie z Magiczną Tabelką Awansów.
W pierwszej linii dana jest liczba 1 <= n <= 2000. W kolejnych n liniach jest po n cyfr 0 lub 1 - Magiczna Tabelka Awansów.
Wypisz jedno słowo złożone z 2n liter: n liter W i n liter C. Oznacza ono kolejne awanse Twojej postaci: czy odbywają się one w klasie Wojownika czy Czarodzieja.
Dla danych wejściowych:
4 1 1 1 1 1 0 1 0 0 1 0 1 0 0 1 1
jedną z prawidłowych odpowiedzi jest:
WWCWCWCC
Wpierw zdobywamy dwa poziomy Wojownika i wciąż mamy zerowy poziom Czarodzieja. W tabelce w drugim wierszu w pierwszej kolumnie jest 1, więc możemy teraz awansować na pierwszy poziom Czarodzieja. Dalej, w trzecim wierszu w pierwszej kolumnie jest 0, więc ostatnio zdobywszy pierwszy poziom Czarodzieja, możemy teraz zdobyć trzeci poziom Wojownika. W trzecim wierszu w drugiej kolumnie jest 1, więc po 3 poziomie Wojownika możemy zdobyć 2 poziom Czarodzieja. Dalej, w 4 wierszu 2 kolumnie jest 0, więc po 2 poziomie Czarodzieja możemy zdobyć 4 poziom Wojownika. Dalej, w 4 wierszu 3 kolumnie jest 1, więc po 4 poziomie Wojownika możemy zdobyć 3 poziom Czarodzieja. I następnie czwarty, bo to jest ta sama klasa w której ostatnio zdobywaliśmy poziom. Nasza postać jest już mega pakerem.
[Zgłoś rozwiązanie] [Moje zgłoszenia]