PROBLEM LINK:
Setter: jeevanjyot
Testers: tejas10p, rivalq
Editorialist: hrishik85
DIFFICULTY:
1187
PREREQUISITES:
None
PROBLEM:
Chef is very hungry. So, Chef goes to a shop selling burgers. The shop has 2 types of burgers:
- Normal burgers, which cost X rupees each
- Premium burgers, which cost Y rupees each (where Y \gt X)
Chef has R rupees. Chef wants to buy exactly N burgers. He also wants to maximize the number of premium burgers he buys. Determine the number of burgers of both types Chef must buy.
Output -1 if it is not possible for Chef to buy N burgers.
EXPLANATION:
The least amount that the Chef definitely needs is (X \times N). If R is less than this amount, we output -1
If the count of burgers purchased are x (normal burgers) and y (premium burgers), then we have the equation R \geq x \times X + y \times Y
R \geq (N - y) \times X + y \times Y
y \leq (R -(N\times X)) \div (Y-X)
Also - y \leq N
Once y is computed, we can output (N-y, y)
TIME COMPLEXITY:
Time complexity is O(1).
SOLUTION:
Editorialist's Solution
t=int(input())
for _ in range(t):
X,Y,N,R = map(int,input().split())
if (N*X)>R:
print(-1)
else:
#R=X*(N-y)+Y*y
y = min((R-N*X)//(Y-X),N)
x = N - y
print(x,y)