Mo and Chemical X
All submissions for this problem are available.
Mo depressed by not getting his electronics intern, has taken up a chemical research and , has found the recipe to remain young forever .But for this he needed Chemical X (X) . It is widely known fact that Chemical X is on the verge of extinction due to the overexploitation of the resource by selfish people .
Fortunately Mo has devised a way of converting gold (G) to chemical X (X) ( Mind it , Mo has lot of gold near infinite .. ) . To do this , Chemical X (X) and Gold (G) need to be placed in a circle , with each block of chemical X in between 2 gold pieces and each block of gold in between 2 blocks of chemical X .
Now Mo , with the help of his chemical magic , can apply 2 transformations :
1) Any sequence of X-G-X in consecutive positions around the circle can be converted to G-X-G i.e. With X converted to G , G converted to X and X converted to G .
2)Any sequence of G-X -Gin consecutive positions around the circle can be converted to X-G-X i.e. With G converted to X , X converted to G and G converted to X .
Given an initial configuration, help Mo generate the maximum amount of Chemical X so as to remain young for the maximum amount of time .
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows:
The input for each test case is an even number 2*N, which denotes that Mo has placed N blocks of Chemical X(X) and N blocks
of Gold(G) in a circle with each block of X in between two blocks of Gold(G) and each block of Gold(G) in
between two blocks of chemical X. Each position around the circle where chemical X or gold is placed is allotted numbers between 0 and (2*N - 1) with successive clockwise positions around the circle being assigned
successive numbers. ( Thus position number 0 and 2*N - 1 will be adjacent). Position numbered 0 in the circle
will always contain a block of Chemical X.
For each test case, Output the sequence of magic transformations that Mo has to use to generate the maximum
amount of Chemical X from the initial configuration.Output -1 after outputting answer of each test case .
Each transformation can be uniquely specified by outputting the position of the middle element being
transformed. For example, if GXG is in position (6 7 8) is transformed to XGX , this magic transformation will
be specified by outputting 7.
- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 1500
Input: 3 4 10 24 Output: 2 -1 2 5 8 3 7 -1 2 5 8 11 14 17 20 3 6 9 12 15 19 4 7 10 14 5 9 -1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.