DigitStringDiv1
TCO19 SRM 741 · 2018-10-30 · by Blue.Mary
Problem Statement
You are given a digit string S and a positive integer X. We are going to erase some (possibly none, but not all) characters of S. While doing so, we have the following goals:
- The string formed by the remaining characters (in their original order) cannot begin with the digit '0'.
- When that string is converted to a number, its value must be strictly greater than the given X.
Two ways of erasing characters are different if there is an index i such that S[i] got erased in exactly one of the two ways.
Compute and return the number of ways in which we can erase some characters and achieve the goals stated above.
Constraints
- S will contain between 1 and 47 characters, inclusive.
- Each character of S will be a digit ('0'-'9').
- X will be between 0 and 777,444,111, inclusive.
"0" 1 Returns: 0
"101" 9 Returns: 3
We can produce one of the strings "10", "11", and "101".
"471" 47 Returns: 2
"00000000000000000000000000000000000000000000000" 777444111 Returns: 0
"99999999999999999999999999999999999999999999999" 777444111 Returns: 140737098539113
"2222" 97 Returns: 5
We have one way to produce the string "2222" and four ways to produce the string "222".
Submissions are judged against all 56 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DigitStringDiv1 with a public method long long count(string S, int X) · 56 test cases · 2 s / 256 MB per case