Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2248
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2248
Internship
By OBI - Olimpíada Brasileira de Informática 2003 
Brazil
Timelimit: 1
You got an internship to work as a programmer in the office of your school. As a first task, Dona Vilma, the coordinator, asked you to enhance a program that was developed by the former trainee. This program has as input a list of names and final average of students in a class, and provides the student with the highest average in the class. Dona Vilma want to use the program to reward the best student from each school class. The program developed by the former intern is on the following pages (Pascal program on page 5, C program on page 6, C ++ program on page 7).
As you can see, the program in its current form has a flaw: if there tied students with the best average in the class, it prints only the first student that appears in the list.
Dona Vilma wants you to change the program so that it produces a list of all students in the class who have obtained the highest average, and not just one. Can you help her in this task?
Input
The input consists of several test sets, representing several classes. The first line of a set of tests contains an integer number N (1 ≤ N ≤ 1000) indicating the total number of students in the class. The N following lines contain, each, a pair of integers C (1 ≤ C ≤ 20000) and M (0 ≤ M ≤ 100), respectively indicating the code and the average of a student. The end of input is indicated by a class with N = 0.
Output
For each entry in the class your program should produce three lines in the output. The first line should contain a test set identifier in the format "Turma n", where n is numbered from 1. The second line should contain the codes of the students who obtained the highest average in the class. The students of codes must appear in the same order of entry, and each must be followed by a blank space. The third line should be left blank. The format shown in no the sample output below should be followed strictly.
| Input Sample | Output Sample |
|
3 1 85 2 91 3 73 5 12300 81 12601 99 15023 76 10111 99 212 99 0 |
Turma 1 2 Turma 2 12601 10111 212 |
Code Examples
#1 Code Example with C++ Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define MAX 1100
typedef struct aluno{
unsigned short id;
char media;
} aluno;
aluno turma[MAX];
int main (void)
{
unsigned short i, melhor;
unsigned short qtsAlunos, caso;
while (scanf("%hu", &qtsAlunos), qtsAlunos)
{
for (i = 0; i < qtsAlunos; ++i)
scanf("%hu %hhd", &turma[i].id, &turma[i].media);
melhor = 0;
for (i = 1; i < qtsAlunos; ++i)
if (turma[i].media > turma[melhor].media)
melhor = i;
printf("Turma %hu\n", ++caso);
for (i = 0; i < qtsAlunos; ++i)
if (turma[i].media == turma[melhor].media)
printf("%hu ", turma[i].id);
printf("\n\n");
}
}
Input
1 85
2 91
3 73
5
12300 81
12601 99
15023 76
10111 99
212 99
0
Output
2
Turma 2
12601 10111 212
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <iostream>
#include <queue>
#define endl '\n'
#define MAXN 10100
using namespace std;
typedef pair < int, int> ii;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, turma = 1;
while (cin >> n && n) {
queue < ii> fila;
fila.push(make_pair(-1, -1));
while (n--) {
int i, j;
cin >> i >> j;
if (j > fila.front().second) {
queue < ii> vazia;
vazia.push(make_pair(i, j));
swap(vazia, fila);
} else if (j == fila.front().second)
fila.push(make_pair(i, j));
}
cout << "Turma " << turma++ << endl;
while (!fila.empty()) {
cout << fila.front().first << ' ';
fila.pop();
}
cout << endl << endl;
}
return 0;
}
Input
1 85
2 91
3 73
5
12300 81
12601 99
15023 76
10111 99
212 99
0
Output
2
Turma 2
12601 10111 212