HUNGRY - EDITORIAL

PROBLEM LINK:

Contest
Practice

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=" ")