Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2191

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2191

Goal Difference

 

By OBI - Olimpíada Brasileira de Informática 2000 BR Brazil

Timelimit: 1

Hippolytus is a fanatical fan. Collects streamers, flags, newspaper clippings, figurines of players, shirts and everything else that relates to his favorite team. When he won this one computer at a party, decided to set up a database with the results of every game of his team occurred since its founding in 1911. After the data entered, Hipólito started to get curious about performance statistics of team. For example, he wants to know what was the period when his team has accumulated the highest goal difference. As Hippolytus has the computer very recently, he does not know to program very well, and needs your help.

It's given a list, numbered sequentially from 1, with the results of all team games (first game: 3 x 0, second game: 1 x 2, third match: 0 x 5 ...) is given. Your task is to write a program to determine in which period the team managed to accumulate the highest goal difference. A period is defined by two matches sequence numbers, A and B (A ≤ B ≤ N). The balance of accumulated goals between A and B is the sum of the goals scored by the team in all matches played between A and B (including the same) minus the sum of the goals scored by the opposing teams in the period. If there is more than one period with the same goal difference, select the longest period (ie the period in which B - is greater). If there is still more than one possible solution, choose any one of them in response.

 

Input

 

Your program should read multiple test sets. The first line of a test set contains a non-negative integer, N (0 ≤ N ≤ 10000), that indicates the number of matches played by the team (the value N = 0 indicates the end of the input). It follows N lines, each one containing a pair of non-negative integer numbers X e Y (0 ≤ X,Y ≤ 50) representing the result of the match: X are the goals for and Y the goals against the team of Hippolytus. The matches are numbered sequentially from 1, in the order they appear in the entry. 

 

Output

 

For each entry test set your program should produce three lines in the output. The first line should contain a test set identifier in the format "Teste n”, where n is numbered from 1. The second line must contain a pair of integers I e J which respectively indicate the first and last matches of the best period, as determined by your program, except when the goal difference of the best period is less than or equal to zero; in this case the second line should contain the word "nenhum". The third line should be left blank. The spelling shown in Example output below should be followed strictly.

 

 

 

Input Sample Output Sample

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

Teste 1

2 2


Teste 2

3 8


Teste 3

nenhum

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#define max(A, B) (A > B) ? (A) : (B)
int main() {
    int n, teste = 1;
    while (scanf("%d", &n) && n) {
        int saldo_maximo = 0, saldo = 0, inicio = 0, primeiro = 0, ultimo = 0;
        printf("Teste %d\n", teste++);
        for (int contador = 0; contador  <  n; contador++) {
            int x, y;
            scanf("%d %d", &x, &y);
            saldo += (x - y);
            if (saldo >= 0) {
                if (saldo > saldo_maximo ||
                    (saldo == saldo_maximo &&
                     ultimo - primeiro  <  contador - inicio)) {
                    saldo_maximo = saldo;
                    primeiro = inicio + 1;
                    ultimo = contador + 1;
                }
            } else {
                saldo = 0;
                inicio = contador + 1;
            }
        }
        if (!saldo_maximo)
            printf("nenhum\n\n");
        else
            printf("%d %d\n\n", primeiro, ultimo);
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

Output

x
+
cmd
Teste 1
2 2

Teste 2
3 8

Teste 3
nenhum
Advertisements

Demonstration


Previous
#2189 Beecrowd Online Judge Solution 2189 Kermesse Solution in C, C++, Java, Js and Python
Next
#2203 Beecrowd Online Judge Solution 2203 Crowstorm Solution in C, C++, Java, Js and Python