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

SALDO - Saldo de gols

Hipólito é um torcedor fanático. Coleciona flâmulas, bandeiras, recortes de jornal, figurinhas de jogadores, camisetas e tudo o mais que se refira a seu time preferido. Quando ganhou um computador de presente em uma festa, resolveu montar um banco de dados com os resultados de todos os jogos de seu time ocorridos desde a sua fundação, em 1911. Depois de inseridos os dados, Hipólito começou a ficar curioso sobre estatísticas de desempenho do time. Por exemplo, ele deseja saber qual foi o período em que o seu time acumulou o maior saldo de gols. Como Hipólito tem o computador há muito pouco tempo, não sabe programar muito bem, e precisa de sua ajuda.

Tarefa

É dada uma lista, numerada seqüencialmente a partir de 1, com os resultados de todos os jogos do time (primeira partida: 3 x 0, segunda partida: 1 x 2, terceira partida: 0 x 5 ...). Sua tarefa é escrever um programa que determine em qual período o time conseguiu acumular o maior saldo de gols. Um período é definido pelos números de seqüência de duas partidas, A e B, onde A ≤ B. O saldo de gols acumulado entre A e B é dado pela soma dos gols marcados pelo time em todas as partidas realizadas entre A e B (incluindo as mesmas) menos a soma dos gols marcados pelos times adversários no período. Se houver mais de um período com o mesmo saldo de gols, escolha o maior período (ou seja, o período em que B - A é maior). Se ainda assim houver mais de uma solução possível, escolha qualquer uma delas como resposta.

Entrada

Seu programa deve ler vários conjuntos de teste. A primeira linha de um conjunto de teste contém um inteiro não negativo, N, que indica o número de partidas realizadas pelo time (o valor N = 0 indica o final da entrada). Seguem-se N linhas, cada uma contendo um par de números inteiros não negativos X e Y que representam o resultado da partida: X são os gols a favor e Y os gols contra o time de Hipólito. As partidas são numeradas sequencialmente a partir de 1, na ordem em que aparecem na entrada.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado a partir de 1. A segunda linha deve conter um par de inteiros I e J que indicam respectivamente a primeira e última partidas do melhor período, conforme determinado pelo seu programa, exceto quando o saldo de gols do melhor período for menor ou igual a zero; neste caso a segunda linha deve conter a expressão “nenhum”. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo

Entrada:
2
2 3
7 1
9
2 2
0 5
6 2
1 4
0 0
5 1
1 5
6 2
0 5
3
0 2
0 3
0 4
0

Saída:
Teste 1
2 2

Teste 2
3 8

Teste 3
nenhum

Restrições

0 ≤ N ≤ 10000 (N = 0 apenas para indicar o fim da entrada)
1 ≤ A ≤ N
A ≤ B ≤ N
0 ≤ X ≤ 50
0 ≤ Y ≤ 50


Adicionado por:Wanderley Guimarăes
Data:2006-04-19
Tempo limite:0.489s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2000

hide comments
2016-12-20 00:17:52
OFF: Hipólito é alemão!
2016-03-28 04:10:45 Elsio [UFABC]
É o algoritmo de Kadane. Só que, além da variável de controle (soma) vc também guarda ponteiros temporários pro início e fim do intervalo. Quando todas as condições forem satisfeitas vc passa os ponteiros temporários pros de resposta definitiva. Tem que ser assim pq vc precisa comparar resultados correntes com ótimos, então deixe eles em variáveis diferentes. Preste muita atenção e teste muitos casos pois o 'else if' que fecha o intervalo tem quatro condições.
2015-12-22 22:51:39
Pra galera q n ta dando talvez estejam fazendo o mesmo erro que eu.Se forem valores iguais deve-se colocar o MAIOR intervalo.
2015-09-29 23:42:22
talvez vc ta errando a parte de imprimir o nenhum, aconteceu comigo tbm, essa entrada dele passa de boa ai na hora q manda nao da certo, so mudei uma comparaçao no final e deu!
2015-04-13 15:04:24 Marcos Antonio de Souza Silva


Last edit: 2015-04-13 17:00:27
2013-05-02 18:24:00 Eduardo Nunes
Semelhante ao problema BAPOSTAS, com algumas adaptaçőes do algoritmo de Kadane ;-)
2013-04-14 19:39:31 Yves Medhard Tibe da Cunha Tibe-bi
Năo sei como funciona os testes do SPOJ mais testei no Ideone.com e o programa reproduz com total fidelidade o teste.. nem adaptando as condicionais como o Vinícius Thiengo disse ele deu como resultado correto (obs os resultados estăo corretos). Alguma dica?

Last edit: 2013-04-14 19:40:34
2012-07-19 23:40:31 Vinícius Thiengo [IFES]
Dica: Se vc estiver utilizando um condicional (similar, năo necessariamente igual) if(pro - contra > 0) e o resultado da certo em seus testes e errado no SPOJ, tente >= ao invés > apenas. Comigo funcionou.
2010-12-29 23:34:37 thiagojobson [UERN]
E eu năo prestei atençăo em que o problema pede o maior período em que o saldo foi o MÁXIMO, e năo o período em que o saldo foi positivo :P
2010-08-21 20:14:06 [ UERN - UFPB ] Thalles Robson
Só uma nota. Fiquei preso no problema um tempo pq năo prestei atençăo em um detalhe. Saldo de gols é (>0), se for 0 ou menor que zero, năo é saldo! O time é um Tabajara.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.