Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1136

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

Bingo!

 

by Ines Kereki  Uruguay

Timelimit: 2

Albert, Charles and Mary invented a new version of the classical game Bingo. In traditional Bingo the game is presided over by a non-player known as the caller. In the beginning of the game each player is given a card containing a unique combination of numbers from 0 to N arranged in columns and rows. The caller has a bag containing N+1 balls, numbered from 0 to N. On each turn, the caller randomly selects a ball from the bag, announces the number of the drawn ball to the players, and sets the ball aside so that it cannot be selected again. Each player searches his/her card for the called number and marks it if he/she finds it. The first player who marks a complete pre-announced pattern on the card (for example, a full horizontal line) wins a prize.
In the Albert-Charles-Mary version, on each turn, the caller draws a first ball, returns it to the bag, draws a second ball, returns it to the bag, and then calls out the absolute difference between the two ball numbers. To generate even more excitement, before the game started a possibly empty subset of balls is removed from the bag, in such a way that at least two balls remain there. They would like to know if every number from 0 to N may still be called out with the new drawing method considering the balls that were left in the bag.

 

Input

 

Each test case is given using exactly two lines. The first line contains two integers N and B. The meaning of N was described above (1 ≤ N ≤ 90), while B represents the number of balls which remained in the bag (2 ≤ B ≤ N+1). The second line contains B distinct integers bi, indicating the balls which remained in the bag (0 ≤ bi ≤ N).
The last test case is followed by a line containing two zeros.

 

Output

 

For each test case, print a single line containing a single uppercase ‘Y’ if it is possible to call out every number from 0 to N, inclusive, or a single uppercase ‘N’ otherwise.

 

 

 

Input Sample Output Sample

6 7
2 1 3 4 0 6 5
5 4
5 3 0 1
5 3
1 5 0
0 0

Y
Y
N

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSIZE 100009

int c[MAXSIZE];
int v[MAXSIZE];

int main(int argc, char **argv)
{

    int n, b;
    while (scanf("%d %d", &n, &b), n)
    {

        for (size_t i = 0; i  <  b; ++i)
        {

            scanf("%d", &v[i]);
            for (size_t j = 0; j  < = i; ++j)
                c[abs(v[i] - v[j])] = 1;
        }

        size_t i = 0;
        for (; i  < = n; ++i)
            if (!c[i])
                break;

        printf("%c\n", (i - 1UL) != n ? 'N' : 'Y');
        memset(c, 0, sizeof(int) * (n + 1));
    }

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
6 7
2 1 3 4 0 6 5
5 4
5 3 0 1
5 3
1 5 0
0 0

Output

x
+
cmd
Y
Y
N

#2 Code Example with C++ Programming

Code - C++ Programming


#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,b;
	while(cin >> n >> b && n)
	{
		vector < bool> a(n+1);
		int count = n+1;
		std::fill(a.begin(),a.end(),false);
		vector<int> c(b);
		for(int i = 0; i  < b; i++)
		{
			cin >> c[i];
			a[c[i]] = true;
			count--;
		}
		int abss;
		for(int i = 0; i  <  b-1; i++)
		{
			for(int j = i+1; j  <  b; j++)
			{
				abss = abs(c[i]-c[j]);
				if(a[abss] == false)
				{
					a[abss]=true;
					count--;
				}
			}
		}
		if(count != 0)
		  cout << "N\n";
		else
		  cout << "Y\n";
	}
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
6 7
2 1 3 4 0 6 5
5 4
5 3 0 1
5 3
1 5 0
0 0

Output

x
+
cmd
Y
Y
N

#3 Code Example with Python Programming

Code - Python Programming


while True:
   n, b = [int(x) for x in input().split()]
   if n == b == 0: break
   p = [int(x) for x in input().split()]
   a = list(set([abs(a-b) for a in p for b in p]))
   b = [x for x in range(0, n+1)]
   print('Y' if a == b else 'N')
Copy The Code & Try With Live Editor

Input

x
+
cmd
6 7
2 1 3 4 0 6 5
5 4
5 3 0 1
5 3
1 5 0
0 0

Output

x
+
cmd
Y
Y
N
Advertisements

Demonstration


Previous
#1134 Beecrowd Online Judge Solution 1134 Type of Fuel Solution in C++, Java, Js and Python
Next
#1140 Beecrowd Online Judge Solution 1140 Flowers Flourish from France Solution in C, C++, Java, Js and Python