XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: palindromo.x, onde x deve ser c, cpp, java, js ou py

Palíndromo

Uma cadeia de caracteres é chamada de palíndromo se a sequência de caracteres da esquerda para a direita é igual à sequência de caracteres da direita para a esquerda (uma outra definição é que o primeiro caractere da cadeia deve ser igual ao último caractere da cadeia, o segundo caractere deve ser igual ao penúltimo caractere, o terceiro caractere deve ser igual ao antepenúltimo caractere, e assim por diante).

Por exemplo, as cadeias de caracteres ‘mim’, ‘axxa’ e ‘ananaganana’ são exemplos de palíndromos. Se uma cadeia não é palíndroma, ela pode ser dividida em cadeias menores que são palíndromas. Por exemplo, a cadeia ‘aaxyx’ pode ser dividida de quatro maneiras distintas, todas elas contendo apenas cadeias palíndromas: \‘aa’, ‘xyx’\, \‘aa’, ‘x’, ‘y’, ‘x’\, \‘a’, ‘a’, ‘xyx’\ e \‘a’, ‘a’, ‘x’, ‘y’, ‘x’\.

Dada uma cadeia de caracteres, escreva um programa que determine qual o menor número de partes em que a dada cadeia deve ser dividida de forma que todas as partes sejam palíndromos.

Entrada

A primeira linha contém um número inteiro N que indica o número de caracteres da cadeia. A segunda linha contém a cadeia de caracteres, composta por letras minúsculas, de ‘a’ a ‘z’, sem espaços em branco.

Saída

Seu programa deve produzir uma única linha, contendo um número inteiro, o menor número de partes em que a cadeia de entrada deve ser dividida de forma que todas as partes sejam palíndromes.

Restrições

  • 1 ≤ N ≤ 2000
  • A cadeia de caracteres contém apenas letras minúsculas não acentuadas (‘a’ a ‘z’).

Informações sobre a pontuação

  • Em um conjunto de casos de teste somando 20 pontos, N ≤ 8
  • Em um conjunto de casos de teste somando 40 pontos, N ≤ 300

Exemplos

Entrada
3
axa
Saída
1
	

 

Entrada
6
xyzyyx
Saída
4
	

 

Entrada
10
bbabcbbaab
Saída
4
	

 

Promoção
logo sbc
Patrocínio
Apoio
Coordenação