W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Mała Bajtosia dostała w prezencie grę o nazwie Usuwanka. W tej grze dany jest ciąg przylegających do siebie klocków, ponumerowanych kolejno od 1 do . Każdy klocek jest albo biały, albo czarny, przy czym białych klocków jest razy więcej niż czarnych. Gra jest jednoosobowa. Celem gry jest usunięcie, za pomocą określonych ruchów, wszystkich klocków z ciągu.
Pojedynczy ruch polega na usunięciu dokładnie białych i jednego czarnego klocka bez zmiany pozycji pozostałych klocków. Ruch jest dozwolony, jeśli między żadnymi dwoma usuwanymi w tym ruchu klockami nie ma "dziury", czyli pustego miejsca po uprzednio usuniętym klocku.
Pomóż Bajtosi, ona tak bardzo Cię prosi... Znajdź dowolny ciąg dozwolonych ruchów prowadzący do usunięcia wszystkich klocków.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem, oznaczające liczbę klocków w grze oraz liczbę białych klocków, które należy usunąć w każdym ruchu. We wszystkich testach zachodzi warunek .
W drugim wierszu znajduje się napis złożony z liter b oraz c. Kolejne litery napisu określają kolor kolejnych klocków: b - biały, c - czarny. Możesz założyć, że dla danych testowych istnieje szukany ciąg ruchów prowadzący do usunięcia wszystkich klocków.
W testach wartych łącznie 40% punktów zachodzi dodatkowy warunek .
Twój program powinien wypisać na standardowe wyjście wierszy. Kolejne wiersze powinny opisywać kolejne ruchy. Każdy z tych wierszy powinien zawierać liczb, podanych w kolejności rosnącej oraz rozdzielonych pojedynczymi odstępami, oznaczających numery klocków, które należy usunąć w danym ruchu.
Dla danych wejściowych:
12 2 ccbcbbbbbbcb
poprawną odpowiedzią jest:
1 8 12 2 6 7 3 4 5 9 10 11
Wyjaśnienie do przykładu: Niech oznacza puste miejsce po usuniętym klocku. Wykonując podane powyżej ruchy, uzyskujemy kolejno następujące układy klocków:
Autorzy zadania: Jakub Pachocki, Wojciech Rytter.