PROBLEM LINK:
Setter: Kevin J, Tanvi Deshpande
Tester: Hussain Pettiwala
DIFFICULTY
Easy
PROBLEM
Devansh is hungry and has been given X bucks to spend for his lunch. He decides to visit a restaurant but the problem is that due to COVID restrictions the restaurant is about to close its kitchen so he bribes the manager Y bucks to take one last order for him. The manager accepts the offer on the condition that Devansh can only order the food from the quantity they have left in the kitchen and they won’t be cooking anymore but also has the freedom to order food in fractional units i.e. if there is only 5 units of a food item available then Devansh can order 5, 4.33, 2.91, 0 or any other amount that he wishes to order. Now since Devansh is hungry he wants to place an order that can maximize his food occupancy on the plate, exhausting the amount of money he has left to spend. Devansh is also tempted to have garlic bread at the moment so he wishes to have at least 4 units of garlic bread (If there are N items on the menu, Garlic bread will be the first item on the menu). Devansh asks for help from you to tell him how many units of each food item he should buy.
EXPLANATION
X is the money Devansh has and Y is the amount of money he gives as a bribe. So Devansh is
left with X-Y rupees to pay for the food. Out of the leftover money, he buys 4 units of garlic
bread. With the remaining money, he buys the food. Use the fractional knapsack method to find
how much quantity of food available should he eat.
SOLUTIONS
Setter's Solution
def hungryboy(N, X, Y, Cost, Units):
# Bribery Case
Wallet = X - Y
# Garlic Bread Case
if Units[0] - 4 < 0 or Wallet - Cost[0] / Units[0] * 4 < 0:
print(-1)
else:
result = [0] * N
Wallet -= Cost[0] / Units[0] * 4
Cost[0] -= Cost[0] / Units[0] * 4
Units[0] -= 4
result[0] = 4
# Fractional Knapsack
temp = dict()
for i in range(N):
temp[i] = Units[i] / Cost[i]
temp = {
k: v
for k, v in sorted(temp.items(), key=lambda item: item[1], reverse=True)
}
for i in temp:
if Wallet - Cost[i] < 0:
result[i] += temp[i] * Wallet
break
else:
Wallet -= Cost[i]
result[i] += Units[i]
# Printing output
for index,i in enumerate(result):
if index == len(result)-1:
print("%.2f" % i)
else:
print("%.2f" % i, end=" ")
# Driver code
T = int(input())
for i in range(T):
N, X, Y = map(int, input().split(" "))
Cost = list(map(int, input().split(" ")))
Units = list(map(int, input().split(" ")))
hungryboy(N, X, Y, Cost, Units)
Tester's Solution
def fractional_knapsack(value, weight, capacity):
index = list(range(len(value)))
ratio = [v/w for v, w in zip(value, weight)]
if capacity <= 0 or value[0] <= 0:
return -1
index.sort(key=lambda i: ratio[i], reverse=True)
max_value = 0
fractions = [0]*len(value)
for i in index:
if weight[i] <= capacity:
fractions[i] = 1
max_value += value[i]
capacity -= weight[i]
else:
fractions[i] = round(capacity/weight[i], 2)
max_value += value[i]*capacity/weight[i]
break
return max_value, fractions
for x in range(int(input())):
n, X, Y = list(map(int, input().split()))
weight = list(map(int, input().split()))
weight = [int(w) for w in weight]
value = list(map(int, input().split()))
value = [int(v) for v in value]
temp = value
capacity = X - Y
max_value, fractions = fractional_knapsack(value, weight, capacity)
if fractions == -1:
print("-1")
continue
res = [fractions[i] * temp[i] for i in range(len(temp))]
if res[0] < 4:
print("-1")
else:
for index, item in enumerate(res):
if len(res) - 1 == index:
print("%.2f" % item)
else:
print("%.2f" % item, end=" ")