GerrymanderEasy | Topcoder Archive

Problem Statement

Cucumber Boy is trying to be elected to the city council. In order to achieve that, he needs to show that he has a lot of support in some part of the city.

The city is divided into N districts. These are numbered from 0 to N-1. For each i, there are A[i] voters in district i, and out of them B[i] support Cucumber Boy.

Cucumber Boy must choose a part of the city: K or more districts with consecutive numbers. Cucumber Boy wants to maximize the proportion of votes in his favor. Formally, Cucumber Boy wants to maximize the value X/Y, where Y is the total number of voters in the chosen districts and X is the number of Cucumber Boy's supporters among them.

You are given the int[]s A and B with N elements each. You are also given the int K. Compute and return a real number: the largest value X/Y that can be achieved.

Definition

Class:: GerrymanderEasy
Method:: getmax
Parameters:: int[], int[], int
Returns:: double
Method signature:: double getmax(int[] A, int[] B, int K)
(be sure your method is public)

Notes

The returned value must have an absolute or relative error less than 1e-9.

Constraints

A will contain between 1 and 1,000 elements, inclusive.
A and B will contain the same number of elements.
For each i, A[i] will be between 1 and 10,000, inclusive.
For each i, B[i] will be between 0 and A[i], inclusive.
K will be between 1 and the number of elements in A, inclusive.

Examples

```
{5,1,2,7}
```
```
{4,0,2,2}
```
```
2
```
```
Returns: 0.75
```
The optimal solution is to choose districts 0, 1, and 2. The total number of voters will be Y = 5+1+2 = 8. The total number of Cucumber Boy's supporters will be X = 4+0+2 = 6. Hence, the proportion of votes in Cucumber Boy's favor is X/Y = 0.75. Note that the chosen districts must have consecutive numbers. We are not allowed to choose only districts 0 and 2.

{12,34,56,78,90}

{1,1,1,1,1}

Returns: 0.08333333333333333

{10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

{3,1,4,1,5,9,2,6,5,3}

Returns: 5.4E-4

{123,4,46,88,22,34,564,87,56,311,886}

{0,0,0,0,0,0,0,0,0,0,0}

Returns: 0.0

Sometimes the answer will be 0.

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.