naoya_t@topcoder

SRM403 Div1 Easy: TheLuckyNumbers

過去問, 練習 | 18:04 |

10^9のループではTLEになるであろう数え上げ系。すこし手間取った(141.71points)。

こういうので200点以上とれるようになりたい。

int c(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1;
  if (r > n-r) r = n-r;
  return n * c(n-1,r-1) / r;
}
int expt(int x,int n){
  int v=1; rep(i,n) v*=x; return v;
}

class TheLuckyNumbers {
public:
  int s_(int k,int n){
    int cnt=0;
    rep(i,1<<k){
      int u=0,m=1<<(k-1);
      rep(j,k){u*=10; u+=(i&m)?7:4; m>>=1;}
      if (n>=u) cnt++; else break;
    }
    return cnt;
  }
  int s(int k){
    return expt(2,k);
  }
  int lns(int n){
    if (n<4) return 0;
    if (n<7) return 1;
    if (n<44) return 2;
    if (n>777777777) n=777777777;

    int k=0,t=0,o=1;
    int n_=n;
    while(n_>0){ t=n_; n_/=10; o*=10; k++; }
    o = (o-1)/9;
    int o4=o*4, o7=o*7;
    int kt=k;
    int cnt=0;
    if (n<o7) {
      kt--;
      if (n>=o4) {
        cnt += s_(k,n);
      }
    }
    rep(i,kt) cnt+=s(i+1);
    return cnt;
  }
  int count(int a, int b) {
    return lns(b)-lns(a-1);
  }
};