MCLB - Magic Crystals and Laser Beams

John and Ged are playing a game with magic crystals and a laser beams. The game starts by arranging a 64 magic crystal in a single row and both John and Ged stand on the right of this row and start shooting them with laser beams. The magic crystals come in different colors each of which has a different behavior.  The red crystal absorbs the laser beam while the blue crystal allows the laser beam to move through it passing to the following crystal. In both cases, the crystals flip its color: red crystal flips to blue crystal while blue crystal flips to red crystal. The behavior of crystals with other colors is not always defined so they will not be part of the game. The game ends when all the magic crystals are all red.

After a long time of playing with the magic crystals, John was wondering, given start state of crystals order, after how many laser beams they can reach a given target order before reaching the end of the game. Kindly help them J, and if the target state can’t be reached, tell them.

Input Specification:

A row of crystals is represented by a string, and the row's right is the last character in the given string. The first line of input contains an integer T that represents the number of test cases, then follow 2T lines such that each case will consist of 2 lines each of them contain a string of exactly 64 character either R (for Red) or B (for Blue) . The first line is the starting state of the game and the second line is the state that John wonders if they can reach.

Output Specification:

For each test case, output a single line of output in the form “Case K: state” where K is the number of the test case and state is either “The goal state could be reached after X laser beams.” Or “The goal state will never be reached!” where X is the number of laser beams needed before reaching the goal state.

Sample input:

3
BBRRBRBRBRBBRBBBRBBRBRBBBRBBBRBRRRBBRBRBBRBRBRBRBBRBRBRBRRBBBBBR
BBRRBRBRBRBBRBBBRBBRBRBBBRBBBRBRRRBBRBRBBRBRBRBRBBRBRBRBRBRRRRRR
BBRRBRBRBRBBRBBBRBBRBRBBBRBBBRBRRRBBRBRBBRBRBRBRBBRBRBRBRRBBBBBR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
BBRRBRBRBRBBRBBBRBBRBRBBBRBBBRBRRRBBRBRBBRBRBRBRBBRBRBRBRRBBBBBR

Sample Output:

Case 1: The goal state could be reached after 2 laser beams.
Case 2: The goal state will never be reached!
Case 3: The goal state will never be reached!

 


Added by:Mostafa Saad Ibrahim
Date:2011-11-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:10th Egyptian Collegiate Programming Contest

hide comments
2011-11-15 09:09:35 multisystem
@:D

Your guess is right. Unfortunately, when both start and end states are red, the output should be "“The goal state will never be reached!"

@A. Muh. Primabudi
unsigned long long is enough. I think my reply to :D is the cause of your WA.
2011-11-15 09:09:35 A. Muh. Primabudi
i dont know where my code fails, are unsigned long long int is enough?
2011-11-15 09:09:35 Mostafa Saad
text refine (1): The red crystal absorbs the laser beam while the blue crystal allows the laser beam to move through it passing to the following crystal. In both cases, the crystals flip its color: red crystal flips to blue crystal while blue crystal flips to red crystal.

Last edit: 2011-11-15 08:50:17
2011-11-15 09:09:35 :D
How do we treat cases when start or end state are all red? I would say this is obvious, but after the WA's I'm really not sure.

Last edit: 2011-11-14 21:47:39
2011-11-15 09:09:35 Ahmed Kamel [ahm.kam_92]
@Kukah: The current crystal (the blue one which the laser just passed though)

@Primabudi: It should return "The goal state will never be reached!".
2011-11-15 09:09:35 A. Muh. Primabudi
what the meaning of this statement
"The game ends when all the magic crystals are all red."

if the start state is
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

and the final state is
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRB

the out put is The goal state will never be reached! or 2 beams?


Last edit: 2011-11-14 11:52:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.