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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>

using namespace std;

/*
n - liczba kolejnych wynagrodzeń
a(i) - wynagrodzenie z umowy
b(i) - wynagrodzenie po zmianach

1 <= n <= 200000
1 <= a(i) <= 10^9

b(i) < b(i+1)
a(i) = prefix(b(i))

Przy pechowych danych prawie każde kolejne b(i) będzie o jedną cyfrę dłuższe
od b(i-1) co dla ostatniej liczby może nam dać około n cyfr, czyli ostatnią 
liczbę rzędu 10^200000. Nie pomieścimy tego na żadnym typie całkowitym.

Dla takiego przypadku dotychczas dodanych zer mogło być około (200000^2)/2, 
czyli 2*10^10. Zmieści się w long long.


Gdy poniżej używam prefix(x) i sufix(x), to zakładam, 
że x = prefix(x) + sufix(x).

Zawsze staram się podbić bieżącą liczbę o możliwie najmniejszą wartość, więc:
* jeśli a(i) > b(i-1) => b(i) := a(i),
* jeśli a(i) = b(i-1) => b(i) := a(i) + "0",
* jeśli a(i) < b(i-1) to :
  * jeśli a(i) > prefix(b(i-1)) 
    => b(i) := a(i) + "0" * length(sufix(b(i-1)))
  * jeśli a(i) < prefix(b(i-1)) 
    => b(i) := a(i) + "0" * (length(sufix(b(i-1))) + 1)
  * jeśli a(i) = prefix(b(i-1)) to:
    * jeśli sufix(b(i-1)) to same "9" 
      => b(i) := a(i) + "0" * (length(sufix(b(i-1))) + 1),
    * wpp. => b(i) := b(i-1) + 1
*/


/* x < y => <0
   x = y => 0
   x > y => >0 */
int compareNumbers(const string& x, const string& y)
{
    if (x.length() < y.length()) 
    {
        return -1;
    }
    if (x.length() > y.length()) 
    {
        return 1;
    }
    return x.compare(y);
}

int main() 
{
    long n;
    cin >> n;

    long long addedDigits = 0;
    string prevB = "";
    string a;
    long aNum;
    for (int i = 0; i < n; ++i) 
    {
        cin >> aNum;
        a = to_string(aNum);
        int cmp = compareNumbers(a, prevB);

        // a(i) > b(i-1) => b(i) := a(i)
        if (cmp > 0) 
        {
            prevB = a;
        } 
        // a(i) = b(i-1) => b(i) := a(i) + "0"
        else if (cmp == 0) 
        {
            a.push_back('0');
            ++addedDigits;
            prevB = a;
        }
        // a(i) < b(i-1)
        else 
        {
            int cmpPrefix = prevB.compare(0, a.length(), a);

            // a(i) > prefix(b(i-1)) => b(i) := a(i) + "0" * length(sufix(b(i-1)))
            if (cmpPrefix < 0) 
            {
                addedDigits += prevB.length() - a.length();
                a.resize(prevB.length(), '0');
                prevB = a;
            }
            // a(i) < prefix(b(i-1)) => b(i) := a(i) + "0" * (length(sufix(b(i-1))) + 1)
            else if (cmpPrefix > 0)
            {
                addedDigits += prevB.length() + 1 - a.length();
                a.resize(prevB.length() + 1, '0');
                prevB = a;
            }
            // a(i) = prefix(b(i-1))
            else
            {
                size_t notNineIdx = prevB.find_last_not_of("9");
                // sufix(b(i-1)) to same "9" => b(i) := a(i) + "0" * (length(sufix(b(i-1))) + 1)
                if ((notNineIdx == std::string::npos) || (notNineIdx < a.length()))
                {
                    addedDigits += prevB.length() + 1 - a.length();
                    a.resize(prevB.length() + 1, '0');
                    prevB = a;
                }
                // wpp. => b(i) := b(i-1) + 1
                else
                {
                    addedDigits += prevB.length() - a.length();
                    ++prevB[notNineIdx];
                    int limit = prevB.length();
                    for (int i = notNineIdx + 1; i < limit; ++i)
                    {
                        prevB[i] = '0';
                    }
                }
            }
        }
    }

    cout << addedDigits;
    return 0;
}