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 <iostream>
#include <cstdio>
#include <utility>

#define DEBUG 0

#define F first
#define S second
#define MP(a,b) make_pair(a, b)
#define LLI long long int
using namespace std;

int akt[20], p = 300100, k = 300099, t = 0;
LLI wynik, n = 0, l, m;
pair<int, int> pop[1000100];

int dl(int a);
int por();
void add();
void przyp();

void wypisz();
//***************************************************************************************
int main()
{
    for(int i = 0; i < 1000000; i++) pop[i] = MP(-1, 1e9);
    scanf("%lld", &m);
    while(m--) {
        scanf("%lld", &l);
        n = dl(l);
        if (DEBUG) cout << "L: " << l << endl;
        if (p > k) { przyp(); continue; }
        int pr = por();
        if (DEBUG) cout << "PR: " << pr << endl;
        if (DEBUG) cout << "N: " << n << endl;
        if (n > k - p + 1) { k = p + n - 1, przyp(); continue; }
        if (pr < 0) 
            wynik += abs (n - k + p - 1) + 1,
            k++,
            przyp();
        else if (pr == 0)
            wynik += abs (n - k + p - 1),
            add();
        else
            wynik += abs (n - k + p - 1),
            przyp();
        if (DEBUG) cout << "WYNIK: " << wynik << endl;
        if (DEBUG) wypisz();
        if (wynik < 0) { cout << "EEE\n"; return 0; }
    }
    printf("%lld\n", wynik);
}

int dl(int a)
{
    if (a == 0) return 1;
    else {
        int d = 0;
        while(a != 0)
            akt[d] = a % 10,
            d++,
            a /= 10;
        for(int i = 0; i < (d+1) / 2; i++) swap(akt[i], akt[d - 1 - i]);
        return d; 
    }
}

/* 0 - rowne
  -1 - akt < pop
   1 - akt > pop */
int por()
{
    for(int i = 0; i < n; i++) {
        if (pop[p+i].S != t) pop[p+i] = MP(0, t);
        if (pop[p+i].F > akt[i]) return -1;
        else if (pop[p+i].F < akt[i]) return 1;
    }
    return 0;
}

void add()
{
    int z = 1, md = k;
    for(int i = k; i >= p; i--) {
        if (pop[i].S != t) pop[i] = MP(0, t);
        pop[i].F += z;
        md = i;
        if (pop[i].F == 10) pop[i].F = 0, z = 1;
        else break;
    }
    if (md - p + 1 <= n) 
        wynik++,
        k++,
        przyp();
}

void przyp()
{
    t++;
    k = max((LLI)k, p + n - 1);
    for(int i = 0; i < n; i++) pop[p+i] = MP(akt[i], t);
}


void wypisz()
{
    cout << p << " " << k << endl;
    for(int i = p; i <= k; i++) cout << pop[i].F << " ";
    cout << "\n";
    for(int i = p; i <= k; i++) cout << pop[i].S << " ";
    cout << "\n";
}