daily pastebin goal
65%
SHARE
TWEET

Untitled

a guest Dec 7th, 2017 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <string>
  5. #include <utility>
  6. #include <functional>
  7. #include <algorithm>
  8. #include <cassert>
  9.  
  10. using namespace std;
  11.  
  12. struct long_num
  13. {
  14.     static constexpr int BASE = 10;
  15.  
  16.     vector<int> digits;
  17.  
  18.     explicit long_num(int x = 0) //privychka pisat' explicit
  19.         : digits(1, x)
  20.     {
  21.         normalize();
  22.     }
  23.  
  24.     long_num operator + (long_num const& other) const
  25.     {
  26.         long_num result;
  27.         result.digits.assign(max(digits.size(), other.digits.size()), 0);
  28.         for (size_t i = 0; i < digits.size(); ++i)
  29.             result.digits[i] += digits[i];
  30.         for (size_t i = 0; i < other.digits.size(); ++i)
  31.             result.digits[i] += other.digits[i];
  32.  
  33.         result.normalize();
  34.         return result;
  35.     }
  36.  
  37.     long_num operator - (long_num const& other) const
  38.     {
  39.         long_num result;
  40.         result.digits.assign(max(digits.size(), other.digits.size()), 0);
  41.         for (size_t i = 0; i < digits.size(); ++i)
  42.             result.digits[i] += digits[i];
  43.         for (size_t i = 0; i < other.digits.size(); ++i)
  44.             result.digits[i] -= other.digits[i];
  45.  
  46.         result.normalize();
  47.         return result;
  48.     }
  49.  
  50.     long_num operator * (long_num const& other) const
  51.     {
  52.         long_num result;
  53.         result.digits.assign(digits.size() + other.digits.size(), 0);
  54.         for (size_t i = 0; i < digits.size(); ++i)
  55.             for (size_t j = 0; j < other.digits.size(); ++j)
  56.                 result.digits[i + j] += digits[i] * other.digits[j]; //TODO: check perepolneniya; budet rabota' do overdofiga dliny, tk BASE == 10
  57.  
  58.         result.normalize();
  59.         return result;
  60.     }
  61.  
  62.     void normalize()
  63.     {
  64.         for (size_t i = 0; i < digits.size(); ++i)
  65.             if (!(0 <= digits[i] && digits[i] < BASE)) //kazhetsya, delit' dol'she chem ifat'
  66.             {
  67.                 auto p = digits[i] / BASE, q = digits[i] % BASE; //digits[i] == p * BASE + q
  68.                 if (q < 0)
  69.                     p -= 1, q += BASE; //p * BASE + q == (p - 1) * BASE + (q + BASE)
  70.  
  71.                 assert(p != 0); //perenos est' vsegda
  72.                
  73.                 if (i + 1 == digits.size()) //mesto est'? a esli naidu?
  74.                 {
  75.                     if (p == -1 && q == BASE - 1)
  76.                         break;
  77.  
  78.                     digits.push_back(0);
  79.                 }
  80.  
  81.                 digits[i + 1] += p;
  82.                 digits[i] = q;
  83.             }
  84.  
  85.         while (digits.size() > 1 && digits.back() == 0) //zapis' dlya 0 budet { 0 }
  86.             digits.pop_back();
  87.     }
  88.  
  89.     bool is_negative() const
  90.     {
  91.         return digits.back() < 0;
  92.     }
  93. };
  94.  
  95. auto read_long_num = [] (auto & stream) {
  96.     string s;
  97.     stream >> s;
  98.  
  99.     assert(!s.empty()); //shito eto bylo?
  100.  
  101.     bool negative = false;
  102.     if (s[0] == '-')
  103.     {
  104.         negative = true;
  105.         s.erase(s.begin());
  106.     }
  107.  
  108.     long_num result;
  109.     result.digits.assign(s.length(), 0);
  110.     for (size_t i = 0; i < s.length(); ++i)
  111.         result.digits[s.length() - i - 1] = s[i] - '0';
  112.    
  113.     static_assert(long_num::BASE == 10, "zdes' dolzhen byt' perevod");
  114.  
  115.     result.normalize();
  116.  
  117.     if (negative)  //a chto eshe takoe unarnyj minus?
  118.         result = long_num(0) - result;
  119.  
  120.     return result;
  121. };
  122.  
  123. auto write_long_num = [] (auto & stream, long_num value) { //kopiruem special'no
  124.     static_assert(long_num::BASE == 10, "zdes' dolzhen byt' perevod");
  125.  
  126.     if (value.is_negative())
  127.     {
  128.         stream << '-';
  129.         value = long_num(0) - value;
  130.     }
  131.  
  132.     for (size_t i = 0; i < value.digits.size(); ++i)
  133.         stream << char('0' + value.digits[value.digits.size() - i - 1]);
  134. };
  135.  
  136. int main()
  137. {
  138.     ifstream cin("input.txt");
  139.     ofstream cout("output.txt");
  140.  
  141.     long_num a = read_long_num(cin);
  142.     long_num b = read_long_num(cin);
  143.     write_long_num(cout, a - b);
  144. }
RAW Paste Data
Top