fork(1) download
copy 
  1. #include<stdio.h>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. const int base = 1000000000;
  8. const int base_digits = 9;
  9.  
  10. struct bigint {
  11.     vector<int> a;
  12.     int sign;
  13.  
  14.     bigint() :
  15.         sign(1) {
  16.     }
  17.  
  18.     bigint(long long v) {
  19.         *this = v;
  20.     }
  21.  
  22.     bigint(const string &s) {
  23.         read(s);
  24.     }
  25.  
  26.     void operator=(const bigint &v) {
  27.         sign = v.sign;
  28.         a = v.a;
  29.     }
  30.  
  31.     void operator=(long long v) {
  32.         sign = 1;
  33.         if (v < 0)
  34.             sign = -1, v = -v;
  35.         for (; v > 0; v = v / base)
  36.             a.push_back(v % base);
  37.     }
  38.  
  39.     bigint operator+(const bigint &v) const {
  40.         if (sign == v.sign) {
  41.             bigint res = v;
  42.  
  43.             for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
  44.                 if (i == (int) res.a.size())
  45.                     res.a.push_back(0);
  46.                 res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  47.                 carry = res.a[i] >= base;
  48.                 if (carry)
  49.                     res.a[i] -= base;
  50.             }
  51.             return res;
  52.         }
  53.         return *this - (-v);
  54.     }
  55.  
  56.     bigint operator-(const bigint &v) const {
  57.         if (sign == v.sign) {
  58.             if (abs() >= v.abs()) {
  59.                 bigint res = *this;
  60.                 for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  61.                     res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  62.                     carry = res.a[i] < 0;
  63.                     if (carry)
  64.                         res.a[i] += base;
  65.                 }
  66.                 res.trim();
  67.                 return res;
  68.             }
  69.             return -(v - *this);
  70.         }
  71.         return *this + (-v);
  72.     }
  73.  
  74.     void operator*=(int v) {
  75.         if (v < 0)
  76.             sign = -sign, v = -v;
  77.         for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  78.             if (i == (int) a.size())
  79.                 a.push_back(0);
  80.             long long cur = a[i] * (long long) v + carry;
  81.             carry = (int) (cur / base);
  82.             a[i] = (int) (cur % base);
  83.             //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  84.         }
  85.         trim();
  86.     }
  87.  
  88.     bigint operator*(int v) const {
  89.         bigint res = *this;
  90.         res *= v;
  91.         return res;
  92.     }
  93.  
  94.     friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  95.         int norm = base / (b1.a.back() + 1);
  96.         bigint a = a1.abs() * norm;
  97.         bigint b = b1.abs() * norm;
  98.         bigint q, r;
  99.         q.a.resize(a.a.size());
  100.  
  101.         for (int i = a.a.size() - 1; i >= 0; i--) {
  102.             r *= base;
  103.             r += a.a[i];
  104.             int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  105.             int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  106.             int d = ((long long) base * s1 + s2) / b.a.back();
  107.             r -= b * d;
  108.             while (r < 0)
  109.                 r += b, --d;
  110.             q.a[i] = d;
  111.         }
  112.  
  113.         q.sign = a1.sign * b1.sign;
  114.         r.sign = a1.sign;
  115.         q.trim();
  116.         r.trim();
  117.         return make_pair(q, r / norm);
  118.     }
  119.  
  120.     bigint operator/(const bigint &v) const {
  121.         return divmod(*this, v).first;
  122.     }
  123.  
  124.     bigint operator%(const bigint &v) const {
  125.         return divmod(*this, v).second;
  126.     }
  127.  
  128.     void operator/=(int v) {
  129.         if (v < 0)
  130.             sign = -sign, v = -v;
  131.         for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  132.             long long cur = a[i] + rem * (long long) base;
  133.             a[i] = (int) (cur / v);
  134.             rem = (int) (cur % v);
  135.         }
  136.         trim();
  137.     }
  138.  
  139.     bigint operator/(int v) const {
  140.         bigint res = *this;
  141.         res /= v;
  142.         return res;
  143.     }
  144.  
  145.     int operator%(int v) const {
  146.         if (v < 0)
  147.             v = -v;
  148.         int m = 0;
  149.         for (int i = a.size() - 1; i >= 0; --i)
  150.             m = (a[i] + m * (long long) base) % v;
  151.         return m * sign;
  152.     }
  153.  
  154.     void operator+=(const bigint &v) {
  155.         *this = *this + v;
  156.     }
  157.     void operator-=(const bigint &v) {
  158.         *this = *this - v;
  159.     }
  160.     void operator*=(const bigint &v) {
  161.         *this = *this * v;
  162.     }
  163.     void operator/=(const bigint &v) {
  164.         *this = *this / v;
  165.     }
  166.  
  167.     bool operator<(const bigint &v) const {
  168.         if (sign != v.sign)
  169.             return sign < v.sign;
  170.         if (a.size() != v.a.size())
  171.             return a.size() * sign < v.a.size() * v.sign;
  172.         for (int i = a.size() - 1; i >= 0; i--)
  173.             if (a[i] != v.a[i])
  174.                 return a[i] * sign < v.a[i] * sign;
  175.         return false;
  176.     }
  177.  
  178.     bool operator>(const bigint &v) const {
  179.         return v < *this;
  180.     }
  181.     bool operator<=(const bigint &v) const {
  182.         return !(v < *this);
  183.     }
  184.     bool operator>=(const bigint &v) const {
  185.         return !(*this < v);
  186.     }
  187.     bool operator==(const bigint &v) const {
  188.         return !(*this < v) && !(v < *this);
  189.     }
  190.     bool operator!=(const bigint &v) const {
  191.         return *this < v || v < *this;
  192.     }
  193.  
  194.     void trim() {
  195.         while (!a.empty() && !a.back())
  196.             a.pop_back();
  197.         if (a.empty())
  198.             sign = 1;
  199.     }
  200.  
  201.     bool isZero() const {
  202.         return a.empty() || (a.size() == 1 && !a[0]);
  203.     }
  204.  
  205.     bigint operator-() const {
  206.         bigint res = *this;
  207.         res.sign = -sign;
  208.         return res;
  209.     }
  210.  
  211.     bigint abs() const {
  212.         bigint res = *this;
  213.         res.sign *= res.sign;
  214.         return res;
  215.     }
  216.  
  217.     long long longValue() const {
  218.         long long res = 0;
  219.         for (int i = a.size() - 1; i >= 0; i--)
  220.             res = res * base + a[i];
  221.         return res * sign;
  222.     }
  223.  
  224.     friend bigint gcd(const bigint &a, const bigint &b) {
  225.         return b.isZero() ? a : gcd(b, a % b);
  226.     }
  227.     friend bigint lcm(const bigint &a, const bigint &b) {
  228.         return a / gcd(a, b) * b;
  229.     }
  230.  
  231.     void read(const string &s) {
  232.         sign = 1;
  233.         a.clear();
  234.         int pos = 0;
  235.         while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  236.             if (s[pos] == '-')
  237.                 sign = -sign;
  238.             ++pos;
  239.         }
  240.         for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  241.             int x = 0;
  242.             for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  243.                 x = x * 10 + s[j] - '0';
  244.             a.push_back(x);
  245.         }
  246.         trim();
  247.     }
  248.  
  249.     friend istream& operator>>(istream &stream, bigint &v) {
  250.         string s;
  251.         stream >> s;
  252.         v.read(s);
  253.         return stream;
  254.     }
  255.  
  256.     friend ostream& operator<<(ostream &stream, const bigint &v) {
  257.         if (v.sign == -1)
  258.             stream << '-';
  259.         stream << (v.a.empty() ? 0 : v.a.back());
  260.         for (int i = (int) v.a.size() - 2; i >= 0; --i)
  261.             stream << setw(base_digits) << setfill('0') << v.a[i];
  262.         return stream;
  263.     }
  264.  
  265.     static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  266.         vector<long long> p(max(old_digits, new_digits) + 1);
  267.         p[0] = 1;
  268.         for (int i = 1; i < (int) p.size(); i++)
  269.             p[i] = p[i - 1] * 10;
  270.         vector<int> res;
  271.         long long cur = 0;
  272.         int cur_digits = 0;
  273.         for (int i = 0; i < (int) a.size(); i++) {
  274.             cur += a[i] * p[cur_digits];
  275.             cur_digits += old_digits;
  276.             while (cur_digits >= new_digits) {
  277.                 res.push_back(int(cur % p[new_digits]));
  278.                 cur /= p[new_digits];
  279.                 cur_digits -= new_digits;
  280.             }
  281.         }
  282.         res.push_back((int) cur);
  283.         while (!res.empty() && !res.back())
  284.             res.pop_back();
  285.         return res;
  286.     }
  287.  
  288.     typedef vector<long long> vll;
  289.  
  290.     static vll karatsubaMultiply(const vll &a, const vll &b) {
  291.         int n = a.size();
  292.         vll res(n + n);
  293.         if (n <= 32) {
  294.             for (int i = 0; i < n; i++)
  295.                 for (int j = 0; j < n; j++)
  296.                     res[i + j] += a[i] * b[j];
  297.             return res;
  298.         }
  299.  
  300.         int k = n >> 1;
  301.         vll a1(a.begin(), a.begin() + k);
  302.         vll a2(a.begin() + k, a.end());
  303.         vll b1(b.begin(), b.begin() + k);
  304.         vll b2(b.begin() + k, b.end());
  305.  
  306.         vll a1b1 = karatsubaMultiply(a1, b1);
  307.         vll a2b2 = karatsubaMultiply(a2, b2);
  308.  
  309.         for (int i = 0; i < k; i++)
  310.             a2[i] += a1[i];
  311.         for (int i = 0; i < k; i++)
  312.             b2[i] += b1[i];
  313.  
  314.         vll r = karatsubaMultiply(a2, b2);
  315.         for (int i = 0; i < (int) a1b1.size(); i++)
  316.             r[i] -= a1b1[i];
  317.         for (int i = 0; i < (int) a2b2.size(); i++)
  318.             r[i] -= a2b2[i];
  319.  
  320.         for (int i = 0; i < (int) r.size(); i++)
  321.             res[i + k] += r[i];
  322.         for (int i = 0; i < (int) a1b1.size(); i++)
  323.             res[i] += a1b1[i];
  324.         for (int i = 0; i < (int) a2b2.size(); i++)
  325.             res[i + n] += a2b2[i];
  326.         return res;
  327.     }
  328.  
  329.     bigint operator*(const bigint &v) const {
  330.         vector<int> a6 = convert_base(this->a, base_digits, 6);
  331.         vector<int> b6 = convert_base(v.a, base_digits, 6);
  332.         vll a(a6.begin(), a6.end());
  333.         vll b(b6.begin(), b6.end());
  334.         while (a.size() < b.size())
  335.             a.push_back(0);
  336.         while (b.size() < a.size())
  337.             b.push_back(0);
  338.         while (a.size() & (a.size() - 1))
  339.             a.push_back(0), b.push_back(0);
  340.         vll c = karatsubaMultiply(a, b);
  341.         bigint res;
  342.         res.sign = sign * v.sign;
  343.         for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  344.             long long cur = c[i] + carry;
  345.             res.a.push_back((int) (cur % 1000000));
  346.             carry = (int) (cur / 1000000);
  347.         }
  348.         res.a = convert_base(res.a, 6, base_digits);
  349.         res.trim();
  350.         return res;
  351.     }
  352. };
  353.  
  354. int main() {
  355. 	int arr[10]={6,2,5,5,4,5,6,3,7,6};
  356. 	int T;
  357. 	cin>>T;
  358. 	int x;
  359. 	while(T)
  360. 	{	bigint number,sum=0;
  361. 	cin>>number;
  362. 	while(number>0)
  363. 	{
  364. 		x=number%10;
  365. 		sum=sum+arr[x];
  366. 		number=number/10;
  367. 	}
  368. 	cout<<sum<<" leds"<<endl;
  369. 	T--;
  370. 	}
  371. 	return 0;
  372. }
Success #stdin #stdout 0s 3484KB
comments ()
stdin
copy 
1
20
stdout
copy 
11 leds
https://ideone.com/RW5deD
5
5 50 50 70 80 100
7 100 95 90 80 70 60 50
3 70 90 80
3 70 90 81
9 100 99 98 97 96 95 94 93 91
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!