Connection Status:
Competition Arena > Decimal

Decimal

TCI '02 Round 1 B · 2002-10-10 · by lars2520

TCI '02 Round 1 B · 2002-10-10 · by lars2520 · Advanced Math
Class Name: Decimal
Return Type: int[]
Method Name: find
Arg Types: (int, int, int, int)
Problem Statement

Problem Statement

A rational number is a number which can be expressed as a ratio of two integers. In addition, all rational numbers can be expressed as a decimal number with some repeating periodic part (in some cases the repeating part is 0). For example 1/7 = 0.1428571428571428... with 142857 repeating itself infinitely. Other fractions have some finite number of non-repeating digits before the periodic part begins. For example, 1/6 = 0.166666... starts with a 1 and then settles into repeating 6's.

Your task is to write a class Decimal with a method find that takes four int's: lower, upper, lowerLength, and upperLength. Your method must find all integers n between lower and upper, inclusive, where the repeating portion of the decimal representation of 1/n has between lowerLength and upperLength digits, inclusive. You should return all of the numbers you find in a int[] sorted in increasing order.

Constraints

  • lower and upper will be between 1 and 1000000, inclusive.
  • upper will be greater than or equal to lower.
  • The difference between upper and lower will be at most 100.
  • lowerLength and upperLength will be between 1 to 1000000, inclusive.
  • upperLength will be greater than or equal to lowerLength.
Examples
0)
1
10
1
1
Returns: { 1,  2,  3,  4,  5,  6,  8,  9,  10 }

1/1 = 1.00000... 1/2 = 0.50000... 1/3 = 0.33333... 1/4 = 0.25000... 1/5 = 0.20000... 1/6 = 0.16666... 1/8 = 0.12500... 1/9 = 0.11111... 1/10 = 0.10000... Thus, all of the numbers other than 7 eventually settle into a repeating sequence of exactly 1 digit.

1)
999899
999999
1
1000
Returns: { 999900,  999908,  999936,  999950,  999954,  999960,  999975,  999980,  999990,  999996,  999999 }
2)
888899
888999
100000
1000000
Returns: { 888909,  888911,  888917,  888919,  888922,  888923,  888926,  888931,  888938,  888941,  888946,  888947,  888961,  888967,  888971,  888973,  888974,  888977,  888981,  888982,  888983,  888988,  888989,  888997 }
3)
55
56
1
10
Returns: { 55,  56 }

1/55 = 0.01818... (18 is repeating) 1/56 = 0.017857142857142... (857142 is repeating) Both of these numbers have between 1 and 10 digits in its repeating part.

4)
200
300
10
20
Returns: { 204,  209,  212,  228,  237,  247,  248,  255,  265,  266,  272,  279,  285 }
7)
999983
999983
999982
999982
Returns: { 999983 }

The repeating part of 1/999983 is 999982 digits long!

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

Coding Area

Language: C++17 · define a public class Decimal with a public method vector<int> find(int lower, int upper, int lowerLength, int upperLength) · 54 test cases · 2 s / 256 MB per case

Submitting as anonymous