1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <string>
#include <cmath>

std::string str_max = "0";
std::string tmp = "0";

struct change {
    int digitsAdded;
};

bool startsWith(std::string mainStr, std::string toMatch)
{
   if(mainStr.find(toMatch) == 0)
      return true;
   else
      return false;
}

void incrementMaxBy1() {
    for(int i = str_max.length()-1; i >= 0; i--) {
        char last = str_max.at(i);
        if(last == '9') {
            str_max[str_max.length()-1] = '0';
        } else { // last != '9'
            int last_int = last - '0';
            str_max[str_max.length()-1] = std::to_string(last_int + 1).at(0);
            return;
        }
        if(i == 0) {
            str_max = "1" + str_max;
        }
    }
}

bool isTmpBiggerThanMax() {
    //printf("(%s -> %s)", tmp.c_str(), str_max.c_str());
    if (str_max.size() > tmp.size()) {
        return false;
    } else if (str_max.size() < tmp.size()) {
        return true;
    }
    for(int i = 0; i < str_max.length(); i++) {
        char max_cur = str_max.at(i);
        char tmp_cur = tmp.at(i);
        int max_dig = max_cur - '0';
        int tmp_dig = tmp_cur - '0';
        //printf("(%d, %d, %d)", i, tmp_dig, max_dig);
        if (tmp_dig > max_dig) {
            return true;
        } else if (tmp_dig < max_dig) {
            return false;
        }
    }
    return false;
}

change getNext(unsigned long long prefix) {
   change c;
   c.digitsAdded = 0;
   std::string pref_str = std::to_string(prefix);
   int lenght_diff = str_max.length() - pref_str.length();
   if (startsWith(str_max, pref_str) && lenght_diff > 0) {
      if (str_max.at(str_max.length()-1) == '9') {
         //printf("a ");
         str_max = pref_str + std::string((lenght_diff+1), '0');
         c.digitsAdded = lenght_diff + 1;
      } else {
         //printf("b ");
         incrementMaxBy1();
         c.digitsAdded = lenght_diff;
      }
   } else {
      //printf("c ");
      tmp = pref_str + std::string(lenght_diff, '0');
      c.digitsAdded = lenght_diff;
       if (isTmpBiggerThanMax()) {
           //printf("c' ");
           str_max = tmp;
       } else {
           //printf("d' ");
           str_max = tmp + "0";
           c.digitsAdded = c.digitsAdded + 1;
       }
   }
   return c;
}

int main( ) {
   int n;
   unsigned long long changes = 0;
   unsigned long long current = 0;
   str_max.reserve(210000);
   tmp.reserve(210000);
   int i;

   scanf("%d", &n);
   for(i = 0 ; i < n; i++) {
      scanf("%lld", &current);
      tmp = std::to_string(current);
      if(isTmpBiggerThanMax()) {
          str_max = tmp;
      } else {
          change c = getNext(current);
          changes += c.digitsAdded;
      }
      //printf("%s", str_max.c_str());
   }
   //printf("\n");
   printf("%lld\n", changes);
   return 0;
}