Vaqt limiti: 1 sekund
Xotira limiti: 64 MB
Rubik's Cube is a 3-D mechanical puzzle
invented in 1974 by Hungarian sculptor and professor of architecture Erno
Rubik. Originally called the "Magic Cube", the puzzle was licensed by
Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year
special award for Best Puzzle that year. As of January 2009, 350 million cubes
had been sold worldwide making it the world's top-selling puzzle game. It is
widely considered to be the world's best-selling toy.
The Rubik's Cube has eight corners and
twelve edges. There are 8! (40,320) ways to arrange the corner cubes.
Seven can be oriented independently, and the orientation of the eighth depends
on the preceding seven, giving 37 (2,187) possibilities. There are 12!/2
(239,500,800) ways to arrange the edges, since an even permutation of
the corners implies an even permutation of the edges as well. (When
arrangements of centers are also permitted, as described below, the rule is
that the combined arrangement of corners, edges, and centers must be an even
permutation.) Eleven edges can be flipped independently, with the flip of the
twelfth depending on the preceding ones, giving 211 (2,048) possibilities.
The total possibilities of a Rubik’s cube
are: 8! * 3^{7} * 12!/2
* 2^{11} = 43,252,003,274,489,856,000.
Although the number of cases is quite
huge, we can still solve the magic cube b some way. It is confirmed that no
matter what cases the cube is, you can solve it within just 20 turnings, quite
fantastic, isn’t it?
A Rubik’s cube
has six faces:
F (Front):
the side currently facing the solver
B (Back):
the side opposite the front
U (Up):
the side above or on top of the front side
D (Down):
the side opposite the top, underneath the Cube
L (Left):
the side directly to the left of the front
R (Right):
the side directly to the right of the front
Now, we define several moves which mean
different turning of layers: U D R L F B which means turning the up, down,
right, left, front back face clockwise for 90 degree. In addition, use
lowercase letters u d r l f b for anticlockwise turnings. Errrrrrrrr, that’s
not the end, I define more operations: X Y Z for turning the middle layer
(behind U R F) clockwise for 90 degree. Also, lowercase letters x y z for
anticlockwise.
There are some examples in the following
picture.
As you know that a Rubik’s cube can be
solved with several turnings, so we can use the letters mentioned above to
represent the solution and a solution is a string containing these lowercase or
capital letters. As the string may be very long, so after moving as the string,
the cube may return the original status as it begins (completely the same), we
define this string as a “meaningless string”.
In this question, we will give you a string,
and you should check whether the string is a “meaningless string” or not.
Input: is a single line, containing a string, length is no more than 100000.
Output: Print “Yes” is after these turnings the cube can return the cases the
same as it starts, otherwise print “No”.
¹ |
Input |
Output |
1 |
XXXX |
Yes |
2 |
UUDDuudd |
Yes |
3 |
RYl |
Yes |
4 |
RURU |
No |
Was prepared: Yo’ldoshboy
Sultonov
Translate by: Khujaniyazova
Guzal.