IGOR - Helping Igor
Dr Samuel has been working in one of his grim (and useless) experiments in order to take control of the humanity.
Recently, he has been working in a hypnotic bomb, and he plans to launch it in the center of the city. Once it falls, all the inhabitants will be under his control, due to the properties of its principal element, the Samuelanium.
Amusingly, the Doctor himself created this element, and he does not know its behavior! He has commanded Igor, his faithful sidekick (and slave) to describe it.
Samuelanium’s behavior is pretty strange. According to Igor’s Notes:
-Its atoms are only composed by electrons and protons and it has a chain-like shape.
-On its sides there are two strange portals. They can suck the proton-electron chain in only one direction. Once a particle enters in a portal, it comes back from the other portal with its charge changed.
-If the first particle in the chain is a proton, the charge of the last particle changes.
For example, suppose we have the chain "+-+".
As you can see, the first particle is a proton, so the last particle must change its charge, becoming "+--". Then, the chain is sucked by the left portal. The proton comes out from the right portal, having changed it charge, becoming "---"(as an electron). This occurs in one second.
So, if the chain is represented as "+-+" at time 0, it will be represented as "---" at time 1.
Doctor Samuel wants to know the state of this chain, having passed some seconds from its initial state.
Unfortunately, Igor is exhausted. Can you help Igor and (ironically) help Doctor Samuel to control the humanity and conquer the whole world?
Your program will be tested with t experiments.
Every experiment begins with two integers, n and k. n represents the length of the Samuelanium chain, and k represents the number of queries that Samuel demands.
Next, there will be a string of length n, composed only of '+' and '-'. '+' represents a proton, and '-' an electron. This chain represents its initial state (time 0).
You must assume that the portal that sucks the chain is on the left side.
Then, there will be k lines, with an integer ki, representing the time query you have been asked for.
For each test case you must print one line containing "Experiment #i:", being i the ith case you are analyzing.
Then, k strings, representing the chain in a given moment.
Remember, protons are represented with '+' and electrons with '-', and there are no neutrons.
@Miguel Oliveira : Thanks for the explanation. :)
There is an easy way to do this and a hard way, think carefully what this resembles :)
@Rajdeep, the chain is sucked to the left "---" => "--" and the first atom ('-') moves to the right while changing its charge: "--" and "+" = "--+"
Can someone please explain the 2nd case? How is --- changed to --+ after 2 seconds?Last edit: 2013-07-30 12:02:33
Great problem !
nice question, it takes some implementation, but it has a nice logic behind it :)