• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/526-U/2C.cpp version [7d7d14d6f38066ca]

                                                                                        >     1  #include <iostream>
                                                                                        >     2  #include <sstream>
                                                                                        >     3  #include <iomanip>
                                                                                        >     4  #include <vector>
                                                                                        >     5  #include <string>
                                                                                        >     6  #include <map>
                                                                                        >     7  #include <set>
                                                                                        >     8  #include <algorithm>
                                                                                        >     9  #include <numeric>
                                                                                        >    10  #include <iterator>
                                                                                        >    11  #include <functional>
                                                                                        >    12  #include <complex>
                                                                                        >    13  #include <queue>
                                                                                        >    14  #include <stack>
                                                                                        >    15  #include <cmath>
                                                                                        >    16  #include <cassert>
                                                                                        >    17  #include <cstring>
                                                                                        >    18  #ifdef __GNUC__
                                                                                        >    19  #include <ext/hash_map>
                                                                                        >    20  #define unordered_map __gnu_cxx::hash_map
                                                                                        >    21  #else
                                                                                        >    22  #include <unordered_map>
                                                                                        >    23  #endif
                                                                                        >    24  using namespace std;
                                                                                        >    25  typedef long long LL;
                                                                                        >    26  typedef complex<double> CMP;
                                                                                        >    27  
                                                                                        >    28  class SumOfLuckiness { public:
                                                                                        >    29          long long theSum(int A, int B)
                                                                                        >    30          {
                                                                                        >    31                  return theSum(B) - theSum(A-1);
                                                                                        >    32          }
                                                                                        >    33  
                                                                                        >    34          LL theSum(LL X)
                                                                                        >    35          {
                                                                                        >    36                  string S; {stringstream ss; ss<<X; ss>>S;}
                                                                                        >    37                  memo.clear();
                                                                                        >    38                  return rec(S, 0, 0);
                                                                                        >    39          }
                                                                                        >    40  
                                                                                        >    41          LL rec(const string& S, int i, int dif)
                                                                                        >    42          {
                                                                                        >    43                  if( i == S.size() )
                                                                                        >    44                          return abs(dif);
                                                                                        >    45  
                                                                                        >    46                  LL total = rec(S, i+1, dif+(S[i]=='4')-(S[i]=='7'));
                                                                                        >    47                  for(char c='0'; c<S[i]; ++c)
                                                                                        >    48                          total += count_all(S.size() - (i+1), dif+(c=='4')-(c=='7
                                                                                        >    49                  return total;
                                                                                        >    50          }
                                                                                        >    51  
                                                                                        >    52          map<pair<int,int>, LL> memo;
                                                                                        >    53          LL count_all(int n, int dif)
                                                                                        >    54          {
                                                                                        >    55                  if( n == 0 )
                                                                                        >    56                          return abs(dif);
                                                                                        >    57  
                                                                                        >    58                  const pair<int,int> key(n, dif);
                                                                                        >    59                  if( memo.count(key) )
                                                                                        >    60                          return memo[key];
                                                                                        >    61  
                                                                                        >    62                  LL total = 0;
                                                                                        >    63                  for(char c='0'; c<='9'; ++c)
                                                                                        >    64                          total += count_all(n-1, dif+(c=='4')-(c=='7'));
                                                                                        >    65                  return memo[key] = total;
                                                                                        >    66          }
                                                                                        >    67  };
                                                                                        >    68  
                                                                                        >    69  // BEGIN CUT HERE
                                                                                        >    70  #include <ctime>
                                                                                        >    71  double start_time; string timer()
                                                                                        >    72   { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000)
                                                                                        >    73  template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
                                                                                        >    74   { os << "{ ";
                                                                                        >    75     for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
                                                                                        >    76     os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return 
                                                                                        >    77  void verify_case(const long long& Expected, const long long& Received) {
                                                                                        >    78   bool ok = (Expected == Received);
                                                                                        >    79   if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer()
                                                                                        >    80   cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' 
                                                                                        >    81  #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(
                                                                                        >    82  #define END      verify_case(_, SumOfLuckiness().theSum(A, B));}
                                                                                        >    83  int main(){
                                                                                        >    84  
                                                                                        >    85  CASE(0)
                                                                                        >    86          int A = 1;
                                                                                        >    87          int B = 10;
                                                                                        >    88          long long _ = 2LL;
                                                                                        >    89  END
                                                                                        >    90  CASE(1)
                                                                                        >    91          int A = 40;
                                                                                        >    92          int B = 47;
                                                                                        >    93          long long _ = 8LL;
                                                                                        >    94  END
                                                                                        >    95  CASE(2)
                                                                                        >    96          int A = 58;
                                                                                        >    97          int B = 526;
                                                                                        >    98          long long _ = 231LL;
                                                                                        >    99  END
                                                                                        >   100  CASE(3)
                                                                                        >   101          int A = 4444;
                                                                                        >   102          int B = 7777;
                                                                                        >   103          long long _ = 2338LL;
                                                                                        >   104  END
                                                                                        >   105  CASE(4)
                                                                                        >   106          int A = 585858585;
                                                                                        >   107          int B = 858585858;
                                                                                        >   108          long long _ = 287481025LL;
                                                                                        >   109  END
                                                                                        >   110  CASE(5)
                                                                                        >   111          int A = 1;
                                                                                        >   112          int B = 1;
                                                                                        >   113          long long _ = 0LL;
                                                                                        >   114  END
                                                                                        >   115  CASE(6)
                                                                                        >   116          int A = 1;
                                                                                        >   117          int B = 2000000000;
                                                                                        >   118          long long _ = -1LL;
                                                                                        >   119  END
                                                                                        >   120  
                                                                                        >   121  }
                                                                                        >   122  // END CUT HERE