TopCoder problem "OptimalTax" used in TCO05 Round 3 (Division I Level Two)



Problem Statement

    

A city has several different tax schemes. In each scheme, the taxpayer pays a percentage of his income plus a fixed base amount every year. Each citizen is free to choose an optimal tax scheme for his income after the end of each year.

You will be given two int[]s, fixedBase and percent (elements with equal indices describe the same tax scheme). Given an index of a tax scheme, return the minimal non-negative income this scheme is optimal for (choosing any other tax scheme results in a tax which is strictly greater). If this scheme is not optimal for any income, return -1.

 

Definition

    
Class:OptimalTax
Method:optimalIncome
Parameters:int[], int[], int
Returns:double
Method signature:double optimalIncome(int[] fixedBase, int[] percent, int index)
(be sure your method is public)
    
 

Notes

-The return value must be within 1e-9 absolute or relative error of the actual result
 

Constraints

-fixedBase and percent will contain between 2 and 50 elements, inclusive.
-fixedBase and percent will contain the same number of elements.
-Each element of fixedBase will be between 0 and 10000, inclusive.
-Each element of percent will be between 0 and 100, inclusive.
-index will be between 0 and number of elements in fixedBase - 1, inclusive.
 

Examples

0)
    
{10, 5, 3}
{0, 10, 20}
0
Returns: 50.0
The first scheme forces a taxpayer to pay 10 units of tax regardless of income. The second scheme leads to the same tax for an income of 50. The first scheme is optimal for any income greater than that.
1)
    
{6000, 435, 3325, 2345, 0}
{ 0, 45, 33, 13, 100}
3
Returns: 5968.75
2)
    
{1, 0, 0, 0}
{9, 6, 7, 8}
0
Returns: -1.0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4013

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8016&pm=4013

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Math