Well, my idea was the following: What should we do? Try each round for at least 1 star (each one independent), then some easiest (by Y) of rest rounds to 2 stars (each one independent again)

Note, that if some hard(by Y) rounds are with 1 star and we need more 2stars it doesn't make sense to have 1 on easy round. So the solution:

Sort by Y, then have a dynamic programming dp(A rounds left,B 2stars needed). If A=B then you need get 2stars on current, else it's not important and you will get 2stars with probability x/(x+y).

And you need fact that if probability of smth is p, then it'll take 1/p turns to first success, but it was even mentioned in sample description.

500?

You must train and quickly solve all first problem before foward 1000 problem!

Even though quite late, I'll explain my approach:

First, if the probability of successfully solving a level is p, then the expected time of solving it is 1 with probability p or E + 1 (starting from the same situation) with probability 1 - p, so

Sort the levels by increasing $y$ and try solving them in that order. For solving level i, we take expected time and get 0 or 1 additional stars (subtract N from m). There's a critical point where, after solving i levels, out of which we only got 0 additional stars for the i-th, we realize that OSHIT, we need N - i more stars, but only have N - i levels left. The optimal strategy, due to sorting (our chances are the best with these N - i levels), is solving these N - i remaining levels each for 1 additional star. Since we can treat it as winning with probability only y_i, the expected time for it is .

What now? Suppose we knew probabilities P_i, j that after solving i levels, we get j additional stars. Then, the probability of the OSHIT moment after solving i levels is : we must've gained exactly m - (N - i) additional stars in levels 1..i - 1 and 0 in level i (which gives the term ). Also, in this situation, total expected time is .

There are 2 special cases here:

• m = 2N originally: the OSHIT moment happens at the beginning of the game (so for i = 0), with probability p₀ = 1; we need time
• we can win the game even without such situations, if we get strictly more than m additional stars just by playing to complete all levels; that gives time with probability

Any win must fall into exactly one of these situations, so the total expected time is

Anybody knows when will be next srm?

To find root of number or to say that it doesn't exist I usually write like that:

(1 <= n and n <= 10 ^ 18)
int get(ll n) { 
  ll x = (ll)sqrt(x + .0);
  if (x * x == n) return x;
  return -1;
}

But after this SRM(div1 250) I noticed that more experienced coders more careful; For example: Mimino used binary search to find SQRT of N, also sdya's code differs from mine.

bool getRoot(long long n) {
  long long m = (long long)(sqrt((double)(n)));
  for (long long i = m - 2; i <= m + 2; ++i) {
    if (i >= 1 && i * i == n) {
      return true;
    }
  }
  return false;
}

Is there some testcases where my code doesn't work?