ZOJ Problem Set - 3022
In the year of 2010, "Watashi" and "Kimi" become the admins of ZOJ. They are twins, but "Kimi" always does the right things while "Watashi" always does the wrong things.
The online contest "ZOJ Weekly" is scheduled in tomorrow. There will be N problems in this contest, and "Watashi" and "Kimi" are busy checking the the data for all the problems. After "Kimi" checks the data of a problem, the data will always be right, but After "Watashi" checks the data of a problem, the data will always be wrong!
In each turn when "Watashi" or "Kimi" checks, he will first choose a problem to check. Either of them will never choose the problems which he can make sure is most recently checked by himself (not by the other one). He will then randomly choose a problem in the candidate problems, and checks the data for that problem. So when either of them is sure that all the problems are lately checked by himself, he will do nothing.
Given the order in which they check the problems, you are to print the probability that all the data are right after all the checks made by them.
Initially, all the problems have been checked by "Kimi" so all of them are right at first. And both of them know when the other one checks the data, but they can't see which problem the other one is checking.
There are multiple test cases. There are two parts for each case. The first part is one line with an integer N (1 <= N <= 16), the number of problems for the contest. The second part consists with some lines. A line will be either "Watashi" or "Kimi", which means a check made by "Watashi" or a check made by "Kimi". This part ends with a line with "End". There will be at most 100 lines for the second part.
For each case, print a real number in one line, the probability that all the data are right after all the checks made by them. Keep two digits after the decimal point.
2 Watashi End 3 Watashi Kimi End
HintFor Sample 1, one of the two problems is ruined by Watashi.
For Sample 2, after the check by Watashi, one of the three problems is wrong, and there is a probility of 1/3 for Kimi to modify this problem right.
Author: HANG, Hang
Source: ZOJ Monthly, August 2008