SameDigits
SRM 358 · 2007-07-17 · by icanadi
SRM 358 · 2007-07-17 · by icanadi · Dynamic Programming
Problem Statement
Problem Statement
Let's define a function f over positive integers which returns the longest subsequence of the same digits in the number.
So, f(344488) = 3 and f(123) = 1.
Given an int n and int k, return an int stating how many numbers, no longer than n digits has f(x) = k. Return the result modulo 44444444.
So, f(344488) = 3 and f(123) = 1.
Given an int n and int k, return an int stating how many numbers, no longer than n digits has f(x) = k. Return the result modulo 44444444.
Constraints
- n and k will be between 1 and 1000, inclusive.
Examples
0)
2 2 Returns: 9
The numbers are 11, 22, 33, 44, 55, 66, 77, 88 and 99.
1)
2 1 Returns: 90
2)
3 2 Returns: 171
3)
10 124 Returns: 0
4)
100 3 Returns: 23156827
Submissions are judged against all 44 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SameDigits with a public method int howMany(int n, int k) · 44 test cases · 2 s / 256 MB per case