CHEFSTON - Editorial

editorial
, , , ,
1

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

1 Like
2

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

3

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

1 Like
4

will be uploaded soon.

5

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

6

that is fixed now.

1 Like
7

Why my code isn’t working
#include <stdio.h>

int main(void) {
long long int t,n,k,a[100002],b[100002],i,max=0,d;
scanf("%lld",&t);
while(t–)
{
scanf("%lld %lld",&n,&k);
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
scanf("%lld",&b[i]);
}
for(i=0;i<n;i++)
{
d=(k/a[i])*b[i];

        if(d>max)
        {
            max=d;
        }
    }
    printf("%lld\n",max);
}

}

8

how we can say (k/x)*y ? is there any formula exist?
would someone elaborate to me ?

9

can somebody tell me the error

#include
#include
#include
#define endll “\n”
#define ll long long int
using namespace std;

int main()
{
int t;
cin >> t;
while ( t-- )
{
ll n, k, MAX=-1;
cin >> n >> k;
while( n-- )
{
ll a, b;
cin >> a >> b;
ll rem = k/a;
//cout<<rem<<" “;
ll val = rem*b;
//cout<<val<<” ";
if( val > MAX )
MAX = val;
}
cout << MAX << endll;

}
return 0;

}