PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra
DIFFICULTY:
728
PREREQUISITES:
None
PROBLEM:
There are two problems in a contest.
- Problem
A
is worth 500 points. - Problem
B
is worth 1000 points.
Once the contest starts, after each minute:
- Maximum points of Problem
A
reduce by 2 points . - Maximum points of Problem
B
reduce by 4 points.
It is known that Chef requires X minutes to solve Problem A
and Y minutes to solve Problem B
.
Find the maximum number of points Chef can score if he optimally decides the order of attempting both the problems.
EXPLANATION:
Let us define a function as f(n,t,d), where n is the points of that problem, t is the time taken to solve the problem and d as the deduction in points per minute for that problem. Then we can define it as:
Now we have two choices, i.e to either solve problem A first then problem B or vice versa. The score for first case would be:
and for the second case would be:
Our answer would be the maximum of the two scores.
TIME COMPLEXITY:
O(1), for each test case
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution