|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||59||29||22||43.137%|
Bob is the Captain of the USS Spacey McSpaceface, the pride of the space fleet of the Human Empire. Unfortunately, Bob is also the last one alive on his ship.
Because of an unrecognized virus, the ship’s AI “Alpha 5” went rampant and killed everyone by funelling neurotoxin into the crew’s quarters. Bob was the only one on the bridge at that time, where he could grab a handy detoxication kit and a gas mask. But alas, Alpha 5 also blocked the ships’ controls, so Bob was now drifting in space, alone, caged with a rampant AI that just initiated the self-destruction mechanism.
Bob remembered that some engineer once told him there was an override switch somewhere near the fusion reactor that powered the ship, so he started to make his way down into the engine quarters. Soon he noticed that the virus had also taken over the automatic door system — all doors seemed to open and close seemingly at random.
At least, Bob does know three things:
Bob wants to stay on the move (neurotoxin and all), so he will use a door whenever possible. However, Bob does not know the exact way to the core, so if there are multiple possible doors he could take, he just chooses one at random. Given the sequence of letters until the explosion, how high is the probability that Bob can reach the reactor core and shut it all down?
The input consists of:
After the last letter, all doors slam shut and the ship will explode if Bob has not reached the switch yet. Bob starts on the bridge, room 1, and the override switch is in room n.
Output the percentage that Bob will reach the override switch in time.
The answer should be correct up to an absolute or relative error of at most 10−3.
5 4 1 2 A 2 3 B 1 4 A 4 5 B AB
3 2 1 2 A 2 3 B AB
3 2 1 2 A 2 3 B ACDEFGHIJKL
3 3 1 2 A 2 3 B 1 3 C ACB