- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: September, 2016 -
**Competitors who opened the problem**: 408 -
**Competitors who submitted a solution**: 221 -
**Number of correct solutions**: 134 -
**Accuracy (percentage correct vs those who opened)**: 32.8% -
**Average Correct Time**: 27 minutes, 5 seconds.

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 *(10 ^{18})*, which means that you need to be careful calculating

T = 0; while (T <= S) T = 10*T + d;When

UNIX>So, instead of using numbers to calculatecat badloop.cpp#include#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.cppUNIX>a.out9 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; } |