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.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.