28a Olimpíada Brasileira de Informática
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.
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'
- Subtarefa 3 (25 pontos):
- N ≤ 100
- Ci ≤ 10 para 1 ≤ i ≤ N
- Subtarefa 4 (34 pontos): Nenhuma restrição adicional.
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 |