In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Na potrzeby tego zadania słowem nazwiemy niepusty ciąg wielkich liter alfabetu angielskiego.
Długością słowa jest liczba zawartych w nim liter.
Tak więc ABAACBBBA jest przykładem słowa o długości 9.
Blokiem w słowie nazywamy maksymalny, spójny podciąg takich samych liter.
Powiemy, że słowo jest
-trudne, jeśli zawiera
bloków.
Nasze przykładowe słowo
jest 6-trudne, ponieważ składa się z bloków A|B|AA|C|BBB|A.
Jeśli dwa słowa mają taką samą długość, to możemy badać, jak bardzo się różnią.
Dwa słowa o długości są
-niepodobne, jeśli dla dokładnie
indeksów
(
),
-ta litera pierwszego słowa jest inna niż
-ta litera drugiego słowa.
Jeśli weźmiemy słowo
AAAABBBBB, to słowa
i
są 3-niepodobne.
Dla danego słowa , chcemy znaleźć niezbyt różniące się od niego słowo
,
które nie będzie na dodatek zbyt trudne. Twoim zadaniem będzie stwierdzić na ile łatwe może być słowo
.
Napisz program, który:
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oddzielone pojedynczym odstępem
(
,
). Oznaczają one odpowiednio: długość słowa
i dopuszczalny stopień
niepodobieństwa. W drugim wierszu znajduje się
-literowe słowo
złożone z wielkich liter alfabetu angielskiego.
W jedynym wierszu wyjścia należy wypisać szukaną liczbę .
9 3 ABAACBBBApoprawną odpowiedzią jest:
2
Autor zadania: Tomasz Idziaszek.