Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2025
Problem description
-…Albert, Salami, Śmieszek, Nerwus, Tom, Tomasz, Tamburyn, Głowonóg, McGula, Karczoszek, Pingwin, Pete i Steve. Ale chyba najgorsze imię dla tego żabusia to…
-Zaraz, czekaj, Greg – przerwał bratu Wirt, rozglądając się niespokojnie wśród otaczających ich drzew. – Gdzie… my jesteśmy? – Nagle chwycił się za głowę, rwąc włosy z rozpaczy. Krążąc nerwowo po leśnej ściółce, zaczął wygłaszać dramatyczny monolog: – Choć zabłądziłem, moje zranione serce zostało w domu i złamane spoczywa na cmentarzu utraconej miłości…
Jednak Greg miał na głowie sprawę znacznie ważniejszą niż zabłądzenie w lesie czy problemy miłosne starszego brata. W końcu kto, jeśli nie on, miał wybrać imię dla żabusia?
Greg chciał, aby imię żabusia było prawie-palindromem. Co więcej, z racji jego młodego wieku, zdarzało mu się czasem mylić litery. Na przykład nie potrafił odróżnić od siebie liter S i Z, a do tego jego pamięć bywała zawodna – jeśli zapomniał, jaką literę miał wpisać, zastępował ją symbolem *, który mógł oznaczać dowolną literę.
Dane jest słowo długości N oraz k - ograniczenie na liczbę błędów.
Słowo zbudowane jest z wielkich liter alfabetu łacińskiego oraz z symbolu *, który może reprezentować dowolną wielką literę A − Z.
Greg uzna, że imię dla żabki jest dobre, jeśli, jest palindromem z nie więcej niż k błędami. Dla przypomnienia:
Słowo jest palindromem, jeśli czytane od lewej do prawej jest takie samo, jak czytane od prawej do lewej (na przykład słowo KAJAK).
Słowo jest palindromem z k błędami, jeśli po zamianie k liter, staje się ono palindromem (na przykład słowo KAJMAK jest palindromem z 1 błędem - można zamienić literę J na M, aby uzyskać palindrom).
Słowo jest palindromem z nie więcej niż k błędami, jeśli jest palindromem z l błędami, dla l ≤ k (słowa KAJMAK i KAJAK są palindromami z nie więcej niż 1 błędem, ale słowo BOJKOT nie jest).
Co więcej, litera S i Z to według niego ta sama litera, więc w słowie ZAW * AS nie widzi żadnego błędu (wyjaśnienie: myląc litery S i Z dopasowuje do siebie pierwszą i ostatnią literę, następnie dopasowuje do siebie literę A z drugiej i piątej pozycji, Litera W z trzeciej pozycji pasuje do * z czwartej pozycji w słowie).
Wejście
W pierwszym wierszu wejścia znajduje się liczba N oznaczająca długość słowa, oraz liczba k - maksymalna liczba błędów.
W drugim wierszu wejścia znajduje się słowo długości N złożone z wielkich liter alfabetu łacińskiego oraz z symbolu *.
Wyjście
W jedynym wierszu wyjścia znajduje się odpowiedź na pytanie - czy imię podane na wejściu spełnia warunki Grega?.
TAK - jeśli spełnia warunki, NIE w przeciwnym przypadku.
Ograniczenia
1 ≤ N ≤ 1000,
0 ≤ k ≤ N/2.
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
Według Grega podane słowo jest palidromem, nie zawiera żadnego błedu. Pierwsza litera S pasuje do ostatniej litery Z, druga litera A pasuje do *, natomiast środkowa litera psuje do samej siebie. |
| Wejście | Wyjście | Wyjaśnienie |
|
|
To słowo nie spełnia podanych warunków - druga litera A nie pasuje do litery U, więc liczba błędów to 1, co przekracza limit 0 błędów, który był podany na wejściu. |
| Wejście | Wyjście | Wyjaśnienie |
|
|
To słowo Greg uznaje za palindrom. Pierwsza i ostatnia litera to G, następnie druga litera * pasuje do drugiej od końca litery O, trzecia i trzecia od końca litera to R, następnie występują dwa błedy - litera E nie pasuje do F, dalej G nie pasuje do S. |
| Wejście | Wyjście | Wyjaśnienie |
|
|
W tym słowie Greg widzi dwa błędy. Limit błędów jest przekroczony o 1. |