# PROBLEM LINK:

*Author:* Kumar Raju

*Editorialist:* Kumar Raju

# DIFFICULTY:

CAKEWALK

# PREREQUISITES:

Implementation, Math

# PROBLEM:

Given N items of value X and M items of value Y, divide the items into two sets S_1 and S_2 such that \sum s_1 = \sum s_2 .

# QUICK EXPLANATION:

You can find the answer by running two nested loops.

# EXPLANATION:

Let the two sets be denoted by S_1 and S_2.

Let (i,j) be the tuple denoting the number of elements valued X and Y respectively is S_1.

Therefore, the number of elements in S_2 will be (N - i, N - j).

Sum of S_1 = i \times x + j \times y

sum of S_2 = (N - i) \times x + (M - j) \times y

Thus, we need to find if there exists 2 non-negative integers i and j such that the following equation is satisfied:

(N - i) \times x + (M - j) \times y = i \times x + j \times y

We can check this by replacing i and j with all possible values using simple for loops.

Check the simple code below for more understanding.

The intended complexity for this problem is \mathcal{O}(N^2)

# EDITORIALIST’S SOLUTION:

Language used : C++

```
#include <bits/stdc++.h>
int main()
{
long long t, n, m, x, y, i, j, flag;
cin>>t;
while(t--)
{
flag = 0;
cin>>n>>m>>x>>y;
for(i = 0; i <= n; ++i)
for(j = 0; j <= m; ++j)
if( (n - i)*x + (m - j)*y == (i)*x + (j)*y )
flag = 1;
if(flag)
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
```