MCLB - Magic Crystals and Laser Beams

no tags 

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!

 


hide comments
Rishav Goyal: 2014-06-05 17:21:54

Beautiful Problem !

Shivam: 2014-01-22 12:44:14

if start and end states are same expected answer is 0.

gabber: 2012-12-21 12:57:03

:O

Aman Choudhary: 2012-06-29 11:33:45

dont 4get to add Case #i.....costted me 4 wa :P

Devil D: 2011-12-13 09:34:39

What if both the start and the end states are the same ...?

dreamer: 2011-11-18 08:39:24

Someone who has got an ac ,please clarify this problem statement a bit more..
thanx in advance

Loai Ghoraba: 2011-11-15 16:28:09

@:D You are correct, we asked for a clarification in the actual contest but got "No response, read the problem statement" and got WA :) :)

:D: 2011-11-15 09:09:35

This problem needs more clarification! If end or start state are all red than the solution is “The goal state will never be reached!”. It's very unintuitive and probably caused a lot of WA's!

P.S.

Thanks for help multisystem. And thanks to the author for additional test cases. Still remember that for start=end=RRR..R is the answer is also "The goal state will never be reached!"

Last edit: 2011-11-15 18:10:30
A. Muh. Primabudi: 2011-11-15 09:09:35

thanks got AC :D

multisystem: 2011-11-15 09:09:35

@: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.


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