# New Year’s Resolution – Facebook Hacker Cup 2015 Qualification Round

### Facebook Hacker Cup 2015 Qualification Round

#### New Year’s Resolution Solution in C++

Alex’s New Year’s resolution for 2015 is to eat healthier foods. He’s done some research and has found out that calories come from three main sources, called macronutrients: protein, carbohydrates, and fat. Alex wants to get the right balance of protein, carbohydrates, and fat to have a balanced diet. For each available food, Alex can only choose to eat it or not eat it. He can’t eat a certain food more than once, and he can’t eat a fractional amount of a food.

Input
Input begins with an integer T, the number of test cases. For each test case, the first line consists of three space-separated integers: GP, GC, and GF, which represent the amount of protein, carbohydrates, and fat that Alex wants to eat. The next line has the number of foods for that test case, an integer N. The next N lines each consist of three space-separated integers: P, C, and F, which represent the amount of protein, carbohydrates, and fat in that food, respectively.

Output
For each test case i, print a line containing “Case #i: ” followed by either “yes” if it is possible for Alex to eat the exact amount of each macronutrient, or “no” if it is not possible.

Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 20
10 ≤ GP, GC, GF ≤ 1000
10 ≤ P, C, F ≤ 1000

Those who unlike after download!, Your FB account will be banned from future downloads from the site!

```#include <cstdio>
#include <vector>
using namespace std;

struct Nutrition {
int p, c, f;
};

int gp, gc, gf;

bool f(vector<Nutrition>& Nutritions, int eaten, int sump, int sumc, int sumf)
{
if (sump > gp || sumc > gc || sumf > gf) return false;
if (sump == gp && sumc == gc  && sumf == gf) return true;
if (eaten == ((1 << Nutritions.size()) - 1)) return false;

for (int next = 0; next < Nutritions.size(); ++next)
{
if (eaten & (1 << next)) continue;
if (f(Nutritions, eaten + (1 << next), sump + Nutritions[next].p, sumc + Nutritions[next].c, sumf + Nutritions[next].f))
return true;
}
return false;
}

int main()    /*  HIT LIKE TO DOWNLOAD ENTIRE SOURCE CODE */
{
FILE *in = fopen("new_years_resolution.txt", "r");
FILE *out = fopen("output.txt", "w");

int T;
fscanf(in, "%d", &T);
for (int t = 1; t <= T; ++t)
{
vector<Nutrition> Nutritions;
int sump = 0, sumc = 0, sumf = 0;
int n;
fscanf(in, "%d %d %d %d", &gp, &gc, &gf, &n);
for (int i = 0; i < n; ++i)
{
Nutrition input;
fscanf(in, "%d %d %d", &input.p, &input.c, &input.f);

if (input.p <= gp && input.c <= gc && input.f <= gf)
Nutritions.push_back(input);
}

/*  HIT LIKE TO DOWNLOAD ENTIRE SOURCE CODE */