# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

SIMPLE

# PREREQUISITES:

# 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

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

# TIME COMPLEXITY:

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