Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1515

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

Hello Galaxy

 

By Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 1

Currently, at the year 2114, the knowledge that we are not alone in the universe is not any news, but one century before it was yet a mystery. Several civilizations in the Milky Way had already sent some kind of signal proving their existence, and others even established an open contact with Earth in search of informations about such Hexagonary Tree (after all, we are at 2114).

Rafael is very interested in this subject, and in a school work he undertook the challenge of finding out which was the first civilization that sent a Hello Galaxy to all the galaxy. Hello Galaxy is nothing more than the first step of the Milky Way Society Iniciation Protocol, MWSIP, ensuring them to get in touch when they need.

The Hello Galaxy brings two kinds of information with it: the text “Hello Galaxy”, as says the tradition, and the name of the planet of the civilization that sent the message. The MWSMC, Milk Way Society Monitoring Center, installed, for some reason, in Earth, receive such messages, saving in a record the year the message was received and the amount of years that such message took to get in there.

Rafael's task is as follows: find out who was the first civilization to send a Hello Galaxy message.

 

Input

 

There will be several test cases.

Each test case starts with an integer N (1 ≤ N ≤ 100), that indicates how many Hello Galaxy messages were collected by Rafael at his research.

Following there will be N lines, each containing one message. Each message is represented by the name of the civilization's planet, containing between 1 and 50 characters (only letters), and two integers A and T (2014 ≤ A ≤ 2113, 1 ≤ T ≤ 1000), representing, respectivelly, the year that message was received at Earth, and the amount of years that such message took to travel between the source's planet to Earth.

The last test case is indicated when N = 0, which should not be processed.

 

Output

 

For each test case, there must be printed one line, containing the name of the first civilization's planet to send a Hello Galaxy message. One could assume that there will be no ties.

 

 

 

Sample Input Sample Output

3
PlanetaXYZ 2014 5
PlanetaDosMacacos 2020 7
JINQEWIOSDFaa 2043 20
2
PlanetaA 2050 10
PlanetaB 2055 16
0

PlanetaXYZ
PlanetaB

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


typedef struct{

	char planetas[51];
	unsigned short anosGastos;

} string;

#include <stdio.h>
#include <stdbool.h>

int main (void)
{

	unsigned short i, aux, ano, anos;
	unsigned short menor, posiMenor, casos;

	while (true)
	{
		scanf(" %hu", &casos);

		if (casos == 0)
			break;

		aux = casos;
		// Vetor do tipo string;
		string nomePlaneta[aux];

		i = 0;
		while (casos--)
		{

			scanf(" %s %hu %hu", nomePlaneta[i].planetas, &ano, &anos);
			// O ano de chegada menos a quantidade de anos que levou para chegar
			// Nos dá o ano original em que a mensagem foi enviada;
			// Usaremos esse resultado para comparação mais adiante;
			nomePlaneta[i].anosGastos = (ano - anos);
			i++;

		}

		menor = nomePlaneta[0].anosGastos;
		posiMenor = 0;

		for (i = 1; i  <  aux; i++)
		{
			// Se quem está na posição atual é menor do que o 'menor'
			// Então eu salvo esse novo menor e sua posição;
			if (nomePlaneta[i].anosGastos  <  menor)
			{	
				menor = nomePlaneta[i].anosGastos;
				posiMenor = i;

			}
		}

		printf("%s\n", nomePlaneta[posiMenor].planetas);		
	}
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
PlanetaXYZ 2014 5
PlanetaDosMacacos 2020 7
JINQEWIOSDFaa 2043 20
2
PlanetaA 2050 10
PlanetaB 2055 16
0

Output

x
+
cmd
PlanetaXYZ
PlanetaB

#2 Code Example with C++ Programming

Code - C++ Programming


#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define mp make_pair
#define pb push_back
#define MAXV 200100

using namespace std;

typedef vector<int> vi;
typedef pair < int, int> ii;
typedef long long int64;

typedef pair < int, string> is;

int main()
{
    ios::sync_with_stdio(false);
    int n, y, t;
    string s;
    while (cin >> n && n) {
        priority_queue < is> pq;
        while (n--) {
            cin >> s >> y >> t;
            pq.push(mp(-(y - t), s));
        }
        cout << pq.top().second << endl;
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
PlanetaXYZ 2014 5
PlanetaDosMacacos 2020 7
JINQEWIOSDFaa 2043 20
2
PlanetaA 2050 10
PlanetaB 2055 16
0

Output

x
+
cmd
PlanetaXYZ
PlanetaB

#3 Code Example with Python Programming

Code - Python Programming


while True:
    n = int(input())
    if n == 0: break
    for q in range(n):
        e = str(input()).split()
        nome = e[0]
        ano = int(e[1])
        dif = int(e[2])
        if q == 0:
            menor = ano - dif
            ganha = nome
        if menor > ano - dif:
            menor = ano - dif
            ganha = nome
    print(ganha)
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
PlanetaXYZ 2014 5
PlanetaDosMacacos 2020 7
JINQEWIOSDFaa 2043 20
2
PlanetaA 2050 10
PlanetaB 2055 16
0

Output

x
+
cmd
PlanetaXYZ
PlanetaB
Advertisements

Demonstration


Previous
#1514 Beecrowd Online Judge Solution 1514 Contest Solution in C, C++, Java, Js and Python
Next
#1521 Beecrowd Online Judge Solution 1521 The Guilty Solution in C, C++, Java, Js and Python