Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1896

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1896

It's Time to Duel!

 

By Caio Russi, UNOESTE BR Brazil

Timelimit: 1

Duel Monsters is the world's most famous Cards championship. Every duel is played by two players, where each player starts with 8000 Life Points and your Deck. Each card is a monster that has the attributes Attack, Defense and Skill. We are in the final duel with the two greatest duelists of history. On one side Charlinho, a boy who loves to study, but also know feel the heart of the cards. Across Gilmar, which was not created to milk with pear, but is recognized as the Master the Cards. It is the turn of Charlinho, and he has just combine their monsters on the table for the forbidden "Prassódia".

Prassódia is the strongest monster in the game, and when invoked the match is completed on time and the player who invoked wins the duel. To invoke Prassódia is necessary to combine two or more cards on the table by adding attack with attack, defense with defense and skill with skill for the Prassódia attributes informed at the beginning of the duel.

If a Card is chosen to be combined, the attributes of the card must be used in full, being invalid only use the attack or just use the defense or just the skill that card and still being able to use only a part of the attack and/or a part of defense and/or a part of skill. Gilmar is surprised for a moment, because he was the only one who could invoke Prassódia in history, but ends up doubting the move by Charlinho because there were several cards on the table, which would make such a very suspicious move. 

You are the judge of the duel and an excellent programmer was responsible for assessing whether the Charlinho actually managed to invoke or not Prassódia with the cards on the table.

 

Input

 

The first row entry contains 4 integers, the first integer n (1 ≤ N ≤ 20) represents the number of cards in the following table by three integers A, D, H (1 ≤ A, D, H, ≤ 1000) representing respectively the attack, defense and the exact skill to invoke Prassódia. Each of the following N lines represent a card of the table, where each row contains the attributes in the order X, Y, Z (1 ≤ X, Y, Z ≤ 50) attack, defense and skill respectively.

 

Output

 

The output should contain "Y" if Charlinho can hold a valid combination to invoke Prassódia or "N" otherwise.

 

 

 

Exemplo de Entrada Exemplo de Saída

2 5 20 10
8 10 7
9 10 3

N

 

 

 

3 13 9 15
7 6 5
6 3 10
5 9 15

Y

 

 

 

 

 

3 10 10 10
10 10 10
9 4 5
1 6 4

N

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>


using namespace std;
typedef long long ll;


struct carta
{
	int a, d, h;
	
	carta(){a = d = h = 0;}
	carta(int i, int j, int k) : a(i), d(j), h(k){}
	
	bool operator == (const carta &other) const
	{
		return a == other.a && d == other.d && h == other.h;
	}
};

carta v[25];

int main()
{
	int n, a, d, h;
	
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	carta prassodia;
	
	while (cin >> n)
	{
		cin >> a >> d >> h;
		prassodia = carta(a, d, h);
		
		for (int i = 0 ; i  <  n ; ++i)
		{
			cin >> a >> d >> h;
			v[i] = carta(a, d, h);
		}
		
		ll lim = (1L << n);
		int flag = 0;
		for (ll i = 3; i  <  lim; ++i)
		{
			if (!(i & (i - 1))) continue;
			a = d = h = 0;
			for (int j = 0 ; j  <  n ; ++j)
			{
				if (i & (1L << j))
				{
					a += v[j].a;
					d += v[j].d;
					h += v[j].h;
				}
			}
			
			carta aux = carta(a, d, h);
			if (aux == prassodia)
			{
				flag = 1;
				break;
			}
		}
		if (flag) cout << "Y\n";
		else cout << "N\n";
	}
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2 5 20 10 8 10 7 9 10 3

Output

x
+
cmd
N
Advertisements

Demonstration


Previous
#1895 Beecrowd Online Judge Solution 1895 Game of Limit Solution in C, C++, Java, Js and Python
Next
#1901 Beecrowd Online Judge Solution 1901 Butterflies Solution in C, C++, Java, Js and Python