TopCoder problem "DigitalCounter" used in TCO09 Qual 2 (Division I Level Three)



Problem Statement

    

We have an N-digit digital counter that increments every second. The counter is cyclic: after it reaches 10^N - 1, it starts once again from zero.

Each digit is shown using the standard seven-segment display. The exact forms of all the digits are shown in the ASCII art below. 

    +   +---+   +---+   +   +   +---+
    |       |       |   |   |   |
    +   +---+   +---+   +---+   +---+
    |   |           |       |       |
    +   +---+   +---+       +   +---+

+---+   +---+   +---+   +---+   +---+
|           |   |   |   |   |   |   |
+---+       +   +---+   +---+   +   +
|   |       |   |   |       |   |   |
+---+       +   +---+       +   +---+

Each line segment that connects two adjacent '+' symbols represents a single lit segment. For example, '1' contains two lit segments, and '9' contains five lit segments.

You are given a String current that contains the current number shown by the counter.

The number of characters in current is equal to the number N of displayed digits.

Return the smallest positive number of seconds after which the counter will have the same total number of lit segments as it does now.

 

Definition

    
Class:DigitalCounter
Method:nextEvent
Parameters:String
Returns:long
Method signature:long nextEvent(String current)
(be sure your method is public)
    
 

Notes

-The digits 1, 2, ..., 9, and 0 have 2, 5, 5, 4, 5, 6, 3, 7, 5, and 6 lit segments, respectively.
-The counter does always show leading zeroes. (See Examples #3 and #5.)
-As the counter is cyclic, the answer always exists and for any valid input the answer fits into a long.
 

Constraints

-current will contain between 1 and 15 characters, inclusive.
-Each character in current will be a digit ('0'-'9').
 

Examples

0)
    
"1"
Returns: 10
No other digit has exactly two segments lit, thus the next time there will be two segments lit will be in 10 seconds.
1)
    
"3"
Returns: 2
In 2 seconds the display will show "5", and "5" and "3" both have exactly five lit segments.
2)
    
"9"
Returns: 3
In 3 seconds, the display will show "2".
3)
    
"99"
Returns: 5
The number "99" is shown using 5+5=10 lit segments. In 5 seconds, the display will show "04", with 6+4=10 lit segments again.
4)
    
"654371"
Returns: 43
5)
    
"007"
Returns: 11
Note that the input can have leading zeroes.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10324

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13757&pm=10324

Writer:

misof

Testers:

PabloGilberto , marian , ivan_metelsky

Problem categories:

Dynamic Programming, Greedy, Search