×

CHEFSTON - Editorial

Author: Dmytro Berezin
Editorialist: Lalit Kundu

CAKEWALK

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).

SOLUTIONS:

This question is marked "community wiki".

3.0k93163187
accept rate: 12%

19.7k350498541

@darkshadows: any idea why solution links are always broken? It happens each contest. That has to be some feature...

(12 Jan '15, 15:04)
1

they haven't been uploaded yet, that's why.

(12 Jan '15, 15:16)

(12 Jan '15, 15:16)

Thanks for an answer - also you swapped all contest/practice links (at least those I checked) ;-)

(12 Jan '15, 15:18)
1

that is fixed now.

(12 Jan '15, 16:08)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,491
×1,610
×204
×167
×9

question asked: 12 Jan '15, 15:02

question was seen: 4,699 times

last updated: 04 Feb '16, 20:17