Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1320
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1320
Ingenious Metro
By Ricardo Anido 
Brazil
Timelimit: 3
The King of Logonia will inaugurate soon a new and revolutionary metro, based on an invention of the Royal Engineers, which allows teletransportation.
The new metro consists of a very long tunnel with a station at each kilometer. There are also T teletransporters, which are located at some of the stations. In each station there is a keyboard with T keys, where each key corresponds to one teletransporter. The figure below illustrates a metro system with three teletransporters, located in stations marked A, B and C.
The metro works as follows. The user goes in a station (the start station) and presses the key corresponding to the teletransporter he wants to use. The user is then teletransported to the station which is at the same distance from the teletransporter as the start station, but on the opposite side relative to the teletransporter. More precisely, if the location of the start station is i and the user presses the key corresponding to the teletransporter located in position j, he will be taken to the station located at position 2 x j - i. For example, if the user is in station 6 and wants to go to station -2, he can use the teletransporter C (goes from 6 to 10) and then the teletransporter A (goes from 10 to -2).
The King, however, knows that it is possible that there is no sequence of teletransporters that will take the user from a given station X to a given station Y. To avoid that the users keep trying to go where they cannot go, he wants to make a program available in the Internet to help users. The King wants you to write a program which, given the position of each teletransporter, answers a series of queries. For each query the start and the destination stations are given, and your program must determine if it is possible for the user to go from start to destination.
Input
Each test case is given using several lines. The first line contains two integers T and Q indicating respectively the number of teletransporters (1 ≤ T ≤ 105) and the number of queries (1 ≤ Q ≤ 10). The second line contains T different integers ti indicating the position of the teletransporters (-107 ≤ ti ≤ 107). Each of the Q following lines describes a query and contains two distinct integers S and D indicating the position of the start and destination stations (-107 ≤ S, D ≤ 107).
The last test case is followed by a line containing two zeros.
Output
For each test case output a single line containing the answers to the Q queries, in the same order that the queries were given in the input. For each query you must output an uppercase 'Y' if it is possible to reach the destination station from the start station using the metro, or an uppercase 'N' otherwise.
| Sample Input | Sample Output |
|
1 1 |
Y |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAXSIZE 101009
int v[MAXSIZE];
char ans[MAXSIZE];
int gcd(int, int);
int compare(const void *, const void *);
int main(int argc, char **argv)
{
size_t j;
int t, q, g;
while (scanf("%d %d", &t, &q), t)
{
for (size_t i = 0; i < t; ++i)
scanf("%d", &v[i]);
qsort(v, t, sizeof(int), compare);
if (t > 1)
g = v[1] - v[0];
for (size_t i = 2; i < t; ++i)
g = gcd(v[i] - v[i - 1], g);
j = 0;
bool pos;
memset(ans, 0, sizeof(ans));
while (q--)
{
int s, d;
pos = false;
scanf("%d %d", &s, &d);
if ((s & 1) == (d & 1))
{
if (t == 1)
pos = (d + s == v[0] << 1);
else if (((d - s) >> 1) % g == 0)
pos = true;
else
{
d = (d + s) >> 1;
for (size_t i = 0; i < t; ++i)
if (d - v[i] % g == 0)
pos = true, i = t;
}
}
if (pos)
ans[j++] = 'Y';
else
ans[j++] = 'N';
}
for (size_t i = 0; i < j - 1; ++i)
printf("%c ", ans[i]);
printf("%c\n", ans[j - 1]);
}
return 0;
}
int gcd(int a, int b)
{
while (b != 0)
{
int aux = a;
a = b;
b = aux % b;
}
return a;
}
int compare(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
Input
-2
-6 2
5 2
10 20 30 40 50
10 15
20 40
5 3
0 5 -3 -8 4
-1 499
4 237
-1 -591
0 0
Output
N Y
Y N Y