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!
hide comments
|
David:
2020-10-30 22:14:47
The problem is specific and clear. An important business rule stated above: The game ends when all the magic crystals are all red. |
|
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..
|
|
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!
|
|
A. Muh. Primabudi:
2011-11-15 09:09:35
thanks got AC :D |
| 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 |
RSS