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 
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 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);
}
}
Input
PlanetaXYZ 2014 5
PlanetaDosMacacos 2020 7
JINQEWIOSDFaa 2043 20
2
PlanetaA 2050 10
PlanetaB 2055 16
0
Output
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;
}
Input
PlanetaXYZ 2014 5
PlanetaDosMacacos 2020 7
JINQEWIOSDFaa 2043 20
2
PlanetaA 2050 10
PlanetaB 2055 16
0
Output
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)
Input
PlanetaXYZ 2014 5
PlanetaDosMacacos 2020 7
JINQEWIOSDFaa 2043 20
2
PlanetaA 2050 10
PlanetaB 2055 16
0
Output
PlanetaB