TopCoder problem "NumbersAndMatches" used in SRM 454 (Division I Level Two , Division II Level Three)



Problem Statement

    You have a piece of paper with exactly D positions laid out in a horizontal row. Each position looks like the following: 
 _
|_|
|_|
There are 7 line segments in each position, and each line segment can hold exactly one match. Matches cannot be placed anywhere except on the line segments.

You are given an integer N containing exactly D digits (with no leading zeroes). Spell out the number using matches on the paper. Each digit must occupy a single position. The following diagram shows how each digit should be formed: 
      _	               _        _                 _       _        _        _        _
 0 - | |  1 -  |  2 -  _|  3 -  _|  4 - |_|  5 - |_  6 - |_   7 -   |  8 - |_|  9 - |_|
     |_|      _|      |_        _|        |       _|     |_|        |      |_|       _|
After you lay out the initial arrangement, you are allowed to move up to K matches. You cannot discard matches or add new matches. After you make all your moves, the final arrangement must be valid (as described above) and the integer formed by the arrangement must contain the same number of digits as the original integer. Leading zeroes are allowed. Return the number of distinct integers that can be formed in this manner. Note that the original integer counts toward the total because it always obtainable by making 0 moves.
 

Definition

    
Class:NumbersAndMatches
Method:differentNumbers
Parameters:long, int
Returns:long
Method signature:long differentNumbers(long N, int K)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 10^18 - 1, inclusive.

-K will be between 1 and 126, inclusive.
 

Examples

0)
    
10
1
Returns: 4
Here you can compose numbers 10, 19, 16 and 70: 
      _                     _
  |  | |     ----->     |  | |
 _|  |_|               _|  |_|
      _                     _
  |  | |     ----->     |  |_|
 _|  |_|               _|   _|
      _                     _
  |  | |     ----->     |  |_ 
 _|  |_|               _|  |_|
      _                _    _
  |  | |     ----->     |  | |
 _|  |_|                |  |_|
1)
    
23
1
Returns: 4
This time it's possible to compose 22, 23, 25 and 33.
2)
    
66
2
Returns: 15
Here you can move up to 2 matches, so quite a lot of numbers can be composed. Note that you are allowed to move a match from one digit to another one, so, for example, it's possible to compose 38. However, you can't discard a match or add a new match, so, for example, you can't compose 55 or 88.
3)
    
888888888
100
Returns: 1
You are allowed to move a lot of matches, but still it's only possible to compose 888888888.
4)
    
444444444444444444
2
Returns: 1
Given that at most 2 matches can be moved, only the initial number can be composed.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13908&pm=10709

Writer:

Gluk

Testers:

PabloGilberto , kalinov , ivan_metelsky

Problem categories:

Dynamic Programming