Az I/S. 70. feladat (2023. március)

I/S. 70. Egy T betűsorozatot palindromnak nevezünk, ha az angol ábécé kisbetűiből áll, és visszafele olvasva megegyezik T-vel. Például az ,,abbfbba'', ,,e'' és ,,tt'' betűsorozatok palindromok, de az ,,ab'', ,,xyz'' és ,,abab'' betűsorozatok nem.

Egy T betűsorozatot szuperpalindromnak nevezünk, ha pontosan egy betűből áll, vagy pedig felírható PxP alakban, ahol P egy szuperpalindrom, x pedig az angol ábécé egy tetszőleges kisbetűje. Például az ,,a'', ,,xyxhxyx'' és ,,aaa'' betűsorok szuperpalindromok, de az ,,aa'', ,,xyxhyxy'' és ,,aabcbaa'' betűsorok nem.

Adott egy \(\displaystyle N\) darab betűből álló betűsor. Adjuk meg, hogy minimum hány betűjét kell megváltoztatni ahhoz, hogy egy szuperpalindromot kapjunk.

A bemenet első sorában az \(\displaystyle N\) szám található, a betűsor hossza. A második sorban az angol ábécé \(\displaystyle N\) darab betűje található, szóköz nélkül.

A kimenet egyetlen sorában egyetlen szám szerepeljen: a minimálisan átírandó betűk száma, hogy szuperpalindromot kapjunk. Ha ez nem lehetséges, írjunk ki \(\displaystyle (-1)\)-et.

Magyarázat (1. példa): 3 betű megváltoztatásával kaphatjuk például a következő szuperpalindromot: ,,abababa''.

Korlátok: \(\displaystyle 1 \le N \le 10^{5}\). Időkorlát: 0,4 mp.

Értékelés: a pontok 50%-a kapható, ha a program helyes kimenetet ad az \(\displaystyle N\le 7\) esetekben.

Beküldendő egy is70.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

A beküldési határidő 2023. április 17-én LEJÁRT.

Statisztika:

5 dolgozat érkezett.
10 pontot kapott:	Zádor-Nagy Zsombor.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2023. márciusi informatika feladatai