Alice and Bob are going to play a game. Before the game starts, each of them will write down a string which only consists of "1" and "0". For convenience, the Alice's string will be marked as P and the Bob's string will be marked as Q.
Then, they will toss a coin by (at most) K times. The i-th tossing result Si is "1" if the coin turns face up, otherwise it will be "0". During the game, if the Alice's string P or the Bob's string Q exists in the current tossing sequence, the game will end immediately. If only P appears in the tossing sequence, Alice will win the game. If only Q appears, Bob will win. If both P and Q appears at the same time, or none of them appears after K times of coin tossing, the game is draw.
Given P, Q and K, please calculate the winning probability of Alice and Bob respectively. The coin is uniform, so any tossing result has an equal probability to be "1" or "0".
2
010
001
25
0
11
5
0.33310899 0.66596049
0.75000000 0.25000000