Problem description

Back
Show PDF
Palindromiczny Żabuś
(A)
Limit pamięci: 64 MB
Limit czasu: 1.00 s

-…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:

  1. 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).

  2. 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).

  3. 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 
5 0
ZAB*S

TAK

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 
5 0
ZABUS

NIE

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 
10 3
G*REGSFROG

TAK

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 
11 1
KARCZOS*ZEK

NIE

W tym słowie Greg widzi dwa błędy. Limit błędów jest przekroczony o 1.