Connection Status:
Competition Arena > OptimalTax

OptimalTax

TCO05 Sponsor 3 · 2005-08-16 · by Olexiy

TCO05 Sponsor 3 · 2005-08-16 · by Olexiy · Math
Class Name: OptimalTax
Return Type: double
Method Name: optimalIncome
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

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.

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)
{0, 1000}
{5, 3}
1
Returns: 50000.0
2)
{0, 1, 2}
{10, 5, 0}
1
Returns: -1.0

May cause precision problems.

3)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
8
Returns: -1.0
4)
{6000, 435, 3325, 2345, 0}
{ 0, 45, 33, 13, 100}
3
Returns: 5968.75

Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OptimalTax with a public method double optimalIncome(vector<int> fixedBase, vector<int> percent, int index) · 116 test cases · 2 s / 256 MB per case

Submitting as anonymous