#include <iostream> #include <string> using namespace std; int compare(string ¤t, string &prev) { if (prev.size() < current.size()) return -100; return prev.compare(0, current.size(), current); } void incrementEnding(string &ending) { bool required = true; for (int i = ending.size()-1; required && i>=0; i--) { if (ending[i] < '9') { ending[i]++; required = false; } else { ending[i] = '0'; } } if (required) ending += '0'; } int main() { int N; string prev = "0"; string current; long long result = 0; cin >> N; while (prev.size()<16 && N--) { cin >> current; int compareResult = compare(current, prev); if (compareResult == -100) // no change required { } else if (compareResult < 0) // prev is smaller { result += prev.size() - current.size(); current.resize(prev.size(), '0'); } else if (compareResult > 0) // prev is greater { result += prev.size() - current.size() + 1; current.resize(prev.size() + 1, '0'); } else { string ending = prev.substr(current.size()); incrementEnding(ending); result += ending.size(); current += ending; } prev = current; } int prevSize = prev.size(); while (N-- > 0) { cin >> current; int compareResult = compare(current, prev); if (compareResult > 0) // prev is greater { prevSize++; } result += prevSize - current.size(); } cout << result << endl; 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 | #include <iostream> #include <string> using namespace std; int compare(string ¤t, string &prev) { if (prev.size() < current.size()) return -100; return prev.compare(0, current.size(), current); } void incrementEnding(string &ending) { bool required = true; for (int i = ending.size()-1; required && i>=0; i--) { if (ending[i] < '9') { ending[i]++; required = false; } else { ending[i] = '0'; } } if (required) ending += '0'; } int main() { int N; string prev = "0"; string current; long long result = 0; cin >> N; while (prev.size()<16 && N--) { cin >> current; int compareResult = compare(current, prev); if (compareResult == -100) // no change required { } else if (compareResult < 0) // prev is smaller { result += prev.size() - current.size(); current.resize(prev.size(), '0'); } else if (compareResult > 0) // prev is greater { result += prev.size() - current.size() + 1; current.resize(prev.size() + 1, '0'); } else { string ending = prev.substr(current.size()); incrementEnding(ending); result += ending.size(); current += ending; } prev = current; } int prevSize = prev.size(); while (N-- > 0) { cin >> current; int compareResult = compare(current, prev); if (compareResult > 0) // prev is greater { prevSize++; } result += prevSize - current.size(); } cout << result << endl; return 0; } |