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.|

TRILHAS - Trilhas

Nos finais de semana Paulo faz longas caminhadas pelas bonitas trilhas que atravessam as matas vizinhas à sua cidade. Recentemente Paulo adquiriu um aparelho de GPS (siglas do inglês Sistema de Posicionamento Global) e com ele mapeou as mais belas trilhas da região. Paulo programou o GPS para armazenar, a intervalos regulares, a altitude do ponto corrente durante o trajeto. Assim, após percorrer as trilhas com o seu GPS, Paulo tem informações que permitem por exemplo produzir gráficos como os abaixo:

Paulo tem uma nova namorada, e quer convencê-la a passear junto com ele pelas trilhas. Para o primeiro passeio juntos, Paulo quer escolher uma trilha “fácil”. Segundo o seu critério, a trilha mais fácil é a que, em um dos sentidos do percurso, exige o menor esforço de subida. O esforço exigido em um trecho de subida é proporcional ao desnível do trecho.

Tarefa

Dadas as informações colhidas por Paulo sobre distâncias e altitudes de um conjunto de trilhas, você deve escrever um programa que determine qual é a trilha que exige o menor esforço de subida.

Entrada

A primeira linha da entrada contém um número inteiro N que indica o número de trilhas. Cada uma das N linhas seguintes contém a descrição de uma trilha (1 <= N <= 100). As trilhas são identificadas por números de 1 a N. A ordem em que as trilhas aparecem na entrada determina os seus identificadores (a primeira trilha é a de número 1, a segunda a de número 2, a última a de número N). A descrição de uma trilha inicia com um número inteiro M que indica a quantidade de pontos de medição da trilha (2 <= M <= 1000), seguido de M números inteiros Hi representando a altura dos pontos da trilha (medidos a intervalos regulares e iguais para todas as linhas). Paulo pode percorrer a trilha em qualquer sentido (ou seja, partindo do ponto de altitude H1 em direção ao ponto de altitude HM, ou partindo do ponto de altitude HM em direção ao ponto de altitude H1).

Saída

Seu programa deve produzir uma unica linha na saída, contendo um número inteiro representando o identificador da melhor trilha, conforme determinado pelo seu programa. Em caso de empate entre duas ou mais trilhas, imprima a de menor identificador.

Exemplo 1

Entrada:
5
4 498 500 498 498
10 60 60 70 70 70 70 80 90 90 100
5 200 190 180 170 160
2 1000 900
4 20 20 20 20

Saída:
2

Exemplo 2

Entrada:
3
5 600 601 600 601 600
4 500 499 500 499
4 300 300 302 300

Saída:
2

Restrições

1 <= N <= 100
2 <= M <= 1000
0 <= Hi <= 1000


Adicionado por:Wanderley Guimarăes
Data:2008-04-02
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Olimpíada Brasileira de Informática 2005 -- Programação Nível 1

hide comments
2017-03-15 03:18:52
Quais são os outros possíveis casos de testes? Tentei arrumar para caso só haja uma trilha (com e sem desnível), mas continua dando wrong answer :(
2011-10-22 23:20:19 thiagojobson [UERN]
@David, @Rafael
Mas acho que o motivo eh porque a trilha 2 veio antes. Pois ambas tem o mesmo esforço de subida (0).
2011-05-28 01:38:13 Rafael Perrella
Está correto, pois "a trilha mais fácil é a que, em um dos sentidos do percurso ...", ou seja, também é possível ir no sentido oposto. Assim, a trilha 2 só tem descidas.
2011-03-27 20:31:33 David Kennedy Souza Araújo [PUC-GO]
Creio que o exemplo 1 esta incorreto pois a tilha 2 tem desniveis proporcionais de 10 enquanto a ultima trilha nem possui desniveis.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.