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.
Na stole ustawiono w rzędzie n pudełek. Wśród nich, pewne dwa sąsiednie pudełka są puste. Reszta pudełek zawiera n/2 - 1 czerwonych piłeczek i n/2 - 1 zielonych piłeczek. W każdym pudełku znajduje się co najwyżej jedna piłeczka.
Bajtazar wymyślił bardzo ciekawą grę, polegającą na przekładaniu piłeczek między pudełkami w ten sposób, aby na koniec wszystkie czerwone piłeczki znalazły się przed wszystkimi zielonymi. W każdym pojedynczym ruchu wolno przełożyć dwie sąsiadujące piłeczki do pustych pudełek, przy czym podczas tej operacji nie wolno zamieniać ich kolejności. Bajtazar przyszedł do Ciebie z prośbą o pomoc w napisaniu programu grającego w tę grę.
Dysponujesz 11 zestawami danych umieszczonych w dziale Przydatne zasoby. Każdy zestaw jest zapisany w osobnym pliku pudk.in, gdzie k jest numerem zestawu ( 0k10). Rozwiązaniem do zadania ma być archiwum spakowane przy użyciu programu zip, które powinno zawierać pliki pudk.out z wynikami dla poszczególnych zestawów. Sumaryczny rozmiar plików przed spakowaniem nie może przekraczać 10 MB, a wielkość archiwum nie może przekraczać 3 MB. Pierwszy wiersz pliku z wynikiem powinien zawierać liczbę ruchów m potrzebnych do wykonania sortowania. Każdy z kolejnych m wierszy powinien zawierać po jednej liczbie pk ( 0pkn - 2), opisującej k - ty ruch. Ruch opisany przez liczbę pk polega na przeniesieniu piłeczki z pudełka pk do lewego, pustego pudełka, a piłeczki z pudełka pk + 1 do prawego, pustego pudełka.
UWAGA: Zawodnik otrzyma 1 punkt za zestaw pod warunkiem, że wypisana sekwencja ruchów będzie prowadziła do poprawnej, posortowanej konfiguracji piłeczek, oraz żaden z zawodników nie poda krótszej sekwencji ruchów prowadzącej do poprawnej, posortowanej konfiguracji piłeczek.
10 0110220101poprawną odpowiedzią jest:
5 1 3 5 8 2 Wykonywane operacje, doprowadzające do sekwencji posortowanej: | C | Z | Z | C | _ | _ | C | Z | C | Z | | C | _ | _ | C | Z | Z | C | Z | C | Z | | C | C | Z | _ | _ | Z | C | Z | C | Z | | C | C | Z | Z | C | _ | _ | Z | C | Z | | C | C | Z | Z | C | C | Z | Z | _ | _ | | C | C | _ | _ | C | C | Z | Z | Z | Z | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Autor zadania: PA team.
<Wyślij rozwiązanie> [0/100]