Connection Status:
Competition Arena > ChartError

ChartError

TCCC05 Semi 2 · 2005-01-10 · by dgoodman

TCCC05 Semi 2 · 2005-01-10 · by dgoodman · Brute Force, Search
Class Name: ChartError
Return Type: double
Method Name: minErr
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Given a collection of real values, we want to represent them with a bar chart. Each value will be represented by a number of characters, and the bar chart will also display the value per character. For example, 
   Sales :  XXXXXXXXXX
   Profit:  XXXX
   Costs :  X
   (Each X has a value of 8.8)
In this bar chart, the "bar_value" of the first bar, which contains 10 characters, is 10*8.8 = 88.0

No bar in our chart is allowed to contain more than 15 characters, and each bar must contain an integer number of characters. Unfortunately, we may not be able to represent all the values exactly. We define the "bar_error" for a bar to be the absolute value of the difference between its bar_value and the true value that it is meant to represent. We define the "chart_error" for the bar chart to be the maximum bar_error.

Construct a class ChartError that contains a method minErr that is given a String[] val containing the values we want to represent in our bar chart as decimal strings, and that returns the minimum chart_error that is possible.

Constraints

  • val will contain between 1 and 50 elements inclusive.
  • Each element of val will contain between 2 and 10 characters inclusive.
  • Each element of val will consist of digits '0'-'9' and exactly one decimal point.
  • Each element of val will have no more than 2 digits before the decimal point.
Examples
0)
{"88.0","44.0","8.8"}
Returns: 0.0

Use 8.8 as the value per character. Then assign 10 characters to 88.0, 5 to 44.0, and 1 to 8.8. The bar chart might appear as in the problem description.

1)
{"9.0","10.","08.9",".1"}
Returns: 0.1

Use 1.0 as the value per character. Assign 10 characters to the second bar, 0 characters to the last bar, and 9 characters to the others. Then 0, 0, .1, and .1 are the resulting bar_errors.

2)
{"99.0","7.","74.32"}
Returns: 0.9923076923076862
3)
{"6.1","6.1","6.1"}
Returns: 0.0
4)
{"0.","0.0","99.","5.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0.","0."}
Returns: 1.4999999999999998

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

Coding Area

Language: C++17 · define a public class ChartError with a public method double minErr(vector<string> val) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous