#64950 (C++11（廃止可能性あり）) No.319 happy b1rthday 2 me

• 問題: No.319 happy b1rthday 2 me
• ユーザー: Nekosyndrome
• 提出日時: 2015-12-12 01:00:43
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 1,892 bytes
• コンパイル時間: 1,288 ms
• コンパイル使用メモリ: 159,216 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-15 08:31:45
• 合計ジャッジ時間: 2,210 ms
• ジャッジサーバーID （参考情報）: judge4 / judge6

ファイルパターン	結果
sample	AC * 4
other	AC * 29

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define FORD(x,y,z) for(int x=y;x>=z;x--)
#define MSET(x,y) memset(x,y,sizeof(x))
#define FOR(x,y) for(__typeof(y.begin()) x=y.begin();x!=y.end();x++)
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SZ size()
#define M 
void RI(){}
template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d",&head);
    RI(tail...);
}
using namespace std;
typedef long long LL;
LL n,m,pw[30];
LL dp[32][2][3],cnt[32][2][3];
char buf[100];
LL solve2(LL x)
{
    if(x<10) return 0;
    
    sprintf(buf, "%lld", x);
    int len = strlen(buf);
    MSET(dp,0);
    MSET(cnt,0);
    REP(i,0,len-1) buf[i]-='0';
    REP(i,0,buf[0]) cnt[0][i==buf[0]][i==1]++;
    int ni,nj,nk;
    REP(i,0,len-2)REP(j,0,1)REP(k,0,2)if(cnt[i][j][k]!=0)
    {
        REP(num,0,9)
        {
            if(j==1 && num>buf[i+1]) continue;
            ni = i+1;
            nj = (j==1 && num==buf[i+1]);
            
            nk = 0;
            if(num==1) nk=1;
            if(k==1 && num==2) nk=2;
            //cnt
            cnt[ni][nj][nk] += cnt[i][j][k];
            //dp
            if(dp[ni][nj][nk]==-1) dp[ni][nj][nk]=0;
            dp[ni][nj][nk] += dp[i][j][k];
            if(nk==2) dp[ni][nj][nk]+=cnt[i][j][k];
        }
    }
    LL re=0;
    REP(j,0,1)REP(k,0,2) re+=dp[len-1][j][k];
    return re;
}
LL solve(LL x)
{
    LL re = solve2(x);
    LL a,b;
    LL l,r,mid;
    REP(dig,1,18)
    {
        a=1, b=2;
        if(dig>1)
        {
            a += pw[dig-1]*2;
            b += pw[dig-1]*2;
        }
        if(b>x) break;
        if(dig<=2) re++;
        else
        {
            l=0, r=pw[dig-2]-1;
            while(l<r-1)
            {
                mid = (l+r)/2;
                if(b+mid*10 <= x) l=mid;
                else r=mid-1;
            }
            if(l==r-1 && b+r*10<=x) l++;
            re += l+1;
        }
    }
    return re;
}
int head(LL x)
{
    while(x>10) x/=10;
    return (int)x;
}
int main()
{
    pw[0]=1;
    REP(i,1,29) pw[i]=pw[i-1]*10;
    while(~scanf("%lld %lld",&n,&m))
    {
        LL ans = solve(m)-solve(n-1);
        int hn = head(n);
        int tn = (n-1)%10;
        if(tn==1 && hn==2) ans--;
        printf("%lld\n",ans);
    }
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX