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
#include <iostream>
#include <string>
using namespace std;

int main()
{
    unsigned long long ile = 0;

    string obecnaStr = "",
            poprzedniaStr = "";
    unsigned long long obecnaLength = 0,
            poprzedniaLength = 0;

    unsigned long long j;

    unsigned long long ileZmienic = 0;

    bool tenSamCiag = false;

    unsigned long long liczba9OdKonca = 0;

    cin >> ile;
    cin >> poprzedniaStr;

    for(unsigned long long l = 1; l < ile; l++)    { // po wszystkich liczbach

        cin >> obecnaStr;   // liczba w stringu

        poprzedniaLength = poprzedniaStr.length();
        obecnaLength = obecnaStr.length();

        // najlatwiej
        // poprzednia jest krotsza od obecnej, czyli na pewno mniejsza
        if(poprzedniaLength < obecnaLength)
            ;
        else if(poprzedniaLength == obecnaLength)    {
            if(poprzedniaStr < obecnaStr)   // są równe długością, ale poprzednia jest leksykograficznie mniejsza od obecnej, czyli również liczbowo
                ;
            else {  // jeśli są równe długością i leksykograficznie, to są równe liczbowo; pomoże tylko dopisanie '0' na końcu
                obecnaStr += '0';                  // lub // są równe długością, ale poprzednia jest leksykograficznie większa, czyli w istocie jest większą liczbą; pomoże tylko '0' na końcu
                ileZmienic++;
            }
        }
        // najtrudniejszy
        // jeśli poprzednia jest dłuższa niż obecna, czyli naprawdę większa
        // ??? dokad liczby sa takie same i ile mozna zmienic ???
        // ??? i co z '9' na koncu ???
        else    {
            tenSamCiag = true;  // jak długo są podobne?
            for(unsigned long long i = 0; i < obecnaLength; i++)    {
                if(obecnaStr[i] > poprzedniaStr[i])  {    // jeśli któraś cyfra od początku jest WIĘKSZA, to da się tylko dodać 000...
                    // tylko ile 000?
                    for(j = obecnaLength; j < poprzedniaLength; j++)  {
                        obecnaStr += '0';
                    }
                    ileZmienic = ileZmienic + poprzedniaLength - obecnaLength;
                    tenSamCiag = false; // nie są podobne!
                    break;  // nie trzeba dalej sprawdzać ciągu
                }
                else if(obecnaStr[i] < poprzedniaStr[i])  {    // jeśli któraś cyfra od początku jest MNIEJSZA, to da się ...
                    // tylko ile 000? // jedno więcej niż w poprzednim przypadku
                    for(j = obecnaLength; j <= poprzedniaLength; j++)  {
                        obecnaStr += '0';
                    }
                    ileZmienic = ileZmienic + poprzedniaLength + 1 - obecnaLength;
                    tenSamCiag = false; // nie są podobne!
                    break;  // nie trzeba dalej sprawdzać ciągu
                }
            }

            //jeśli po sprawdzeniu całości dostępnej z obecnej są takie same (do długości obecnej)
            if(tenSamCiag)
            {
                // jeśli nie ma 9 na końcu, to można przepisać do przedostatniej
                // a ostatnią zwiększyć o 1

                liczba9OdKonca = 0;
                if(poprzedniaStr[poprzedniaLength - 1] == '9') {
                        liczba9OdKonca = 1;
                    }
                for(j = poprzedniaLength - 2; j >= obecnaLength; j--)   {
                    if(poprzedniaStr[j] != '9') {
                        liczba9OdKonca = poprzedniaLength - j - 1;
                        break;
                    }
                }
                if(liczba9OdKonca >= (poprzedniaLength - obecnaLength)) {
                    for(j = obecnaLength; j <= poprzedniaLength; j++)  {
                        obecnaStr += '0';
                     }
                    ileZmienic = ileZmienic + poprzedniaLength + 1 - obecnaLength;
                }
                else    {
                    for(j = obecnaLength; j < poprzedniaLength - 1; j++)  {
                        obecnaStr += poprzedniaStr[j];
                    }
                    obecnaStr += (poprzedniaStr[j] + 1);
                    ileZmienic = ileZmienic + poprzedniaLength - obecnaLength;
                }
            }
        }

        poprzedniaStr = obecnaStr;
    }

    cout << ileZmienic;

    return 0;
}