Quasi palíndroms P94172


Statement
 

pdf   zip

En aquest problema, direm que una paraula és un quasi palíndrom si es pot convertir en un palíndrom canviant com a molt un caràcter. Donada una paraula, dividiu-la en el mínim nombre de quasi palíndroms.

Entrada

L’entrada consisteix en diverses paraules amb entre 1 i 1000 lletres minúscules.

Sortida

Per a cada paraula, escriviu el mínim nombre de quasi palíndroms en què es pot dividir.

Pista

Feu dues programacions dinàmiques, una d’elles per calcular, per a cada subparaula, el nombre mínim de caràcters que cal canviar per convertir-la en un palíndrom.

Public test cases

  • Input

    z
abba
ab
abcd
racecar
abcda
acabbaa
abcdef
aabb
aabbccddee
abcdefghij
qwertyuiopasdfgh

    Output

    1
1
1
2
1
1
2
2
2
3
4
6
    • Information
    Author
    David García
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++