SRM510 Div1 Easy

250

全通り試して間に合う。

view plainprint?

1. lli bt(lli m, lli n, bool almost)  
2. {  
3.   if (m > n) return 0;  
4.    
5.   lli ret = 1;  
6.    
7.   ret += bt(m * 10LL + 4LL, n, almost);  
8.   ret += bt(m * 10LL + 7LL, n, almost);  
9.   
10.   if (!almost) {  
11.     if (m) ret += bt(m * 10LL, n, true);  
12.     for (lli i = 1; i <= 9; ++i) {  
13.       if (i == 4 || i == 7) continue;  
14.       ret += bt(m * 10LL + i, n, true);  
15.     }  
16.   }  
17.   
18.   return ret;  
19. }  
20.   
21. class TheAlmostLuckyNumbersDivOne {  
22. public:  
23.   long long find(long long a, long long b)  
24.   {  
25.     lli A = bt(0, a - 1, false);  
26.     lli B = bt(0, b, false);  
27.     return B - A;  
28.   }  
29. };  

lli bt(lli m, lli n, bool almost)
{
  if (m > n) return 0;
 
  lli ret = 1;
 
  ret += bt(m * 10LL + 4LL, n, almost);
  ret += bt(m * 10LL + 7LL, n, almost);

  if (!almost) {
    if (m) ret += bt(m * 10LL, n, true);
    for (lli i = 1; i <= 9; ++i) {
      if (i == 4 || i == 7) continue;
      ret += bt(m * 10LL + i, n, true);
    }
  }

  return ret;
}

class TheAlmostLuckyNumbersDivOne {
public:
  long long find(long long a, long long b)
  {
    lli A = bt(0, a - 1, false);
    lli B = bt(0, b, false);
    return B - A;
  }
};