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

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.
Por exemplo, suponha que a sequência de instruções seja EEDE. Isso significa que o participante deve escolher as portas esquerda, esquerda, direita e esquerda, nesta ordem. Podemos ver no diagrama abaixo que, neste caso, o participante termina na sala de número 18. Portanto, ao chegar na última sala, o participante deve dizer o número 18 para vencer. 1 →(E) 2 →(E) 4 →(D) 9 →(E) 18 Você se inscreveu para participar do game show, mas percebeu que ele exige muita habilidade com cálculos matemáticos e decidiu praticar. Para isso, você quer escrever um programa que te ajude a conferir os cálculos. Dada uma sequência de instruções, determine qual o número da sala na qual o participante terminará o jogo se ele seguir corretamente as instruções.

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.
Seu programa pode resolver corretamente todas ou algumas das subtarefas acima (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por qualquer uma das suas submissões.

Exemplos

Entrada
4
EEDE
Saída
18
	

 

Entrada
2
ED
Saída
5
	

 

Entrada
8
EEEEEEEE
Saída
256
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação