Submission #3864750

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(int)(n);++i)
#define rep1(i, n) for(int i=1;i<=(int)(n);++i)
#define irep(i, a, n) for(int i=a;i<(int)(n);++i)
#define rrep(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define rrep1(i, n) for(int i=(int)(n);i>=1;--i)
#define allrep(V, v) for(auto&& V:v)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const int INF=1<<29;
const double EPS=1e-9;
using namespace std;


lint have_in_digit(int x){
  static lint ans_memo[100]={};
  if(x == 1) return 0;
  if(x == 2) return 2;
  if(ans_memo[x] != 0) return ans_memo[x];
  else{
    ans_memo[x]=have_in_digit(x-1)*8+(lint)pow(10,x-2)*2;
    return ans_memo[x];
  }
}

lint count_49(lint n){
  lint ans=0;
  int max_digits=to_string(n).length();
  for(int digits=max_digits; digits > 0; --digits){
    int digit_num=to_string(n)[max_digits-digits]-'0';
    if(digits == 0) continue;
    else if(digit_num <= 4){
      ans+=have_in_digit(digits)*digit_num;
    }else{
      ans+=have_in_digit(digits)*(digit_num-1)+(lint)pow(10,digits-1);
    }
    if(digit_num == 4 || digit_num == 9){
      ans+=1+n%(lint)pow(10,digits-1);
      break;
    }
  }
  return ans;
}

int main (void)
{
  lint a,b; cin>>a>>b;
  cout << count_49(b)-count_49(a-1) << endl;
  return 0;
}

Submission Info

Judge Result