ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural FU Open Personal Contest 2014

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Thousand Imps

Time limit: 1.0 second
Memory limit: 64 MB
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.


5 0
3 50


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
To submit the solution for this problem go to the Problem set: 2094. Thousand Imps