TopCoder problem "SegmentDisplay" used in TCHS SRM 54 (Division I Level Two)



Problem Statement

    

You have a digital display with an infinite number of positions. Each position consists of 7 segments - 4 vertical and 3 horizontal. Lighting certain segments within a position allows you to represent different decimal digits on the display:

                   

You can use the display to represent different non-negative integers. To represent an integer you need to show its digits, in order, on consecutive display positions. The integers you represent on the display cannot have extra leading zeros.

You are given an int n, and your task is to count each integer that can be represented by lighting exactly n segments. Return this count modulo 1,000,000,007.

 

Definition

    
Class:SegmentDisplay
Method:howManyNumbers
Parameters:int
Returns:int
Method signature:int howManyNumbers(int n)
(be sure your method is public)
    
 

Constraints

-n will be between 0 and 500000, inclusive.
 

Examples

0)
    
2
Returns: 1
Using 2 segments you can represent an integer 1.
1)
    
1
Returns: 0
One segment is not enough to display even one digit.
2)
    
6
Returns: 7
Using 6 segments you can represent integers 0, 6, 9, 14, 41, 77, 111.
3)
    
10
Returns: 59
4)
    
0
Returns: 0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13523&pm=9748

Writer:

mateuszek

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming