#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; }
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; } |