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