BackupMedia | Topcoder Archive

Problem Statement

Backup media come in many different forms, such as optical discs and magnetic tapes. Each medium has a reliability and a cost associated with it. The reliability of a particular medium is given as an integer, x, where the probability of the medium failing is x%. By backing up files on more than one medium, or by backing up files on the same medium more than once, the probability of all backups failing can be reduced. For example, if a file is backed up on a specific medium twice, the probability that both copies will fail is x*x/10000. Similarly, if a file is backed up on two different mediums, with failure probabilities of x% and y%, the probability that both copies will fail is x*y/10000. However, backing up files multiple times is more expensive.

Given an int, budget, giving the maximum amount of money to spend, determine the minimum probability of failure that can be achieved by backing up files on some combination of different media, or multiple copies of the same medium. You will be given a int[], cost, and a int[], reliability, representing the costs and the reliabilities of the various media. Corresponding elements of cost and reliability represent a single backup medium.

Definition

Class:: BackupMedia
Method:: minProb
Parameters:: int[], int[], int
Returns:: double
Method signature:: double minProb(int[] cost, int[] reliability, int budget)
(be sure your method is public)

Notes

Your return must have an error less than 1e-9.

Constraints

budget will be between 1 and 1,000,000,000, inclusive.
Each element of cost will be between 1 and 100,000, inclusive.
Each element of reliability will be between 1 and 10, inclusive.
cost and reliability will each contain between 1 and 50 elements, inclusive.
cost and reliability will contain the same number of elements.
At least one element of cost will be less than or equal to budget.

Examples

```
{5,6,7}
```
```
{10,5,3}
```
```
15
```
```
Returns: 9.0E-4
```
The best thing to do in this case is to backup the data twice on the medium thats costs 7. This costs 7+7=14, and gives a failure probability of 0.0009.
```
{2}
```
```
{10}
```
```
10000000
```
```
Returns: 0.0
```
We can afford to backup the data 500 million times on this medium, which clearly gives an extremely low probability of failure - essentially 0.

{426,243,202}

{6,3,2}

Returns: 5.2428800000000005E-33

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.