MILAR10 - Ingenious Metro

no tags 



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 × 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.




Gene and Gina have a particular kind of farm. Instead of growing animals and vegetables, as
it is usually the case in regular farms, they grow strings. A string is a sequence of characters.
Strings have the particularity that, as they grow, they add characters to the left and/or to the
right of themselves, but they never lose characters, nor insert new characters in the middle.
Gene and Gina have a collection of photos of some strings at different times during their growth.
The problem is that the collection is not annotated, so they forgot to which string each photo
belongs to. They want to put together a wall to illustrate strings growing procedures, but they
need your help to find an appropriate sequence of photos.
Each photo illustrates a string. The sequence of photos must be such that if si comes imme-
diately before si+1 in the sequence, then si+1 is a string that may have grown from si (i.e., si
appears as a consecutive substring of si+1). Also, they do not want to use repeated pictures,
so all strings in the sequence must be different.
Given a set of strings representing all available photos, your job is to calculate the size of the
largest sequence they can produce following the guidelines above.





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 ≤ 10^5) and the number of queries (1 ≤ Q ≤ 10). The second line contains T different integers ti indicating the position of the teletransporters (−10^7 ≤ ti ≤ 10^7). 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 (−10^7≤ S,D ≤ 10^7).

The last test case is followed by a line containing two zeros.





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.




1 1
-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




hide comments
Simes: 2019-10-13 10:22:41

Image can be found at

Added by:~!(*(@*!@^&
Time limit:0.806s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ICPC2010 – Latin American Regional