Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FUGIT09 - O fugitivo

 

Demasi é um terrorista e mafioso italiano que tentou escapar vindo para o Brasil. Mas Demasi não contava com a astúcia de nossa polícia, e acabou sendo preso aqui também.

Por ser mafioso, Demasi conseguiu contratar advogados muito bons, que através de muitos recursos na justiça, acabaram conseguindo uma liberdade condicional para ele.

Nessa liberdade condicional, Demasi deve permanecer a uma certa distância da delegacia de polícia responsável por ele. Para monitorá-lo melhor, eles instalaram nele uma coleira eletrônica inquebrável que, minuto a minuto, envia para uma central as movimentações de Demasi naquele momento.

A informação da coleira é enviada indicando uma direção e uma distância. Por exemplo, em quatro minutos chegam as quatro linhas de informação abaixo:

N 30
O 44
S 22
L 10

Isso significa que no primeiro minuto Demasi se deslocou 30 metros para o norte (letra N), no minuto seguinte andou 44 metros para o oeste (letra O), no outro minuto andou 22 metros para o sul (letra S) e no quarto minuto se deslocou 10 metros para o leste (letra L). Para poder dar um castigo ao terrorista, o juiz decidiu que Demasi só poderia andar nas quatro direções citadas acima. Ou seja, Demasi nunca se movimenta na direção noroeste, por exemplo. Neste problema, você pode supor que todos os movimentos de Demasi ocorrem sobre um plano cartesiano.

A polícia precisa estar sempre atenta à movimentação dele, e pede a sua ajuda para verificar se em algum momento o italiano se desloca a uma distância da delegacia maior do que a permitida. A distância considerada para esta medida é a distância euclidiana.

Tarefa

Sua missão é criar um programa que receba as informações da coleira de Demasi e diga se em algum momento Demasi esteve a uma distância maior do que a permitida.

Você deve assumir que no instante 0 (zero) Demasi está dentro da delegacia (ou seja, a uma distância zero).

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).

A primeira linha da entrada contém dois inteiros N e M (2 ≤ N ≤ 500.000, 1 ≤ M ≤ 1.000.000) representando o número de registros enviados pela coleira de Demasi e a distância máxima que ele pode ficar da delegacia, respectivamente. As N linhas seguintes contêm os registros da coleira, em ordem de envio. Cada linha contém um caractere C (’N’, ’S’, ’L’ ou ’O’, como especificados acima) e um inteiro D (1 ≤ D ≤ 1.000) representando a distância percorrida no minuto.

Saída

Seu programa deve imprimir, na saída padrão, o valor 1 se em algum momento Demasi se afastou da delegacia além da distância permitida, ou o valor 0 caso contrário.

Exemplos

Entrada
5 10
N 2
L 3
S 4
O 4
O 3

Saída
0

Entrada
5 10
N 6
L 8
S 15
O 5
O 4

Saída
1

Adicionado por:Wanderley Guimarăes
Data:2012-05-31
Tempo limite:0.184s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2009 - fase 1 nível 2

hide comments
2015-02-01 03:27:31 Frederico Miranda Brandão Alves
Há um problema no enunciado. "Maior" năo significa "Maior ou igual".
2014-09-04 13:20:48 Washington
Dica: Tente aplicar a distancia manhattan antes da distância euclidiana em alguns casos
2013-04-13 00:16:48 Otávio Augusto
É possível resolver esse problema com Python 2.7?
2013-03-05 15:20:34 Tiago Santana [UNIARARAS]
Pra quem ainda năo conseguiu, passei o problema trocando as variáveis do tipo int por float, mantendo apenas as variaveis de controle (for, while, if, etc) como int. Até que em fim, shaushau.

Last edit: 2013-03-05 15:42:31
2012-06-03 19:58:38 Matheus Henrique
desisto, todos os meus testes deram certo, mas tomo resposta errada :S
2012-06-01 07:26:41 Wanderley Guimarães
Já estăo arrumados os casos de teste, năo há mais N=0, as submissőes foram rejulgadas e mais usuários passaram o problema
2012-06-01 02:49:22 Wyllian
Esse E ai é uma entrada/saída bugada, já notifiquei o pessoal pelo fórum para resolverem estes testes problemáticos.
2012-05-31 19:16:51 Feeh
Alguem pode dar mais exemplos de entrada, ja coloquei os 2 do problema e ta tudo certo, inclusive esse da saida "E", ja tentei maior/igual, igual nos casos pra verificar a distancia, inclusive o tamanho das variaveis ja foi verificado, ja coloquei \n na saida e nada..alguem da uma ajuda? vlw
2012-05-31 19:05:03 Matheus Flauzino [UNIS-MG]
Valew!!!
2012-05-31 18:21:09 Álvaro Tavares de Oliveira
Entrada
0

Saída
E
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.