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 BR 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");

	}

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
1 85
2 91
3 73
5
12300 81
12601 99
15023 76
10111 99
212 99
0

Output

x
+
cmd
Turma 1
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;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
1 85
2 91
3 73
5
12300 81
12601 99
15023 76
10111 99
212 99
0

Output

x
+
cmd
Turma 1
2

Turma 2
12601 10111 212
Advertisements

Demonstration


Previous
#2247 Beecrowd Online Judge Solution 2247 Grandma Vitória's Piggy Banks Solution in C, C++, Java, Js and Python
Next
#2249 Beecrowd Online Judge Solution 2249 Erdos Number Solution in C, C++, Java, Js and Python