Official

E - Σ[k=0..10^100]floor(X/10^k) Editorial by en_translator


First, note the constraint \(X < 10^{500000}\), which is too large to store in an ordinary integer type.
Thus, we have to receive \(X\) as a string and solve it.
Let’s consider how the desired value can be obtained, taking \(X=123456\) as the example.
Horizontally aligned terms are not really easy to understand; let’s align the terms (of at least \(1\)) vertically, in the manner of column addition. Note that the fractional part of each term is truncated before added.

 123456
  12345 .6
   1234 .56
    123 .456
     12 .3456
+     1 .23456
-------
 137171

Here, we can see that “the sum of all the digits except for the least significant \((k-1)\) digits contributes the \(k\)-th least significant digit of the result.” Actually, we can supplement the following process to the column addition above.

 123456
  12345
   1234
    123
     12
+     1
-------
     21
    15
   10
   6
  3
+1
-------
 137171

We need to implement this (including carries).

There are several ways of implementations; one is to determine from the least significant place to the most, roughly through the following steps:

  1. Initialize \(s\) with the sum of digits of \(X\), and \(c=0\).
  2. Add \(s\) to \(c\).
  3. Find the remainder of \(c\) divided by \(10\). Determine the digit of the answer currently focused on to be the remainder.
  4. Divide \(c\) by \(10\) and truncate the fractional part. This corresponds to the carry.
  5. Subtract from \(s\) the currently focused digit of \(X\). (If there is no such digit, subtract \(0\).) At this point, \(s\) is the sum of all digits of \(X\), except for the current and less significant digits.
  6. Repeat the flow from 2. through 5. until all the digits of \(X\) are consumed and \(c=0\).

Sample code (C++)

#include<bits/stdc++.h>

using namespace std;

int main(){
  string x;
  cin >> x;
  int s=0,c=0;
  for(auto &nx : x){s+=(nx-'0');}
  string res;
  for(int i=x.size()-1;;i--){
    c+=s;
    res.push_back('0'+(c%10));
    c/=10;
    if(i>=0){s-=(x[i]-'0');}
    if(i<=0 && c==0){break;}
  }
  reverse(res.begin(),res.end());
  cout << res << '\n';
  return 0;
}

posted:
last update: