PROBLEM LINK:
Practice
Contest
Author: Dmytro Berezin
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu
DIFFICULTY:
CAKEWALK
PRE-REQUISITES:
Basic Maths
PROBLEM:
There are total N kinds of stones. There is unlimited supply of each kind of stone.
Chef knows that one stone of kind i needs A_{i} minutes to pick it from the ground and it will give Chef a profit of B_{i} Rs.
Chef has K minutes of free time. During this free time, Chef want to pick stones so as to maximize his profit. But he can not pick stones of different kinds, he has to pick stones of a single kind. Please help Chef to find the maximal possible profit.
EXPLANATION:
We traverse over each kind of stone assuming that he will pick that kind of stone and calculate profit in that case.
So, if it takes x minutes to pick up one stone(which gives a profit of y), in K minutes, you will pick up K/x stones(note the division is integer division). So profit in such a case will be (K/x) * y.
Pseudo Code:
ans=-1
for i=1 to N:
ans = max(ans, (K/A[i])*B[i])
Note that we'll need to use 64-bit integers because of higher constraints.
Complexity: O(N).
SOLUTIONS:
Setter's solution
Tester's solution
asked
12 Jan '15, 15:02
5★darkshadows ♦
3.0k●93●163●187
accept rate:
12%
@darkshadows: any idea why solution links are always broken? It happens each contest. That has to be some feature...
they haven't been uploaded yet, that's why.
will be uploaded soon.
Thanks for an answer - also you swapped all contest/practice links (at least those I checked) ;-)
that is fixed now.