Neaten

TCO07 Sponsor 2 · 2007-03-07 · by dgoodman

TCO07 Sponsor 2 · 2007-03-07 · by dgoodman · Math, Search, String Manipulation

Show categories

Class Name: Neaten

Return Type: int

Method Name: shortest

Arg Types: (int, string)

Problem Statement

We have a real number that we want to approximate with as few characters as possible. We require that either the absolute error or the relative error must be strictly less than 10^-k. The absolute error is the absolute difference between the values of the shortened version and the original. The relative error is the absolute error divided by the absolute value of the original (or is taken to be infinity if the original is 0).

We want the shortened version expressed as a string of digits, possibly with a decimal point. The original number is given to us in that form. Given k and number, return the number of characters in the shortest approximation.

Constraints

k will be between 1 and 50, inclusive.
number will contain between 1 and 50 characters, inclusive.
number will contain at most one decimal point ('.').
Other than '.', number will contain only digits ('0'-'9').
number will contain at least one digit.

Examples

2
"00."
Returns: 1

The approximation "0" has 1 character and has an absolute error of 0.

2
".20050"
Returns: 2

The approximation ".2" has 2 characters and has an absolute error of .0005 (which is less than .01).

3
"10000"
Returns: 4

The approximation "9995" has a relative error of 5/10000 (which is less than .001).

1
"1001.2"
Returns: 3

//int k=1; String num = "1001.2"; //return "999", OY!

1
"999.9"
Returns: 3

//int k=1; String num = "999.9"; //return "999"

4
".00000005"
Returns: 1

//int k=4; String num = ".00000005"; //return "0"

4
"3.1127"
Returns: 5

//int k=4; String num = "3.1127"; //return "3.113"

1
"6.94"
Returns: 1

//int k=1; String num = "6.94"; //return "7"

2
"0.50"
Returns: 2

//int k=2; String num = "0.50"; //return ".5"

1
"0.90"
Returns: 2

Please note that the error must be strictly less than 10-k.

10)

1
"0.901"
Returns: 1

//int k=1; String num = "0.901"; // "1"

11)

2
"9.99"
Returns: 2

//int k=2; String num = "9.99"; //"10"

12)

1
"9.901"
Returns: 1

//int k=1; String num = "9.901"; // "9"

13)

1
"9.9"
Returns: 1

int k=1; String num = "9.9"; //1 ("9"!)

21)

5
"9100.909"
Returns: 4

"9451.909"

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

Coding Area

Language: C++17 · define a public class Neaten with a public method int shortest(int k, string number) · 40 test cases · 2 s / 256 MB per case