結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0