 SIMPLE

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

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

Can somebody please explain why this doesn’t pass: Solution: 51645774 | CodeChef

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