JOIN
Get Time

   Problem Statement  

 Problem Statement for DoraemonPuzzleGame

Problem Statement

    

Doraemon is fond of playing puzzle games. Today he found a new puzzle game. This problem is about the first episode of this game.

The episode is divided into N levels, numbered 0 through N-1. You are allowed to play the levels in any order you like. Each time you play a level it takes you one minute. There are three possible outcomes: you either fail the level, or you clear it and get one star, or you clear it and get two stars. If you play the same level multiple times, only the best result is stored by the game. (Clearing is better than not clearing, and two stars are better than one.)

In order to advance to the next episode, you must clear all N levels, and the total number of stars you received must be at least m. (If you have enough stars but you did not clear some levels, you do not advance yet.)

You already know how good Doraemon is in each of the levels. You are given this information as int[]s X and Y. For each i, the values X[i] and Y[i] describe what happens when Doraemon plays level i:

  • With probability (1000 - X[i] - Y[i])*0.001, Doraemon will not clear the level.
  • With probability X[i]*0.001, Doraemon will clear the level and get one star.
  • With probability Y[i]*0.001, Doraemon will clear the level and get two stars.

You are also given the int m: the number of stars Doraemon needs to collect. Doraemon is trying to minimize the expected time he will need to finish the current episode. Assume that he always picks the next level to play optimally. Compute and return the expected number of minutes from the beginning to the episode to the moment when Doraemon finishes it.

 

Definition

    
Class:DoraemonPuzzleGame
Method:solve
Parameters:int[], int[], int
Returns:double
Method signature:double solve(int[] X, int[] Y, int m)
(be sure your method is public)
    
 

Notes

-When Doraemon plays the same level multiple times, we assume that the outcomes are mutually independent.
-Your return value must have an absolute or relative error smaller than 1e-9.
 

Constraints

-N will be between 1 and 2000, inclusive.
-X and Y will each contain exactly N elements.
-Each element of X and Y will between 1 and 1000, inclusive.
-For each i, X[i] + Y[i] will not exceed 1000.
-m will be between N and 2*N, inclusive.
 

Examples

0)
    
{800}
{200}
2
Returns: 5.0
There is only one level. Doraemon needs two stars to finish the episode. The only strategy is to play level 0 until he gets two stars. As that happens with probability 0.2, the expected time is 5 minutes.
1)
    
{1,999,999}
{999,1,1}
3
Returns: 3.0
In this episode, Doraemon will surely clear each level he plays. Thus, he needs to play each level at least once. The optimal strategy is to play each level exactly once, in any order. Once he clears all of them, he will also have enough stars. Note that for example after playing levels 0 and 1 Doraemon will almost certainly have enough stars. However, that is not enough - he is also required to clear all levels.
2)
    
{500,500}
{500,500}
3
Returns: 2.5
Here is one optimal strategy: Doraemon will start by playing each level once. With probability 0.75 he will collect enough stars and finish the episode. With probability 0.25 he will clear both levels but he will have only two stars. In this unlucky case, he can now play level 0 again and again, until he clears it for two stars.
3)
    
{250,250,250,250}
{250,250,250,250}
5
Returns: 8.25
4)
    
{250,500,250}
{500,250,500}
5
Returns: 4.962962962962963
5)
    
{600,900,800,500,900,200,400,100,800,300,900,300,800,700,800,600,800,900,400,100,100,700,600,100,500,
800,700,600,900,600,300,100,300,100,700,500,900,200,800,400,300,700,300,400,700,300,400,800,300,200}
{400,100,200,500,100,800,600,900,200,700,100,700,200,300,200,400,200,100,600,900,900,300,400,900,500,
200,300,400,100,400,700,900,700,900,300,500,100,800,200,600,700,300,700,600,300,700,600,200,700,800}
95
Returns: 119.33578280666175

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 628 Round 1 - Division I, Level Three