Problem Statement
Time limit: 4 seconds.
In tally marks, any non-negative integer can be represented using zero or more symbols for the number 5, followed by between 0 and 4 symbols for the number 1.
For example, we can represent 3 as "111", 15 as "555", and 17 as "55511".
Of course, representing large numbers this way is impractical.
We will investigate what happens if we allow parentheses, addition and multiplication in the representation of our numbers. E.g., instead of "555555555555555555555555555555555555555511" it might be a better idea to represent 202 as "(55*55+1)*11" (i.e., ten times ten plus one, and all of that multiplied by two).
Given N, find and return the smallest number of tally symbols ('5's and '1's) in an expression of the above form that evaluates to N.
Definition
- Class:
- TallyMarksSystem
- Method:
- construct
- Parameters:
- int
- Returns:
- int
- Method signature:
- int construct(int N)
- (be sure your method is public)
Notes
- The expressions may contain an arbitrary amount of '+', '*', '(' and ')' symbols, we are only interested in minimizing the number of tally marks used.
Constraints
- N will be between 1 and 2,000,000, inclusive.
Examples
3
Returns: 3
The best way to represent the number 3 is still "111". (This is no longer the only optimal way, but there is no better one.)
4
Returns: 4
One best way to represent 4 is "1111", another is "(1+1)*(1+1)". Both use four tally mark symbols.
1
Returns: 1
2
Returns: 2
30
Returns: 3
The best way to represent 30 is "5*51", i.e., five times six. This representation uses three tally mark symbols: '5', '5', '1'.
202
Returns: 7
One optimal way to represent 202 is the one shown in the statement.
1301
Returns: 7
1692601
Returns: 14
5
Returns: 1
6
Returns: 2
7
Returns: 3
8
Returns: 4
9
Returns: 5
10
Returns: 2
11
Returns: 3
12
Returns: 4
13
Returns: 5
14
Returns: 5
15
Returns: 3
16
Returns: 4
17
Returns: 5
18
Returns: 5
19
Returns: 6
20
Returns: 4
21
Returns: 5
22
Returns: 5
23
Returns: 6
24
Returns: 6
25
Returns: 2
26
Returns: 3
27
Returns: 4
28
Returns: 5
29
Returns: 6
212
Returns: 8
247
Returns: 8
306
Returns: 6
377
Returns: 7
466
Returns: 8
629
Returns: 8
1152
Returns: 9
1264
Returns: 9
1290
Returns: 9
1502
Returns: 8
1616
Returns: 9
1651
Returns: 8
1793
Returns: 10
1817
Returns: 10
1924
Returns: 10
1961
Returns: 10
1972
Returns: 11
2068
Returns: 11
2182
Returns: 11
2308
Returns: 12
72160
Returns: 12
76386
Returns: 12
207810
Returns: 14
265592
Returns: 15
413407
Returns: 13
500981
Returns: 15
502821
Returns: 16
510014
Returns: 16
702698
Returns: 17
719446
Returns: 16
743644
Returns: 16
755450
Returns: 16
763328
Returns: 18
787086
Returns: 17
929805
Returns: 15
1080238
Returns: 17
1099776
Returns: 17
1172172
Returns: 15
1178789
Returns: 18
1208479
Returns: 17
1215293
Returns: 18
1262738
Returns: 18
1444405
Returns: 16
1505497
Returns: 19
1531537
Returns: 16
1600217
Returns: 17
1656234
Returns: 18
1765317
Returns: 16
1912726
Returns: 16
1914437
Returns: 17
1921198
Returns: 19
1928646
Returns: 17
1929747
Returns: 18
1931323
Returns: 18
1933139
Returns: 19
1937528
Returns: 16
1943890
Returns: 16
1946274
Returns: 18
1950276
Returns: 15
1954612
Returns: 16
1961738
Returns: 18
1964357
Returns: 16
1966624
Returns: 17
1970795
Returns: 17
1972779
Returns: 18
1979253
Returns: 17
1985040
Returns: 14
1988454
Returns: 17
1991646
Returns: 17
1997541
Returns: 18
9868
Returns: 13
199923
Returns: 16
31458
Returns: 14
1955996
Returns: 18
782247
Returns: 18
1997199
Returns: 18
392389
Returns: 17
1999999
Returns: 18
34646
Returns: 14