Intermediário Informática – Semana 26 – Noic
Browse: Home / Problemas da Semana / Informática / Intermediário Informática – Semana 26
Intermediário Informática - Semana 26
Zonas de Ataque Independentes
Uma técnica comum usada por exércitos invasores é cercar uma cidade em vez de diretamente entrar nela. Os exércitos divididem-se em pelotões com bases em uma forma circular ao redor da cidade. Para assumir o controle interno da cidade, pelotões são agrupados em três para cobrir regiões triangulares. Isso é uma política do general para garantir que não haja duas regiões triangulares sobrepostos. Infelizmente, o processo é um pouco mais complicado porque existem dois tipos de exércitos na força invasora. Os dois exércitos diferentes são conhecidos como Exército Vermelho eo Exército Negro. Cada pelotão é formado por um tipo de exército. Enquanto o Exército Preto tem clara intenção de servir ao General, os vermelhos podem trair na primeira oportunidade. Então se decidiu que cada grupo triangular será composto de no máximo um pelotão do Exército Vermelho para que os vermelhos não dominam em qualquer tarefa que lhes for atribuída.
Problema: será dado a você um número de pelotões e suas cores. Você deve encontrar o número de possíveis configurações tal que cada pelotão faça parte de exatamente um grupo e respeite as restrições passadas acima.
A primeira linha de entrada é um inteiro T (T<100) que indica o número de casos de teste. Cada caso consiste de duas linhas. A primeira linha é um inteiro P ( 2 < P < 40 e P é um múltiplo de 3). P representa o número de batalhões. As próximas linhas consistem de uma string de tamanho P. Cada caracter da string é 'R' (Red: vermelho) ou 'B' (Black: preto). A string dá a posição do batalhão no sentido horário. A posição inicial é arbitrariamente escolhida. Portanto, o exemplo acima pode ser representado por qualquer uma das seguintes sequências: 'RBBBRB', 'BBBRBR', 'BBRBRB', 'BRBRBB', 'RBRBBB' ou 'BRBBBR'.