28a Olimpíada Brasileira de Informática
Game Show
Populares no mundo inteiro, os game shows são programas de televisão ou internet nos quais os participantes competem em jogos para ganhar prêmios. A rede de televisão da sua cidade lançou um novo game show que funciona da seguinte forma:- O jogo é jogado por um único participante e possui diversas salas numeradas a partir do número 1.
- Ao entrar em uma sala, o participante deve escolher seguir por uma das duas portas à sua frente: a porta da esquerda e a porta da direita. Na sala i, a porta da esquerda leva à sala 2 · i enquanto que a porta da direita leva à sala 2 · i+1. Por exemplo, na sala 1, a porta da esquerda leva à sala 2 e a porta da direita leva à sala 3. Da mesma forma, a porta da esquerda da sala 2 leva à sala 2 · 2=4 e a porta da direita da sala 4 leva à sala 2 · 4+1=9.
- No início do jogo, o participante é colocado na sala de número 1, em frente às portas para as salas 2 e 3, e recebe um papel com uma sequência de instruções indicando por qual porta ele deve seguir a cada momento do jogo. Cada instrução é representada por uma letra E ou D, indicando que ele deve seguir pela porta da esquerda ou da direita, respectivamente.
- As salas não possuem indicação de seus números e o desafio é não perder as contas: o participante ganha o jogo se ele conseguir chegar na sala final correta (ou seja, seguir pela porta correta a cada passo de acordo com as instruções) e, ao chegar nesta sala final, dizer corretamente o número dela.
Entrada
A primeira linha da entrada contém um inteiro N, o número de instruções dadas no início do jogo. A segunda e última linha contém uma cadeia de N caracteres a1a2… aN, cada um deles sendo `E' ou `D', indicando as instruções dadas no início do jogo. No i-ésimo passo, se ai=`E' o participante deve escolher a porta da esquerda e se ai=`D' ele deve escolher a porta da direita.Saída
Seu programa deverá imprimir uma única linha contendo um único inteiro, o número da sala final caso o participante siga corretamente as instruções.Restrições
- 1 ≤ N ≤ 20
- ai=`E' ou `D' para 1 ≤ i ≤ N
Informações sobre a pontuação
A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima.- Subtarefa 1 (0 pontos): Esta subtarefa é composta apenas pelos exemplos mostrados abaixo. Ela não vale pontos, serve apenas para que você verifique se o seu programa imprime o resultado correto para os exemplos.
- Subtarefa 2 (30 pontos): N=2 (veja o exemplo 2).
- Subtarefa 3 (30 pontos): O participante deve ir para a esquerda em todos os passos, ou seja, ai=`E' para todo 1 ≤ i ≤ N (veja o exemplo 3).
- Subtarefa 4 (40 pontos): Sem restrições adicionais.
Exemplos
Entrada
4 EEDE |
Saída
18 |
Entrada
2 ED |
Saída
5 |
Entrada
8 EEEEEEEE |
Saída
256 |