TopCoderQuiz | Topcoder Archive

Problem Statement

Gogo is a programmer and has been participating in the TopCoder Quiz! He has finally advanced to the final stage: the TopCoder Quiz Onsite! Gogo will start with a balance of $15,000. He will be given N problems. For each problem, if he solves it, his balance is not changed otherwise his balance is multiplied by -1.

He has asked you (whom he sees as a friend) to help him. You decide to give him a slip of paper containing the solution to each problem. You claim that you are one of the staff and you can't guarantee that those solutions are correct. Specifically, you may give wrong solutions to at most maxWrong of the problems. You know the correct solution to each of the problems before the quiz starts and it is entirely up to you whether you want to give the wrong or correct solution to each problem.

When the i-th problem is given, there's a Ci / 100 chance that Gogo will submit a correct solution, a Wi / 100 chance that he will submit a wrong solution, and a (100 - Wi - Ci) / 100 chance that he can't come up with any solution and is forced to submit the solution in the paper you gave him.

You are given String[]s correctChance and wrongChance. Concatenate all the elements of correctChance (wrongChance) in the order they are given to obtain N single space-separated integers with no leading or trailing spaces. The i-th integer in this list is Ci (Wi).

You are not a very nice person and you have decided to give him the worst possible set of solutions, that is, the one that minimizes Gogo's expected balance after the game. Return this expected balance.

Definition

Class:: TopCoderQuiz
Method:: determineBalance
Parameters:: String[], String[], int
Returns:: double
Method signature:: double determineBalance(String[] correctChance, String[] wrongChance, int maxWrong)
(be sure your method is public)

Notes

Gogo has a strange sense of sportsmanship. Although he is cheating by asking for your help, he will not deliberately submit a wrong solution, that is, if he submits the wrong solution it must be either the solution you gave him or the solution he came up with with the Wi / 100 probability.
Gogo's performance on each problem is independent of his performance on each of the problems previously given to him.
You must provide all solutions to Gogo before the start of the competition. It's not possible to change them during the competition.
The returned value must have an absolute or relative error less than 1e-9.

Constraints

correctChance and wrongChance will contain between 1 and 50 elements, inclusive.
Each element of correctChance and wrongChance will contain between 1 and 50 characters, inclusive.
Each character in correctChance and wrongChance will be ' ' or '0'-'9'.
correctChance and wrongChance will be formatted as described in the problem statement.
Each integer in the concatenation of all the elements of correctChance and the concatenation of all the elements of wrongChance will have no leading zeroes.
Ci and Wi as described in the problem statement will be between 0 and 100, inclusive.
For each i, the sum of Ci and Wi as described in the problem statement will not exceed 100.
There will be the same number of integers in the concatenation of all the elements of correctChance and the concatenation of all the elements of wrongChance.
maxWrong will be between 0 and N, inclusive, where N is the number of integers in the concatenation of all the elements of correctChance.

Examples

```
{"25 25 25"}
```
```
{"25 25 25"}
```
```
1
```
```
Returns: -1875.0
```
Give the wrong solution for the first problem and correct solutions for the rest.
```
{"50 60 40"}
```
```
{"50 40 60"}
```
```
3
```
```
Returns: 0.0
```
Your interference has no effect on this particular quiz.
```
{"90 80 70"}
```
```
{"0 10 20"}
```
```
2
```
```
Returns: 3600.0
```
Unfortunately you can't make Gogo's balance negative.

{"20 3","0 40 ","10"}

{"2","0 10 0 ","3","0"}

Returns: -5760.000000000001

```
{"0"}
```
```
{"0"}
```
```
0
```
```
Returns: 15000.0
```
He gets $15,000 and we can expect him to treat his helpers.

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.