IOISureWinner | Topcoder Archive

Problem Statement

The International Olympiad in Informatics (IOI) is currently in progress. To honor this competition, our problems for this round have IOI-flavored stories.

Topher Coder is leading the IOI after day 1. On day 2, he needs at least scoreNeeded points to be guaranteed the first place.

Day 2 contains N subtasks Topher may possibly solve. Each subtask offers some number of points. Additionally, for each subtask we are given the probability that Topher will successfully solve the subtask (and thus get the points). The tasks are such that each subtask is solved independently, so we will assume that all the random events "Topher solves subtask i" are mutually independent.

You are given the information about subtasks in the int[]s subtasks and p. For each i, Topher will solve subtask i with probability p[i] percent, and if he does, he will get subtasks[i] points.

Calculate and return the probability that Topher's day 2 score will be greater than or equal to scoreNeeded points.

Definition

Class:: IOISureWinner
Method:: probability
Parameters:: int, int[], int[]
Returns:: double
Method signature:: double probability(int scoreNeeded, int[] subtasks, int[] p)
(be sure your method is public)

Notes

Your return value must have an absolute error of at most 1e-9 to be accepted. In languages where you have the choice, we recommend the use of double-precision floating point variables ("double"s) when calculating the result.

Constraints

scoreNeeded will be between 1 and 300, inclusive.
N (the length of subtasks) will be between 1 and 50, inclusive.
Each element of subtasks will be positive.
sum(subtasks) will not exceed 300.
p will contain exactly N elements.
Each element of p will be between 1 and 100, inclusive.

Examples

```
31
```
```
{10, 10, 10, 10}
```
```
{50, 50, 50, 50}
```
```
Returns: 0.0625
```
Topher needs at least 31 points. There are four subtasks. Each gives 10 points and Topher will solve it with probability 50 percent. He needs to solve all four, which will happen with probability (1/2)^4 = 1 / 16.
```
40
```
```
{10, 10, 10, 10}
```
```
{50, 50, 50, 50}
```
```
Returns: 0.0625
```
The same situation as in the previous example. Getting exactly 40 points is still enough.

{10, 20, 30, 40}

{99, 98, 97, 96}

Returns: 0.0

There is no way to get 101 or more points.

```
100
```
```
{20, 30, 100, 50}
```
```
{12, 34, 56, 78}
```
```
Returns: 0.57400256
```
One option for Topher is to solve the subtask worth 100 points (and any other subtasks along with it). If he doesn't solve that subtask, he must solve all three remaining subtasks. The first option has probability 0.56, the second option has probability 0.12 * 0.34 * (1 - 0.56) * 0.78.

{10, 11, 12, 13, 14}

{10, 10, 10, 10, 10}

Returns: 0.08146000000000005

Any two (or more) of these five subtasks are enough.

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)2024, TopCoder, Inc. All rights reserved.