Diet Plan | TCS CodeVita 9 Solution ( Zone 1 ) 2020 | By CodingHumans |

Diet Plan
Problem Description

Arnold is planning to follow a diet suggested by his Nutritionist. The Nutritionist prescribed him the total protein, carbohydrates and fats, he should take daily. Arnold searches on an online food store and makes a list of protein, carbohydrates and fats contained in a single unit of various food items.

His target is to have the maximum protein, carbohydrates and fats in his diet without exceeding the prescribed limit. He also wants to have as much diverse food items as much as possible. That is, he does not want to have many units of one food item and 0 of others. Multiple combinations of 'units of food items' are possible to achieve the target. Mathematically speaking, diversity is more if the difference between the number of units of food item chosen the most and the number of units of another food item chosen the least, is as small as possible.

To solve this problem, he uses maximum possible number of units of all the items so that total amount of protein, carbohydrates and fats is not more than prescribed limit. For example - if total nutrition required is 100P, 130C and 130F (where P is Protein, C is Carbohydrates and F is Fats) and 2 different food items, viz. Item A and Item B, have following amount of nutrition:

Item A - 10P, 20C, 30F

Item B - 20P, 30C, 20F

then, he can have (maximum possible) 2 units of all the items as having 3 units will exceed the prescribed amount of Carbohydrates and fats.

Next, he chooses food items to fulfill the remaining nutrients. He chooses one more units of maximum number of food items. He continues this process till he cannot add a unit of any food item to his diet without exceeding the prescribed limit. In this example, he can choose one more unit of item B or one more unit of item A. In case he has two sets of food items then the priority is given to fulfill the requirements of Protein, Carbohydrates, and Fats in that order. So he chooses item B.

You will be provided the maximum nutrients required and the nutrients available in various food items. You need to find the amount of nutrients for which there is a shortfall as compared to the prescription, after making his selection using the process described above. In the example he still needs 20P, 0C, 10F to achieve his target.

Constraints

Number of Food Items <= 10

Maximum amount of Nutrients is less than 1500 i.e. x +y + z <= 1500

Amount of P, C, F in two food items will not be same

P, C, F values in input can be in any order

Output should be in order - P, C, F.

Input

First line contains the maximum limit of nutrients in the following format.

xP yC zF, where x, y and z are integers

Second line contains nutrient composition of different food items separated by pipe (|).
Output

Print the shortfall for each nutrient type, fulfilled separated by space.

E.g. If the output is 10P, 20 C, 30 F, then print "10 20 30" (without quotes).

Time Limit

1

Examples

Example 1

Input

100P 130C 130F

10P 20C 30F|20P 30C 20F

Output

20 0 10

Explanation

Having 2 units of item A and 3 units of item B provides - 2 * [10P 20C 30F] + 3 * [20P 30C 20F] = 100P, 130C, 120F. This is the best combination that can reduce the shortfall [20P, 0C, 10F] without exceeding his prescription. In contrast, if 3 units of A and 2 units of B are chosen then 3 * [10P 20C 30F] + 2 * [20P 30C 20F] = 70P, 120C, 130F produces a shortfall of [30P, 10C, 0F]. However, since protein shortfall in this case is more than the previous combination, this is not the right combination to follow.

Example 2

Input

130P 120C 110F

4P 9C 2F|4P 3C 2F|7P 1C 3F

Output

2 4 50

Explanation

Having 9 units of item A, 9 units of item B and 8 units of Item C provides - 9 * [4P 9C 2F] + 9 * [4P 3C 2F] + 8 * [7P 1C 3F] = 108P, 116C, 60F. This is the best combination that can reduce the shortfall [2P, 4C, 50F] without exceeding his prescription.

Recommended: Please try your approach on your integrated development environment (IDE) first, before moving on to the solution.

Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.

HAPPY CODING 😁

Solution 

( C ++ )

#include<bits/stdc++.h>
using namespace std;
typedef  long long  ll;
ll inf=1000000000000000000,mod=1000000007,BS,k;
#define en printf("\n");
int main(){
        string a,b;
        getline(cin,a);int res=0,p,c,f,a_len,b_len;
        a_len=a.length();
        for(int i=0;i<a_len;i++){
            if(a[i]==' ')continue;
            if(isdigit(a[i])){
                res=res*10+a[i]-'0';
            }
            else{
                if(a[i]=='P')
                p=res;
                else if(a[i]=='C')
                c=res;
                else
                f=res;
                res=0;
            }
        }
        getline(cin,b);int pp,cc,ff;
        vector<pair<int,pair<int,int>>>ans;res=0;
        int mi=INT_MAX,sump=0,sumc=0,sumf=0;
        b_len=b.length();
        for(int i=0;i<b_len;i++){
            if(b[i]==' ')continue;
            if(b[i]=='|'){
                ans.push_back({pp,{cc,ff}});
                pp=0;ff=0;cc=0;
            }
            if(isdigit(b[i])){
                res=res*10+b[i]-'0';
            }
            else{
                if(b[i]=='P')
                pp=res,sump+=pp;
                else if(b[i]=='C')
                cc=res,sumc+=cc;
                else
                ff=res,sumf+=ff;
                res=0;
            }
        }ans.push_back({pp,{cc,ff}});
        if(sump)
        mi=min(mi,p/sump);
        if(sumc)
        mi=min(mi,c/sumc);
        if(sumf)
        mi=min(mi,f/sumf);
        if(mi==INT_MAX)mi=0;
        int nn=ans.size();
        pair<int,pair<int,int>>lef,ma={0,{0,0}},curr;
        // cout<<p<<" "<<c<<" "<<f;
        lef={p-mi*sump,{c-mi*sumc,f-mi*sumf}};
        // cout<<lef.first<<" "<<lef.second.first<<" "<<lef.second.second;
        for(int i=0;i<(1<<nn);i++){
            curr={0,{0,0}};
            for(int j=0;j<nn;j++){
                if(i&(1<<j))
                {
                    curr.first+=ans[j].first;
                    curr.second.first+=ans[j].second.first;
                    curr.second.second+=ans[j].second.second;
                }
            }
            if(curr.first<=lef.first&&curr.second.first<=lef.second.first&&curr.second.second<=lef.second.second)
            ma=max(ma,curr);
        }
        cout<<p-sump*mi-ma.first<<" "<<c-sumc*mi-ma.second.first<<" "<<f-sumf*mi-ma.second.second<<endl;
    return 0;
}

If you have any doubts regarding this problem or  need the solution in other programming languages then leave a comment down below .