Nosaukums
Palindroma veidošana (palin)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

Palindroms ir simetriska simbolu virkne, t.i., virkne, kas lasāma vienādi gan no kreisās puses uz labo, gan no labās puses uz kreiso. Jums jāuzraksta programma, kas dotai simbolu virknei nosaka, kāds mazākais simbolu skaits tajā jāiesprauž, lai pārveidotu to par palindromu.

Tā, piemēram, iespraužot divus simbolus virknē “Ab3bd”, to var pārveidot par palindromu (“dAb3bAd” vai “Adb3bdA”). Jāatzīmē, ka šajā gadījumā tas arī ir mazākais nepieciešamais iespraužamo simbolu skaits.


Ievaddatu raksturojums

Ievaddatu pirmajā rindā ir dots naturāls skaitlis: ievada simbolu virknes garums N, 3<=N<=5000. Faila otrajā rindā dota simbolu virkne garumā N. Virkne var saturēt tikai latīņu alfabēta lielos ('A'..'Z') un mazos ('a'..'z') burtus un ciparus ('0'..'9'). Lielie un mazie burti tiek uzskatīti par atšķirīgiem simboliem.


Izvaddatu raksturojums

Izvaddatu pirmajā rindā jāizvada viens vesels nenegatīvs skaitlis, kas ir mazākais virknē iespraužamo simbolu skaits.


Piezīmes

Uzdevums izmantots 12. Vispasaules informātikas olimpiādē Pekinā (Ķīnas TR) 2000.gadā. 

Autors: Sergejs Meļņiks


Paraugdati

Stdin
5
Ab3bd
Stdout
2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.