Algorithm
Problem Name: beecrowd | 2551
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2551
New Record
By Ricardo Oliveira, UFPR 
Brazil
Timelimit: 1
The great Curitiban street marathon will occur in the next few days! Many athletes are training for the big day! Flávio is one of these athletes. He trains daily, hoping to be well placed in the marathon. He runs every morning on the streets near to his house.
His trainings are monitored by an app installed on his smartphone. After each training, Flávio knows both the duration and the distance he ran. With these information, he can determine his average speed in the training.
Flávio is really concerned about the evolution of his performance in his trainings, and, in particular, about the records of his average speed. Such record is beaten in some training when the average speed of that training is greater than all average speeds of the previous trainings. Help Flávio to determine in which trainings he beat his record.
Input
The input contains several test cases. The first line of each test case contains an integer N (1 ≤ N ≤ 30), the number of trainings. Consider that the trainings were done in days 1, 2,...,N. The next N lines describe the trainings. Line i (1 ≤ i ≤ N) contains two integers Ti and Di (1 ≤ Ti, Di ≤ 100), the duration of the training (in minutes) and the distance ran during it (in kilometers).
The input ends with end-of-file (EOF).
Output
For each test case, print a list of integers indicating the days in which the record was beaten. Each day must be printed in a single line. Print them in ascending order. Please notice that day 1 must always be printed.
| Input Sample | Output Sample |
|
3 |
1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
while(cin >> t){
float A[t];
for(int i = 1; i < = t; i++){
float a,b;
cin >> a >> b;
float m = b/a;
A[i-1] = m;
}
for(int i = 0; i < t; i++)
{
if(i == 0)
cout << 1 << endl;
else{
bool x = false;
for(int j = 0; j < i; j++)
{
if(A[i] < = A[j]){ x = true; break;}
}
if(!x>
cout << i+1 << endl; }
}
}
return 0;
}
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
import java.util.Scanner;
import java.util.Locale;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
sc.useLocale(Locale.ENGLISH);
Locale.setDefault(new Locale("en", "US"));
while (sc.hasNext()) {
int N = sc.nextInt(); //num de treinos feitos
double R = 0; //para calcular o record
for (int i = 1 ; i < = N ; i++) {
Double T = sc.nextDouble(); //duracao do treino
Double D = sc.nextDouble(); //distancia percorrida no treino
if (D/T > R) {
System.out.println(i);;
R = D/T;
}
}
}
sc.close();
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');
let record = 0;
while(lines.length != 0){
const number = parseInt(lines.shift());
for(let i = 1; i < = number; i++){
let [a, b] = lines.shift().split(" ");
if(i == 1){
console.log(i);
record = b / a;
}
if((b / a) > record){
console.log(i);
record = b / a;
}
}
if(lines.length == 1){
break;
}
record = 0;
}
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
while True:
try:
n = int(input())
treino = []
recorde = []
while n:
n -= 1
treino.append([int(x) for x in input().split()])
if len(treino) == 1:
media = treino[0][1]/treino[0][0]
recorde.append(1)
else:
if treino[-1][1] / treino[-1][0] > media:
media = treino[-1][1] / treino[-1][0]
recorde.append(1)
else:
recorde.append(0)
for i in range(len(recorde)):
if recorde[i] == 1:
print(i + 1)
except EOFError:
break
Input
Output