DBBench | Topcoder Archive

Problem Statement

In a system that you are building, the biggest bottleneck is the database, and the performance of the system as a whole can be approximated simply by looking at the performance of the database. In order to generate some useful statistics about the database performance, you have determined what percentage of the system resources each query in the system requires, as well as what percentage of all of the queries are that type of query. For example, you might have two queries, one of which requires 2% of the system's resources, and accounts for 40% of the queries being run, and another of which requires 0.7% of the system's resources, and accounts for 60% of the queries being run. Your task is to figure out the maximum number of queries that can be run on the system at once, without using more than 100% of the resources. In the example above, you could run at most 81 queries at once. This would give you 81 * 0.4 = 32.4 of the first type of query, and 81 * 0.6 = 48.6 of the first type of query. The total resources being used would be 32.4 * 2% + 48.6 * 0.7% = 98.82%. Note that while it is not really possible to run a query 32.4 times, in this problem it will be easier to determine the total number of queries we can run if we don't constrain the number of times we run the queries to be integers. Also, note that the total percentage of the system resources being used with 81 queries is less than 100%, but if we tried to run 82 queries at once, we would exceed 100%, thus the most we can run is 81.

Each of the queries will be represented by an element of queries as "<percentOfQueries> <percentOfSystemResources>", where both <percentOfQueries> and <percentOfSystemResources> are real valued percentages.

Definition

Class:: DBBench
Method:: maxQueries
Parameters:: String[]
Returns:: int
Method signature:: int maxQueries(String[] queries)
(be sure your method is public)

Constraints

queries will contain between 1 and 50 elements, inclusive.
Each element of queries will be formatted exactly as: "<percentOfQueries> <percentOfSystemResources>" (quotes and angle brackets for clarity only).
In each element, <percentOfQueries> will be a sequence of digits ('0'-'9'), with an optional decimal point ('.') somewhere in the sequence, and will represent a number between 0.01 and 100, inclusive.
In each element, <percentOfSystemResources> will be a sequence of digits ('0'-'9'), with an optional decimal point ('.') somewhere in the sequence, and will represent a number between 0.01 and 100, inclusive.
The sum of <percentOfQueries> over all elements will be exactly 100.
Rounding errors will not come into play. In other words, there will never be a case where you could run some number of queries and it would use within 0.000001 of 100% of the total system resources.

Examples

```
{"40 2","60 0.7"}
```
```
Returns: 81
```
This is the example from the problem statement.
```
{"00100 0099"}
```
```
Returns: 1
```
```
{"0010 100.00","90 10"}
```
```
Returns: 5
```
Notice that even though the first query requires 100% of the system's resources, if we run 5 queries, we are only running that query 0.5 times, using 50% of the resources. Though this seems counterintuitive, one valid way to interpret it is that if 90% of the queries require 10% of the resources, and 10% of the queries require 100% of the resources, then the weighted average amount of resources required by a query is 0.9 * 0.1 + 0.1 * 1 = 0.19 = 19%. So, if the average query requires 19% of the resources, then clearly we can run at most 5 of them.

{"7.08 3.0005468696049067",
 "6.09 2.927543743005923",
 "6.05 1.8175508886801033",
 "9.06 0.4004342857814497",
 "8.14 2.2281611840964493",
 "11.09 2.826467735712054",
 "10.02 3.066355338938588",
 "2.08 4.002775125190415",
 "13.08 0.8883744919586389",
 "11.1 4.935868346665145",
 "5.11 0.8067228277510863",
 "11.1 0.893867331322834"}

Returns: 44

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.