Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1125
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1125
Formula 1
Maratona de Programação da SBC Brazil
Timelimit: 1
The Formula 1 season consists of a series of races, known as Grand Prix, organized by the International Federation of Automobile (FIA). The results of each Grand Prix are combined to determine Pilots\' World Championship. More specifically, for each race some points are distributed to pilots, depending on their classification in the race. At the end of the season, the pilot who has earned the most points is declared the World Champion.
Formula 1 organizers change constantly the competition rules, aiming to provide more excitement to fans. One rule modified for the 2010 season was the distribution of points in each Grand Prix. Since 2003, the scoring rule rewarded the top eight pilots, according to the following table:
That is, the winning driver received 10 points, second place received 8 points, and so on. In the 2010 season the top ten will receive points, obeying the following table:
The change in the scoring system led to much speculation about what would have been the effect to the World Championship in the past if the new score had been used. For example, would Lewis Hamilton have been champion in 2008, considering he and Felipe Massa were separated by just one point? To end the speculation, FIA hired you to write a program that, given the results of each race of a season determines the World Champion for different scoring systems.
Input
The input contains several test cases. The first line of a test case contains two integers G and P separated by a blank space, indicating the number of Grand Prix (1 ≤ G ≤ 100) and the number of pilots (1 ≤ P ≤ 100).. Pilots are identified by integers from 1 to P. Each of the following G lines indicates the result of a race, and contains Q integers separated by spaces. On each line, the (i)-th number indicates the order of arrival of pilot i in the race (the first number indicates the order of arrival of a pilot 1 in that race, the second number indicates the order of arrival of pilot 2 in that race and so on). The next line contains a single integer S indicating the number of scoring systems (1 ≤ S ≤ 10), After that, each of the following lines S contains a description of a scoring system. The description of a scoring system begins with an integerK (1 ≤ K ≤ P), indicating the last finishing order to receive points, followed by a blank space, followed by e K integers k0, k1, ... , kn−1 (1 ≤ ki ≤ 100) separated by spaces, indicating the number of points to be assigned (the first integer indicates the points for first place, the second integer indicates the points for second place and so on). The last test case is followed by a line containing only two zeros separated by a blank space.
Output
For each scoring system in the input your program must print one line, containing the identifier of the World Champion. If more than one pilot are World Champions (ie, if there is a tie), the line must contain all World Champions, in increasing order of identifier, separated by a space.
Input Sample | Output Sample |
1 3 |
3 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#define true 1
#define false 0
#define MAXSIZE 105
#define INF 0x3f3f
typedef unsigned short us;
int main (void)
{
us g, p, i, j, k;
us grid[MAXSIZE][MAXSIZE], pointS[MAXSIZE], pontos[MAXSIZE];
while (scanf("%hu %hu", &g, &p), g)
{
for (i = 0; i < g; ++i)
for (j = 0; j < p; ++j)
scanf("%hu", &grid[i][j]);
us _system;
scanf("%hu", &_system);
while (_system--)
{
memset(pontos, 0, sizeof(pontos));
memset(pointS, 0, sizeof(pointS));
scanf("%hu", &k);
for (i = 0; i < k; ++i)
scanf("%hu", &pointS[i]);
for (i = 0; i < g; ++i)
for (j = 0; j < p; ++j)
pontos[j] += pointS[grid[i][j] - 1];
us maior = 0;
for (i = 0; i < p; ++i)
if (pontos[i] > maior)
maior = pontos[i];
_Bool flag = true;
for (i = 0; i < p; ++i)
if (pontos[i] == maior)
if (flag)
printf("%hu", i + 1), flag = false;
else
printf(" %hu", i + 1);
printf("\n");
}
}
}
Copy The Code &
Try With Live Editor
Input
3 2 1
3
3 5 3 2
3 5 3 1
3 1 1 1
3 10
1 2 3 4 5 6 7 8 9 10
10 1 2 3 4 5 6 7 8 9
9 10 1 2 3 4 5 6 7 8
2
5 5 4 3 2 1
3 10 5 1
2 4
1 3 4 2
4 1 3 2
2
3 3 2 1
3 5 4 2
0 0
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <cstring>
using namespace std;
int g, p, s, k;
int corrida[101][101], sistema[101], ponto[101];
int main()
{
int m;
while(scanf("%i %i", &g, &p) && (g || p))
{
for (int i = 0; i < g; ++i)
{
for (int j = 0; j < p; ++j)
{
scanf("%i", &corrida[i][j]);
}
}
scanf("%i", &s);
while(s--)
{
memset(ponto, 0, sizeof(ponto));
memset(sistema, 0, sizeof(sistema));
scanf("%i", &k);
for (int i = 0; i < k; ++i)
scanf("%i", &sistema[i]);
for (int i = 0; i < g; ++i)
{
for (int j = 0; j < p; ++j)
{
ponto[j] += sistema[corrida[i][j]-1];
}
}
m = 0;
for (int i = 0; i < p; ++i)
if( ponto[i] > m)
m = ponto[i];
bool f = true;
for (int i = 0; i < p; ++i)
{
if(ponto[i] == m){
if(f){
printf("%d", i + 1);
f = false;
}else{
printf(" %d", i + 1);
}
}
}
printf("\n">;
}
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
3 2 1
3
3 5 3 2
3 5 3 1
3 1 1 1
3 10
1 2 3 4 5 6 7 8 9 10
10 1 2 3 4 5 6 7 8 9
9 10 1 2 3 4 5 6 7 8
2
5 5 4 3 2 1
3 10 5 1
2 4
1 3 4 2
4 1 3 2
2
3 3 2 1
3 5 4 2
0 0
Output
3
1 2 3
3
3
2 4
4