Harold and Diane finally arrive at the end of the long trapped hallway, expecting to finally take possession of the pricessless Tiger Jewel. However instead of any treasure room, they instead uncover the entrance to a room containing an even more puzzling obstacle!
The next room is in a large triangular shape, divided up into smaller triangular tiles of equal size.
At the corner of each tile is a stone. If a room has N stones in total, then each stone
is labeled sequentially from 0 to N-1. The stones are initially in some random order,
but they can be moved by rotating tiles. Any floor tile may be rotated clockwise,
similarly adjusting the stones located on the corners of that tile.
Let's take the following room as an example.
Notice that there are S = 3 stones along the bottom edge of the room.
0
/ \
1---2
/ \ / \
3---4---5
This layout is considered ordered, as the stones are in ascending order when read from top-to-bottom and left-to-right. Conversely, the following layout is considered disordered.
2
/ \
5---4
/ \ / \
0---3---1
However, this triangle may be reverted back to an ordered state, by rotating the bottom-left tile once, the bottom-right tile twice, then the top tile once.
2 2 2 2 0
/ \ / \ / \ / \ / \
5---4 -> 0---4 -> 0---5 -> 0---1 -> 1---2
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \
0---3---1 3---5---1 3---1---4 3---4---5 3---4---5
As Harold and Diane start to solve the problem, they again hear the growling of hungry tigers prowling down the hallway behind them... they need to act fast!
To determine the initial layout of the stones, we'll use the
Linear Congruential Generator
(use a = 445, c = 700001 and m = 2097151) .
0, 1, 2, 3, ...N pseudo-random numbers from the Linear Congruential Generator and take the result of each modulo N to yield a list of N random numbers [r0, r1, r2, ...]0th position, and replace it with the stone in the rth position. For example, starting with the LCG seed value of x0 = 8756942 ...
Input Data
The first line will be Q, the quantity of testcases.
Each testcase consists of 2 space-separated values: S x0,
where S is the quantity of stones along the bottom edge of the trangular room,
and x0 is the seed value for the Linear Congruential Generator.
Answer
If it is possible to order the stones by some sequence of valid rotations, the result is Y.
Otherwise, the result is N.
Concatenate all results together into a single string and return the answer.
As the tigers are about to find the siblings, you have just 3 minutes to solve the problem after you are given
your input data; so please reload the page to get new input before calculating and submitting the answer.
Example:
input data:
4
3 1321093
3 37943
67 1459008
70 392856
answer:
YNYN