Harold and Diane are treasure-hunting siblings, currently on a dangerous trek to retrieve the priceless Tiger Jewel, hidden in an ancient underground complex in the middle of a wild jungle home to hungry man-eating tigers. The team are able to navigate the jungle without alerting any of the tigers, however the Jewel is located at the end of a long underground tunnel, to which the siblings have just uncovered the sealed entrance door. Next to the door are many stone buttons, alongside a giant lever. Luckily the siblings have already done their research, having poured through old historical documents to understand how these mechanisms work.
The hallway inside consists of many rooms,
each separated by a narrow trap-filled passage with pressure-plates in the floor
and holes in the walls, ready to release arrows at whatever passes through.
However, each passage is either in a SAFE
state which will allow a person to pass unharmed,
or in an UNSAFE state which will trigger the arrows to release once
the pressure-plates on the floor have been activated.
Aside from the final room containing the Jewel, the other rooms are labeled from 0 to N.
The buttons outside are labeled from 1 to N, each corresponding to a room bounded by passages.
When a given button is pressed, both passages adjacent to the corresponding
room will toggle their state, either from SAFE to UNSAFE, or from UNSAFE to SAFE.
The large lever will open the sealed entrance to the hallway. However once the main entrance is unsealed, the buttons will no longer work and the rooms and passages will no longer be able to be toggled. Thankfully, the state of each passage is visible before unsealing the main entrance, but the two adventurers must be certain that the entire passage is indeed safe before doing so. Unfortunately, the initial state of each passage is random.
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
║ └┬┘ └┬┘ └┬┘ └┬┘ │
║ 0 X 1 2 X 3 J │
║ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ │
└─────┘ └─────┘ └─────┘ └─────┘ └─────┘
In the above example where N=3, the passages between rooms 0-1 and 2-3 are initially UNSAFE. However the
siblings could remove all traps by toggling rooms in the order 1, 2.
Some of these hallways will be quite long, so instead of providing the initial states directly we will use the
Linear Congruential Generator
(use a = 445, c = 700001 and m = 2097151) to pseudo-randomly determine the state of each passage in the hallway,
beginning with the passage closest to the entrance.
Each testcase will consists of two numbers, N and x0. Use x0 as the seed and generate N+1 numbers.
An even number corresponds to an initially SAFE passage,
and an odd number corresponds to an initially UNSAFE passage.
As Harold and Diane ponder the problem, they begin to hear the growling of hungry tigers stalking them... they need to act fast!
Input Data
The first line will be Q, the quantity of testcases.
Q lines will then follow, each representing a testcase with two values each: N being the number of rooms in the
hallway able to be toggled, and x0 being the initial seed for the Linear Congruential Generator.
N will always be an integer greater than 0.
Answer
If it is possible to create a safe passage to the Jewel by toggling all passages into a SAFE state, the result is Y.
Otherwise, the result is N. Combine 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:
6
4 86
40 964
400 1336
4000 14116
40000 777777
400000 314157
answer:
YNYNYN