DIWALI1 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greedy

PROBLEM:

Given a budget of P rupees, you may buy the following items (any number of times):

  • Fuljhari for a rupees,
  • Anar for b rupees,
  • Chakri for c rupees

To light up a Anar, you require x Fuljihari’s. To light up a Chakri, you require y Fuljihari’s. Determine the maximum total of Anar and Chakri’s that you can light up.

EXPLANATION:

Since we require x Fuljihari’s to light up a Anar, the total cost to buy and light up an Anar is equal to b+x*a. Similarly, the total cost to buy and light up a Chakri is equal to c+y*a.

Since we are only interested in lighting up the maximum total number of Anar’s and Chakri’s, we use a greedy strategy and only buy the firecracker with a cheaper total cost.
So, we spend \min (b+x*a, c+y*a) per lit firecracker. Since we have a budget of P rupees, the maximum total number of firecrackers we can light up using this strategy is equal to

\lfloor P/\min (b+x*a, c+y*a) \rfloor

(where \lfloor x \rfloor equals the largest integer less than x).

TIME COMPLEXITY:

O(1)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here.

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2

Can somebody please explain why this doesn’t pass: CodeChef: Practical coding for everyone

3
4

Hi!

My understanding is that ax or, ay can result in an overflow (10e9 * 10e9), and thus, anar and chakri cost’s are evaluated incorrectly.

1 Like