Submission #1477619

---

Source Code Expand

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;

ll calc(string s, bool eq) {
  ll dp[s.length()+1][2][2][2]; // 桁数、小さいことが確定しているか、4がついているか、9がついているか
  FOR(i,0,s.length()+1) FOR(j,0,2) FOR(k,0,2) FOR(l,0,2) {
    dp[i][j][k][l] = 0;
  }
  dp[0][0][0][0] = 1;
  FOR(i,0,s.length()) FOR(j,0,2) FOR(k,0,2) FOR(l,0,2) {
    int lim = j ? 9 : s[i] - '0';
    FOR(d,0,lim+1) {
      dp[i+1][j||d<lim][k||d==4][l||d==9] += dp[i][j][k][l];
    }
  }
  ll ret = 0;
  if(eq) {
    FOR(j,0,2) FOR(k,0,2) FOR(l,0,2) {
      if(k || l) ret += dp[s.length()][j][k][l];
    }
  } else {
    FOR(k,0,2) FOR(l,0,2) {
      if(k || l) ret += dp[s.length()][1][k][l];
    }
  }
  return ret;
}

int main()
{
  string A, B;
  cin >> A >> B;
  cout << calc(B,1) - calc(A,0) << endl;
  return 0;
}

Submission Info

Judge Result