That helps us spot the recursion for a dynamic programming solution. Find the number T, which is the largest number less than or equal to S which is composed of the same digit repeated. In the example above, T is 1111. And then find the number I, which is the first digit of T, followed by all zeros. In the example above, I is 1000.
Solve the problem recursively on (S-T), and add I to the solution. In the example above, you solve the problem on 259, whose answer is 234, and add 1000, so that the answer to 1370 is 1234. Put in a base case, memoize, and you're done. Or are you? Are there things that can go wrong?
Let's think of a few. First, what happens when S is less than 1111? In that case, you'll have to set T to 999, so you'll need to be ready for that case. That will help with some problems -- for example, when S is 1001, then we'll set T to 999, and sove the subproblem with S equals 2. The answer will be 902. That works.
However, it doesn't always work. Suppose S is 1110. Then T is 999, and you'll solve the problem recursively on (1110-999) = 111. That answer is 100, but you can't add it to 900 -- both the answer and T are three digits. You'll need to account for that problem.
Finally, the constraints present another challenge. S can be as big as (1018), which means that you need to be careful calculating T. When I first tried to solve this problem, I got tripped up on this issue. My loop was the following:
T = 0; while (T <= S) T = 10*T + d;When S was 999,999,999,999,999,999 (example 5), the loop above calculates the wrong value of T, because 10(999,999,999,999,999,999) overflows. I'll illustrate:
UNIX> cat badloop.cpp #includeSo, instead of using numbers to calculate T and I, I used strings. I also converted the return value of the recursive call to a string, so that I could make sure that it had fewer digits than T.#include using namespace std; int main() { long long S, T; int d; S = 999999999999999999LL; T = 0; while (T <= S) { T = T*10 + 9; printf("%lld\n", T); } return 0; } UNIX> g++ badloop.cpp UNIX> a.out 9 99 999 9999 99999 999999 9999999 99999999 999999999 9999999999 99999999999 999999999999 9999999999999 99999999999999 999999999999999 9999999999999999 99999999999999999 999999999999999999 -8446744073709551617 7766279631452241919 UNIX>
Finally, you actually don't have to memoize this program, because there is no exponential blowup of recursive calls -- each call to findX() makes at most one recursive call, to a value that is roughly a factor of 10 smaller. No memoization necessary!
The solution is in Solution.cpp.
/* Topcoder SRM 699, D2, 500-pointer: LastDigit.
* James S. Plank
* Fri Nov 25 11:20:03 EST 2016
*/
#include <string>
#include <map>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class LastDigit {
public:
long long findX(long long S);
};
long long LastDigit::findX(long long S)
{
long long T; /* T is the biggest number <= S with all repeated digits. */
long long I; /* I is the first digit of T with all zeros. */
long long RV; /* This is the return value of the recursive call */
string SS; /* The string version of S. */
string ST; /* The string version of T. */
string SI; /* The string version of I. */
string SRV; /* The string version of RV. */
char buf[50]; /* This is to convert long long's to strings. */
int i;
/* Base case. */
if (S < 10) return S;
/* Create string version of S. */
sprintf(buf, "%lld", S);
SS = buf;
/* Create ST from SS. If it's too big, then either subtract
all 1's from it, or make it be all 9's, and one digit smaller. */
ST = buf;
for (i = 1; i < ST.size(); i++) ST[i] = ST[0];
if (ST > SS) {
if (ST[0] != '1') {
for (i = 0; i < ST.size(); i++) ST[i]--;
} else {
for (i = 0; i < ST.size(); i++) ST[i] = '9';
ST.pop_back();
}
}
/* Now, create SI, and convert SI and ST back to I and T */
SI = ST;
for (i = 1; i < SI.size(); i++) SI[i] = '0';
sscanf(ST.c_str(), "%lld", &T);
sscanf(SI.c_str(), "%lld", &I);
/* Make the recursive call, and check to make sure that the return
value is not too big. */
RV = findX(S-T);
if (RV != -1) {
sprintf(buf, "%lld", RV);
SRV = buf;
if (SRV.size() == ST.size()) RV = -1;
}
/* If the return value is ok, then add I, and you're done. */
if (RV != -1) RV += I;
return RV;
}
|