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

Corrida de Rua

A Quadradônia foi escolhida para sediar uma prova internacional de corrida de rua. As ruas da Quadradônia são todas alinhadas aos eixos Norte-Sul e Leste-Oeste. As quadras da cidade são quadradas, todas de mesma dimensão. A partida e a chegada da corrida são em uma mesma interseção de ruas. Para realizar a corrida será necessário cercar a área da cidade onde será feito o percurso. A cerca será colocada a no mínimo uma quadra de distância de qualquer ponto do percurso da corrida, e deve ser retilínea e alinhada aos eixos. As figuras (a) e (b) abaixo mostram mapas da cidade ilustrando duas possibilidades de percurso e respectivas possibilidades de cercas.
Dado o percurso da corrida, sua tarefa é escrever um programa para determinar o menor comprimento possível da cerca, em número de quadras.

Entrada

A primeira linha contém um inteiro N, o número de segmentos que definem o percurso da corrida. As N linhas seguintes descrevem os segmentos, na ordem em que são percorridos na corrida, a partir do ponto de partida/chegada. Cada linha contém um inteiro Ci e um caractere Di, indicando respectivamente o comprimento do segmento, em número de quadras, e a direção do segmento, onde `N' indica Norte, `S' indica Sul, `L' indica Leste e `O' indica Oeste.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o menor comprimento possível da cerca, em número de quadras.

Restrições

  • 2 ≤ N ≤ 100 000
  • 1 ≤ Ci ≤ 10 000 para 1 ≤ i ≤ N
  • Di é `N', `S', `L' ou `O' para 1 ≤ i ≤ N

Informações sobre a pontuação

A tarefa vale 100 pontos. Os pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:
  • Subtarefa 1 (11 pontos): N = 2, ou seja, o percurso utiliza uma única rua. (Veja o exemplo de entrada 1.)
  • Subtarefa 2 (30 pontos):
    • Di= `N' ou `L' para 1 ≤ i ≤ N - 2
    • D_{N-1}= `S'
    • DN= `O'
    Ou seja, o percurso da corrida forma uma escadinha. (Veja os exemplos de entrada 3 e 4.)
  • Subtarefa 3 (25 pontos):
    • N ≤ 100
    • Ci ≤ 10 para 1 ≤ i ≤ N
  • Subtarefa 4 (34 pontos): Nenhuma restrição adicional.
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
2
7 L
7 O
Saída
22
	

 

Entrada
8
2 L
3 S
3 L
3 N
2 L
5 S
7 O
5 N
Saída
32
	

 

Entrada
8
3 N
1 L
1 N
2 L
1 N
3 L
5 S
6 O
Saída
30
	

 

Entrada
8
2 N
2 L
2 N
3 L
1 N
1 L
5 S
6 O
Saída
30
	

 

Entrada
7
5 L
3 S
3 O
5 N
4 O
2 S
2 L
Saída
32
	

 

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