ASCIISum
2020 TCO Semi 1 · 2020-11-12 · by misof
Problem Statement
Consider the following function:
def f(n): return sum( ord(x) for x in str(n) )
(The function writes n as a string and then adds up the ASCII values of its digits.)
If we start from some positive integer n and repeatedly apply this function f, we will get an infinite sequence of positive integers. It's fairly obvious that for any starting number n this sequence must eventually become periodic. Perhaps more surprisingly, each of these sequences eventually becomes constant. Let final(n) denote that constant for the sequence starting with n.
Given the
Notes
- The ASCII values of the characters '0', '1', ..., '8', '9' are 48, 49, ..., 56, 57. (I.e., the character representing the digit x has ASCII value 48+x.)
Constraints
- N will be between 1 and 10^18 - 1, inclusive.
3 Returns: 465
We have: f(1) = 49, f(49) = 109, f(109) = 154, and f(154) = 154 f(2) = 50, f(50) = 101, f(101) = 146, f(146) = 155, and f(155) = 155 f(3) = 51, f(51) = 102, f(102) = 147, f(147) = 156, and f(156) = 156 Hence, the sum final(1) + final(2) + final(3) equals 154 + 155 + 156.
6 Returns: 930
We now also have final(4) = 157, final(5) = 158, and final(6) = 150.
10 Returns: 1543
The next few values are final(7) = 151, final(8) = 152, final(9) = 153, and final(10) = 157.
999999999999 Returns: 454936082
Don't forget to do calculations modulo 10^9 + 7, and watch out for integer overflows.
1 Returns: 154
Submissions are judged against all 181 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ASCIISum with a public method int total(long long N) · 181 test cases · 2 s / 256 MB per case