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 
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;
}
Input
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
2 2
Teste 2
3 8
Teste 3
nenhum