Connection Status:
Competition Arena > DigitalCounter

DigitalCounter

TCO09 Qual 2 · 2009-02-24 · by misof

TCO09 Qual 2 · 2009-02-24 · by misof · Dynamic Programming, Greedy, Search
Class Name: DigitalCounter
Return Type: long
Method Name: nextEvent
Arg Types: (string)
Problem Statement

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.

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)
"888888888888888"
Returns: 1000000000000000
103)
"007"
Returns: 11

Note that the input can have leading zeroes.

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

Coding Area

Language: C++17 · define a public class DigitalCounter with a public method long long nextEvent(string current) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous