Nosaukums
Sadalīšana palindromos (sadpalin)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
90%

Definīcija

Palindroms ir burtu virkne, kas vienādi lasāma gan no kreisās puses uz labo, gan no labās puses uz kreiso. Piemēram, palindromi ir virknes 'ala', 'sileputrakartupelis','f', bet nav 'ligzda','alas' un 'kuku'.

Ja burtu virkne nav palindroms, to vienmēr var "sagriezt" daļās, no kurām katra ir palindroms.

Uzrakstiet programmu, kas dotai burtu virknei noskaidro mazāko skaitu fragmentu, kādā tā jāsagriež, lai katra daļa būtu palindroms!


Ievaddatu raksturojums

Ievaddatu vienīgajā rindā dota burtu virkne - ne vairāk kā 100 angļu alfabēta mazie burti (a-z).


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada naturāls skaitlis - mazākais iespējamais fragmentu skaits, kādā jāsadala dotā virkne.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā


Paraugdati

Stdin
anaban
Stdout
2

Stdin
abaccbcb
Stdout
3

Stdin
anavolimilana
Stdout
5

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