Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PAL - Palíndrome

Uma cadeia de caracteres é chamada de palíndrome se seqüência de caracteres da esquerda para a direita é igual à seqüência de caracteres da direita para a esquerda (uma outra definição é que o primeiro caractere da cadeia deve ser igual ao último caractere, o segundo caractere seja igual ao penúltimo caractere, o terceiro caractere seja igual ao antepenúltimo caractere, e assim por diante). Por exemplo, as cadeias de caracteres 'mim', 'axxa' e 'ananaganana' são exemplos de palíndromes.

Se uma cadeia não é palíndrome, ela pode ser dividida em cadeias menores que são palíndromes. Por exemplo, a cadeia 'aaxyx' pode ser dividida de quatro maneiras distintas, todas elas contendo apenas cadeias palíndromes: {'aa', 'xyx'}, {'aa', 'x', 'y', 'x'}, {'a', 'a', 'xyx'} e {'a', 'a', 'x', 'y', 'x'}.

Tarefa

Escreva um programa que determine qual o menor número de partes em que uma cadeia deve ser dividida de forma que todas as partes sejam palíndromes.

Entrada

A entrada é constituída de vários conjuntos de teste. A primeira linha de um conjunto de testes contém um inteiro N que indica o número de caracteres da cadeia (1 <= N <= 2000). A segunda linha contém a cadeia de caracteres, composta por letras minúsculas (de 'a' a 'z'), sem espaços em branco. O final da entrada é indicado por N = 0.

Exemplo de Entrada
3
axa
6
xyzyyx
10
bbabcbbaab
0

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A segunda linha deve conter um inteiro indicando o menor número de partes que a cadeia de entrada deve ser dividida de forma que todas as partes sejam palíndromes. A terceira linha deve ser deixada em branco. O formato mostrado no exemplo de saída abaixo deve ser seguido rigorosamente.

Exemplo de Saída
Teste 1
1

Teste 2
4

Teste 3
4

(esta saída corresponde ao exemplo de entrada acima)

Restrições

0 <= N <= 2000 (N = 0 apenas para indicar o fim da entrada)


Adicionado por:Wanderley Guimarăes
Data:2007-03-07
Tempo limite:0.140s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2004

hide comments
2016-04-10 22:58:12 Elsio [UFABC]
Alguém pode me explicar pq a matriz pal[n][n] só pode ser declarada no global? tive que fazer um bool pal[3000][3000] no global quando na verdade queria fazer com n.
2010-03-23 22:04:50 Davi Souto Grangeiro [USJT]
Limitem seus Loop's pelo valo de "N", pois os casos de teste tem strings de tamanho superior.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.