PROBLEM LINK:
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 Ai minutes to pick it from the ground and it will give Chef a profit of Bi 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).
