#include <iostream> #include <iterator> #include <vector> #include <algorithm> #include <string> class Number { public: std::string value = "0"; public: Number(std::string init = "0") : value(init) {} void append(std::string sufix) { value += sufix; } friend std::ostream& operator<< (std::ostream &out, const Number &number) { return out << number.value; } friend std::istream& operator>> (std::istream &in, Number &number) { return in >> number.value; } std::pair<size_t, const std::string&> key() const { return {value.size(), value}; } size_t size() const { return value.size(); } void pop() { value.pop_back(); } friend bool operator< (const Number &lhs, const Number &rhs) { return lhs.key() < rhs.key(); } friend bool operator<= (const Number &lhs, const Number &rhs) { return lhs.key() <= rhs.key(); } friend bool operator>= (const Number &lhs, const Number &rhs) { return lhs.key() >= rhs.key(); } void operator++ () { auto it = std::prev(value.end()); while (*it == '9') { *it = '0'; /*if (it == value.begin()) { value = "1" + value; return; }*/ --it; } *it += 1; } }; void test() { using namespace std; int n; cin >> n; vector<Number> input(n); copy_n(istream_iterator<Number>(cin), n, input.begin()); long long answer = 0; long long zeros = 0; Number previous = {"0"}; for (const Number &prefix : input) { Number low = prefix; Number high = prefix; while (previous >= high) { answer += 1; low.append("0"); high.append("9"); } answer += zeros; constexpr int MAX_LENGTH = 20; if (low.size() > MAX_LENGTH) { //if (previous.size() != MAX_LENGTH) throw std::logic_error("Incorrect previous size"); low.pop(); high.pop(); zeros += 1; previous = {"0"}; } if (low <= previous) { low = previous; ++low; } previous = low; } cout << answer << endl; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); test(); 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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | #include <iostream> #include <iterator> #include <vector> #include <algorithm> #include <string> class Number { public: std::string value = "0"; public: Number(std::string init = "0") : value(init) {} void append(std::string sufix) { value += sufix; } friend std::ostream& operator<< (std::ostream &out, const Number &number) { return out << number.value; } friend std::istream& operator>> (std::istream &in, Number &number) { return in >> number.value; } std::pair<size_t, const std::string&> key() const { return {value.size(), value}; } size_t size() const { return value.size(); } void pop() { value.pop_back(); } friend bool operator< (const Number &lhs, const Number &rhs) { return lhs.key() < rhs.key(); } friend bool operator<= (const Number &lhs, const Number &rhs) { return lhs.key() <= rhs.key(); } friend bool operator>= (const Number &lhs, const Number &rhs) { return lhs.key() >= rhs.key(); } void operator++ () { auto it = std::prev(value.end()); while (*it == '9') { *it = '0'; /*if (it == value.begin()) { value = "1" + value; return; }*/ --it; } *it += 1; } }; void test() { using namespace std; int n; cin >> n; vector<Number> input(n); copy_n(istream_iterator<Number>(cin), n, input.begin()); long long answer = 0; long long zeros = 0; Number previous = {"0"}; for (const Number &prefix : input) { Number low = prefix; Number high = prefix; while (previous >= high) { answer += 1; low.append("0"); high.append("9"); } answer += zeros; constexpr int MAX_LENGTH = 20; if (low.size() > MAX_LENGTH) { //if (previous.size() != MAX_LENGTH) throw std::logic_error("Incorrect previous size"); low.pop(); high.pop(); zeros += 1; previous = {"0"}; } if (low <= previous) { low = previous; ++low; } previous = low; } cout << answer << endl; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); test(); return 0; } |