In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
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 Bajtocji odbędzie się Parada Kolorowych Pociągów. Na torach
technicznych bajtockiego dworca trwają intensywne przygotowania.
Na dworcu jest równoległych torów, ponumerowanych od
do
. Na
-tym torze ustawiono pociąg o numerze
. Każdy pociąg
składa się z
wagonów, z których każdy jest pomalowany na jeden
z 26 kolorów (oznaczonych małymi literami alfabetu angielskiego).
Mówimy, że dwa pociągi wyglądają identycznie, jeśli ich
kolejne wagony są tego samego koloru.
Parada będzie polegać na tym, że co minutę stacyjny dźwig zamieni miejscami pewną parę wagonów. Prawdziwa parada odbędzie się jednak dopiero jutro. Dziś dyżurny ruchu Bajtazar bacznie przyglądał się próbie generalnej. Dokładnie zapisał sobie ciąg kolejno zamienianych par wagonów.
Bajtazar nie lubi, gdy zbyt wiele pociągów wygląda identycznie.
Chciałby, żebyś dla każdego pociągu policzył maksymalną liczbę
pociągów, które w pewnym momencie wyglądają identycznie jak pociąg
w owym momencie.
Napisz program, który:
Pierwszy wiersz wejścia zawiera trzy liczby naturalne ,
oraz
(
,
,
), oznaczające
odpowiednio liczbę pociągów, ich długość oraz liczbę wykonywanych
zamian wagonów.
W kolejnych
wierszach znajdują się opisy kolejnych pociągów stojących
na torach.
-ty z tych wierszy składa się z
małych liter alfabetu angielskiego
reprezentujących kolory kolejnych wagonów
-tego pociągu.
Za opisami pociągów znajduje się
wierszy zawierających opisy kolejnych
zamian, w kolejności ich wykonywania.
W
-tym z tych wierszy znajdują się cztery liczby całkowite
,
,
,
(
,
,
lub
) i opisują one
-tą operację
wykonywaną przez dźwig - zamianę wagonu numer
z pociągu
z wagonem
pociągu
.
Twój program powinien wypisać dokładnie wierszy.
-ty wiersz
powinien zawierać jedną liczbę całkowitą - liczbę pociągów
wyglądających tak samo jak pociąg numer
w pewnym momencie czasu.
Dla danych wejściowych:
5 6 7 ababbd abbbbd aaabad caabbd cabaad 2 3 5 4 5 3 5 5 3 5 2 2 1 2 4 3 2 2 5 1 1 1 3 3 4 1 5 6
poprawną odpowiedzią jest:
3 3 3 2 3
Oto wygląd pociągów w kolejnych fazach próby generalnej:
tor 1: ababbd ababbd ababbd ababbd aaabbd aaabbd aaabbd aaabbd tor 2: abbbbd ababbd ababbd aaabbd aaabbd acabbd acabbd acabbd tor 3: aaabad -> aaabad -> aaabad -> aaabbd -> aaabbd -> aaabbd -> aaabbd -> aaabbd tor 4: caabbd caabbd caabbd caabbd cabbbd cabbbd cabbbd dabbbd tor 5: cabaad cabbad caabbd caabbd caabbd aaabbd aaabbd aaabbc (0) (1) (2) (3) (4) (5) (6) (7)
Dla pociągów 1, 2 i 3 najwięcej podobnych było np. w momencie (4) (były one nawzajem do siebie podobne). Dla pociągu 5 najwięcej mu podobnych było w momentach (5) i (6). Dla pociągu 4 najwięcej podobnych było np. w momencie (2).
Autor zadania: Piotr Stańczyk.