John and Brus believe that the digits 4 and 7 are lucky and all others are not. According to them, an almost lucky number is a number that contains at most one non-lucky digit in its decimal representation. Return the total number of almost lucky numbers between a and b, inclusive.

• ClassTheAlmostLuckyNumbersDivTwo
• Methodfind
• Parametersint , int
• Returnsint
• Method signatureint find(int a, int b)

• Time limit (s)2.000
• Memory limit (MB)64

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <ctime>

 #include <iostream>

 #include <algorithm>

 #include <set>

 #include <vector>

 #include <sstream>

 #include <typeinfo>

 #include <fstream>

 using namespace std;

 int dp[][] , dp2[][];

 int dig[] ;

 int vis[] ;

 void init ()

 {

     memset (dp ,  , sizeof(dp)) ;

     memset (dp2 ,  , sizeof(dp2) ) ;

     for (int i =  ; i <  ; i ++) dp[][i] =  ;

     for (int i =  ; i <=  ; i ++ ) {

         for (int j =  ; j <  ; j ++) {

           dp[i][j] += dp[i-][] + dp[i-][] ;

         }

     }

     int a , b , c =  , d =  ;

     for (int i =  ; i <=  ; i ++) for (int j =  ; j <  ; j ++) dp2[i][j] = dp[i][j] ;

     for (int i =  ; i <=  ; i ++) {

         a = dp[i][] , b = dp[i][] ;

         for (int j =  ; j <  ; j ++) {

             if (!(j ==  || j == )) {

                 dp2[i][] += dp[i-][j] ;

                 dp2[i][] += dp[i-][j] ;

             }

             else if (j == ) {

                 dp2[i][] += c ;

                 dp2[i][] += c ;

             }

             else if (j == ) {

                 dp2[i][] += d ;

                 dp2[i][] += d ;

             }

         }

    //    printf ("dp[%d][4]=%d , dp[%d][7]=%d\n" , i , dp[i][4] , i , dp[i][7]) ;

         c = dp2[i][] - a , d = dp2[i][] - b ;

     }

 }

 int cal (int x)

 {

     memset (dig ,  , sizeof(dig)) ;

     memset (vis ,  , sizeof(vis)) ;

     int ans =  ;

     int len =  ;

     int tmp = x ;

     int cnt =  ;

     while (x) {

         dig[len ++] = x %  ;

         x /=  ;

     }

     for (int i = len -  ; i >=  ; i --) {

         vis[i] = cnt ;

         if (dig[i] !=  && dig[i] != ) cnt ++ ;

     }

     //for (int i = 0 ; i < dig[1] ; i ++) ans += dp[1][i] ;

  //   ans += 10 ;

   //  printf ("hahaha") ;

   //  printf ("%d " , vis[0]) ;

    // for (int i = 1 ; i < len ; i ++) printf ("%d " , vis[i]) ; puts ("") ;

     for (int i =  ; i < len  ; i ++) {

        printf ("vis[%d]=%d:\n\n" , i , vis[i] ) ;

         if (vis[i] ==  ) {

             for (int j =  ; j < dig[i] ; j ++) ans += dp2[i][j] ;

         }

         else if (vis[i] == ) {

             for (int j =  ; j < dig[i] ; j ++) if (j ==  || j == ) ans += dp[i][j]  , printf ("dp[%d][%d]=%d\n" , i , j , dp[i][j]) ;

         }

         if (i == len - ) ans -= dp[i][] ;

     }

     printf ("ans = %d\n" , ans ) ;

     if (len == ) {

         ans += dp[][] ;

     }

     else {

         ans += dp[][] ;

         for (int i =  ; i < len -  ; i ++) {

             for (int j =  ; j <  ; j ++) ans += dp2[i][j] ;

         }

     }

     printf ("%d:ans = %d\n" , tmp , ans) ;

     printf ("-----------------------------------\n") ;

     return ans ;

 }

 class TheAlmostLuckyNumbersDivTwo {

     public:

     int find(int a, int b) {

         puts ("") ;

         if (a > b) swap(a,b) ;

         init () ;

         printf ("%d ~ %d\n" , a , b) ;

      //   printf ("%d - %d\n" , cal(b) , cal(a-1)) ;

         return cal(b+) - cal(a) ;

         //return 0 ;

     }

 };

 // CUT begin

 ifstream data("TheAlmostLuckyNumbersDivTwo.sample");

 string next_line() {

     string s;

     getline(data, s);

     return s;

 }

 template <typename T> void from_stream(T &t) {

     stringstream ss(next_line());

     ss >> t;

 }

 void from_stream(string &s) {

     s = next_line();

 }

 template <typename T>

 string to_string(T t) {

     stringstream s;

     s << t;

     return s.str();

 }

 string to_string(string t) {

     return "\"" + t + "\"";

 }

 bool do_test(int a, int b, int __expected) {

     time_t startClock = clock();

     TheAlmostLuckyNumbersDivTwo *instance = new TheAlmostLuckyNumbersDivTwo();

     int __result = instance->find(a, b);

     double elapsed = (double)(clock() - startClock) / CLOCKS_PER_SEC;

     delete instance;

     if (__result == __expected) {

         cout << "PASSED!" << " (" << elapsed << " seconds)" << endl;

         return true;

     }

     else {

         cout << "FAILED!" << " (" << elapsed << " seconds)" << endl;

         cout << "           Expected: " << to_string(__expected) << endl;

         cout << "           Received: " << to_string(__result) << endl;

         return false;

     }

 }

 int run_test(bool mainProcess, const set<int> &case_set, const string command) {

     int cases = , passed = ;

     while (true) {

         if (next_line().find("--") != )

             break;

         int a;

         from_stream(a);

         int b;

         from_stream(b);

         next_line();

         int __answer;

         from_stream(__answer);

         cases++;

         if (case_set.size() >  && case_set.find(cases - ) == case_set.end())

             continue;

         cout << "  Testcase #" << cases -  << " ... ";

         if ( do_test(a, b, __answer)) {

             passed++;

         }

     }

     if (mainProcess) {

         cout << endl << "Passed : " << passed << "/" << cases << " cases" << endl;

         int T = time(NULL) - ;

         double PT = T / 60.0, TT = 75.0;

         cout << "Time   : " << T /  << " minutes " << T %  << " secs" << endl;

         cout << "Score  : " <<  * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT)) << " points" << endl;

     }

     return ;

 }

 int main(int argc, char *argv[]) {

     cout.setf(ios::fixed, ios::floatfield);

     cout.precision();

     set<int> cases;

     bool mainProcess = true;

     for (int i = ; i < argc; ++i) {

         if ( string(argv[i]) == "-") {

             mainProcess = false;

         } else {

             cases.insert(atoi(argv[i]));

         }

     }

     if (mainProcess) {

         cout << "TheAlmostLuckyNumbersDivTwo (250 Points)" << endl << endl;

     }

     return run_test(mainProcess, cases, argv[]);

 }

 // CUT end