All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Eat Or Not?
Tag(s):

Data Structures, Easy

Problem
Editorial
Analytics

Our friend Monk has decided to go on a diet in order to improve his Eating Habits. One of his friends told him that Monk should eat a fixed amount of Vitamins, Carbs, Fats and Proteins daily in order to loose weight. Monk wants to strictly follow this regime.

There are $$N$$ fruits kept in Monk's Fridge. Each fruit contains a fixed amount of Vitamins, Carbs, Fats and Proteins. Now, Monk wants to know if upon selecting any subset of fruits from the fridge, the sum of their Vitamins, Carbs, Fats and Proteins is individually equal to their corresponding equivalent amount that Monk desires to eat. For example, if Monk selects Fruits $$i$$, $$j$$ and $$k$$, then the sum of the vitamins of these $$3$$ fruits should be equal to the amount of vitamins Monk wants to eat and so on for Carbs, Fats and Protiens as well.

If there exists such a subset to satisfy Monk's demands, print "YES"(without quotes), else print "NO"(without quotes).

Input Format:

The First line contains $$4$$ space separated integers denoting the amount of Vitamins, Carbs, Fats and Protiens that Monk desires to eat. The next line contains a single integer $$N$$ denoting the number of Fruits in Monk's Fridge. Each of the next $$N$$ lines contains $$4$$ space separated integers, where the $$i^{th}$$ line denotes the number of VItamins, Carbs, Fats and Proteins in the$$i^{th}$$ fruit.

Output Format:

Print the required answer on a single line

Constraints:

$$ 10 \le V_{des} ,C_{des}, P_{des}, F_{des} \le 1000 $$

$$ 1 \le N \le 20 $$

$$ 10 \le V[i],C[i],F[i],P[i] \le 1000$$,

where $$V[i],C[i],F[i],P[i]$$ denote the number of VItamins, Carbs,Fats and Proteins in the $$i^{th}$$ fruit respectively .

SAMPLE INPUT
100 100 100 100
4
50 50 50 50
50 50 50 50
50 50 50 50
50 50 50 50
SAMPLE OUTPUT
YES
Explanation

Here, selecting any two pairs of fruits shall lead to satisfaction of Monk's demands.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

ThoughtWorks

Challenge Name

Women Application Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications