1554 . Thomas' Rods
Description
Thomas has recently acquired a rod with dimensions 1x2xN, where 3<= N<=100000. The mechanics of Thomas' Rod resemble those of a standard 3x3x3 Rubik's Cube; in fact, one can twist it around in N+1 different ways as follows (all twists must be by multiples of 180 degrees):
The long length of the rod has made it particularly useful for a variety of essential day-to-day errands: it has successfully served Thomas as a back-scratcher, TV remote replacement and as a means to prod one Waylon Smithers. However, during its most recent stint as a fishing rod, it fell into a pond when Thomas was unable to sustain the weight of a particularly hungry goldfish. Unfortunately, this meant the coloured labels peeled off, leaving an unlabelled Rod, 6N+4 sticky labels and a very confused goldfish splashing around in the pond.
Smithers, as dutiful as ever, retrieved the sticky labels and pasted them back on the Rod. Due to Smithers' haste to reaffix the labels before the adhesive completely wore off, however, the labels were randomly placed back on! Thomas, as exceedingly reasonable as he is, has become wary of Smithers' performance, and is concerned that the Rod may no longer be solvable.
You are Lisa Simpson, and Thomas has come desperately seeking your help. Can you determine if the Rod is solvable? Note that the Rod is said to be solvable if there is a sequence of twists, as described above, such that any two labels are the same color if and only if they're on the same face of the Rod. Moreover, cheap manufacturing processes mean that the labels could have changed color while floating around in the pond.
Input Format
The first line of the input file contains an integer indicating the number of test cases.
The first line of each test case contains a single integer N, 3<= N<=100000, denoting the length of the Rod. Following this are N+2 lines, describing the affixed colors -- assume the Rod lies flat, pointing away from you:
- The first line has two space-separated integers, a_1 (your left) and a_2 (your right), denoting the colors of the two labels closest to you and facing you.
- The second line has two space-separated integers, b_1 (your left) and b_2 (your right), denoting the colors of the two labels furthest from you and facing away.
- The (2+k)-th line has six space-separated integers, c_1, c_2, c_3, c_4, c_5 and c_6, denoting the colors affixed to the two blocks at position k from you -- the colors are ordered clockwise, proceeding in this order: top left, top right, right, bottom right, bottom left, left.
Output Format
For each test case, print out a single line that contains the word "solvable" (no quotes) if the rod is solvable,
or "unsolvable" otherwise.
Sample Input 1
5 5 0 0 1 1 2 2 3 4 4 5 2 2 3 4 4 5 2 2 5 4 4 3 2 2 3 4 4 5 2 2 3 4 4 5 4 1 1 2 2 4 4 3 0 0 5 4 0 5 4 0 3 4 0 5 4 0 3 4 4 3 0 0 5 4 2 2 3 3 1 1 5 0 0 4 0 0 5 1 1 5 1 0 5 1 0 4 1 1 5 0 0 4 4 0 0 2 2 5 5 1 4 4 3 5 5 1 4 4 1 5 5 1 4 4 3 5 5 1 4 4 3 4 1 1 0 0 2 2 5 3 3 5 2 3 5 2 3 4 2 3 5 2 3 4 2 2 5 3 3 4
Sample Output 1
solvable solvable unsolvable unsolvable unsolvable
Hints
Problem Source
Migrated from old NTUJ.
2010 Stanford Local Round 2
Subtasks
| No. | Testdata Range | Score |
|---|