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.|

VIRA11 - Vira!

 

Vira! é um jogo individual que se inicia com N peças igualmente espaçadas em uma linha. Cada peça do Vira! possui dois lados, sendo um branco e um preto; assim, ao virar uma peça, alterna-se a cor que está sendo mostrada entre branco e preto. A figura abaixo ilustra um possível arranjo com 5 peças, duas mostrando o lado branco e duas mostrando o lado preto.

Um movimento consiste em retirar uma peça preta – criando um espaço – e inverter as peças vizinhas à retirada. Sendo assim, dependendo do número de peças vizinhas à retirada, um movimento pode inverter duas, uma, ou mesmo nenhuma peça (se não houver peças vizinhas à que está sendo retirada). Você vence o jogo quando consegue remover todas as peças. A figura abaixo exemplifica uma sequência de movimentos que resolvem uma instância do problema com 5 peças, em que as peças são retiradas na ordem 5-2-1-3-4.

Para uma determinada disposição inicial das peças, podem existir várias soluções diferentes. Por exemplo, poderíamos retirar as peças na ordem 5-2-3-4-1 e ainda assim conseguir retirar todas as peças.

Sua tarefa, neste problema, consiste em contar o número de soluções diferentes para uma dada disposição inicial das peças. Como o número de soluções pode ser muito grande, você deve imprimir apenas o resto do número quando dividido por 10007.

Entrada

A primeira linha da entrada contém o inteiro N. A linha seguinte contém N letras separadas por espaço representando o arranjo inicial das peças. Uma peça branca é indicada pela letra B na entrada, e uma peça preta é indicada pela letra P.

Saída

Seu programa deve imprimir uma linha contendo o número de soluções distintas que resolvem o jogo.

Restrições

  • 1 ≤ N ≤ 1000.

Exemplos

Entrada
5
B P B P P

Saída
11

Entrada
3
B P B

Saída
2


Adicionado por:Wanderley Guimarăes
Data:2012-03-10
Tempo limite:0.100s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2011 - fase 2 nível 2

hide comments
2016-04-17 18:50:38 Elsio [UFABC]
Muito parecido com o http://br.spoj.com/problems/VIVO/
mas ainda estou confuso sobre como resolver.
2012-04-30 14:24:59 Wisllay Vitrio [INF-UFG]
O primeiro caso de teste está errado. A resposta certa é 11. Fiquei muito tempo tentando chegar no 15 =P
2012-04-16 18:42:12 Marcos Kawakami
Pense em uma DP cujo estado tem a ver com quando vocę remove uma peça.
2012-04-15 16:54:03 Kelvin Azevedo Santos [FMUSP]
Minha solucăo é cubica sim... :(
+ a constante é pequena.

Năo sei um algoritmo mais eficiente. alguma dica?
2012-04-14 05:33:33 Marcos Kawakami
@Kelvin
Qual a complexidade de seu código? A soluçăo esperada tem uma complexidade menor que O(N^3), mas como o time limit da OBI estava folgado, algumas soluçőes cúbicas ganharam pontuaçăo integral.
2012-04-12 23:44:45 Kelvin Azevedo Santos [FMUSP]
Meu código passa no site da obi com 700 ms, mas aqui no SPOJ dá TLE. Năo seria possível aumentar um pouco o tempo limite?
2012-03-28 23:34:30 Kelvin Azevedo Santos [FMUSP]


Last edit: 2012-03-28 23:38:40
2012-03-19 18:33:41 Fernando Fonseca [ITA]
A saída correta para o primeiro exemplo é "11".
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.