TheLuckySequence
SRM 403 · 2008-05-29 · by Vasyl[alphacom]
Problem Statement
John thinks 4 and 7 are lucky digits, and all other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation.
A lucky sequence is a sequence of length numbers A[0], A[1], ..., A[length - 1] that satisfies all of the following properties:
- Each number A[i] is lucky, where 0 <= i < length.
- For each i, where 0 <= i < length, there exists at least one j such that A[i] = numbers[j].
- For each i, where 0 <= i < length - 1, the last digit of A[i] is the same as the first digit of A[i + 1].
You are given a
Notes
- Two lucky sequences A[0], A[1], ..., A[length - 1] and B[0], B[1], ..., B[length - 1] are considered distinct if there exists i, 0 <= i < length, such that A[i] ≠ B[i].
Constraints
- numbers will contain between 1 and 50 elements, inclusive.
- Each element of numbers will be between 1 and 1,000,000,000, inclusive.
- length will be between 1 and 1,000,000,000, inclusive.
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
1
Returns: 2
There are only two lucky numbers among these ten integers.
{47, 74, 47}
3
Returns: 2
We can construct only two different sequences (47, 74, 47) and (74, 47, 74).
{100, 4774, 200, 747, 300}
47
Returns: 2
{44, 47, 74, 77}
2
Returns: 8
{44, 47, 74, 77, 44, 47, 74, 77}
1000000000
Returns: 1133762585
Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheLuckySequence with a public method int count(vector<int> numbers, int length) · 96 test cases · 2 s / 256 MB per case