TallyMarksSystem
SRM 843 · 2023-01-03 · by misof
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.
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.
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.
Submissions are judged against all 112 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TallyMarksSystem with a public method int construct(int N) · 112 test cases · 2 s / 256 MB per case