Winter in Yekaterinburg is the longest time of the year. And everyone
spends long winter evenings in his own way. Alex loves magical worlds and
tales of dragons saving princes from terrible princesses, so he often goes
to the cinema to watch animated movies.
There is a problem that such movies are popular among kids. So if you take
seat too early, each passing child can pour a coke on you. And if you
enter the cinema hall too late, each child, by which you are squeezing to
your seat, will try to kick you. Therefore, in recent times Alex,
entering the hall, studies which seats have already taken, and depending
on that decides whether to wait in the aisle or go to his seat.
Alex knows that:
- if at the moment when he enters the hall, some seat is vacant, it
will remain vacant up to the start of the movie with probability p%;
- spectators enter the hall one at a time and in a random order;
- each spectator, including Alex, goes to his seat from the left edge
of the row;
- latecomers are not allowed to the hall. So if at the beginning of
the movie Alex is still standing in the aisle he goes to his seat as
realizes that no one else will have to pass.
Alex wants to get a strategy minimizing the sum of the number of
spectators, through whom he will pass to his seat, and the number of
spectators who will pass to their seats through him. Find the
mathematical expectation of the required sum in the optimal strategy.
The first line contains integers n and p that are the number of seats
in the row and the probability in percent, that a vacant seat will remain
vacant up to the start of the movie (1 ≤ n ≤ 1 000; 0
≤ p ≤ 100). The second line contains n characters
describing the occupied seats in the row at the moment when Alex enters
the hall. The i-th character equals 0 if the i-th left seat is
vacant, 1 if it is occupied, and 2 if it is Alex’s seat. It is
guaranteed that the string has exactly one character 2.
Output the required mathematical expectation with absolute or relative
error not exceeding 10−6.
In the first example the optimal strategy for Alex is to wait until the
fifth spectator (counting from the left) will come and to go to his seat
right after that. If the fifth spectator will come before the first one,
Alex will have to pass through two spectators; if the first spectator will
come earlier, Alex will pass through three spectators. The probability of
each of these two events is 0.5, so the required mathematical expectation
is 0.5 · (2 + 3) = 2.5.
In the second example Alex should wait for the third spectator or for the
beginning of the movie. With probability 0.375 the first spectator will
come next (and Alex will have to pass through him), with probability 0.375
the third spectator will come next, and with probability 0.25 nobody of
them will come before the beginning of the movie.
Problem Author: Denis Dublennykh
Problem Source: Open Ural FU Personal Contest 2014