You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFSTON - Editorial

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 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:

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 12 Jan '15, 15:02

darkshadows's gravatar image

5★darkshadows ♦
3.0k93162187
accept rate: 12%

edited 04 Feb '16, 20:17

admin's gravatar image

0★admin ♦♦
19.1k348495534

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

(12 Jan '15, 15:04) betlista ♦♦3★
1

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

(12 Jan '15, 15:16) darkshadows ♦5★

will be uploaded soon.

(12 Jan '15, 15:16) darkshadows ♦5★

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

(12 Jan '15, 15:18) betlista ♦♦3★
1

that is fixed now.

(12 Jan '15, 16:08) darkshadows ♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,809
×1,481
×204
×167
×9

question asked: 12 Jan '15, 15:02

question was seen: 4,492 times

last updated: 04 Feb '16, 20:17