結果

問題 No.319 happy b1rthday 2 me
ユーザー NekosyndromeNekosyndrome
提出日時 2015-12-12 00:51:21
言語 C++11
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,866 bytes
コンパイル時間 1,222 ms
コンパイル使用メモリ 161,080 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-09-15 08:31:05
合計ジャッジ時間 4,671 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘LL solve(LL)’:
main.cpp:68:16: warning: ‘b’ may be used uninitialized [-Wmaybe-uninitialized]
   68 |         while(b<=2)
      |               ~^~~

ソースコード

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)
{
	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)
{
	if(x==0) return 0;
	LL re = solve2(x);

	LL a,b;
	LL l,r,mid;
	while(b<=2)
	{
		re++;

		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++;

				//printf("dig=%d a=%lld b=%lld lim=%lld\n",dig,a,b,b+l*10);

				re += l+1;
			}
		}
	}
	return re;
}
int main()
{
	pw[0]=1;
	REP(i,1,29) pw[i]=pw[i-1]*10;

	while(~scanf("%lld %lld",&n,&m))
	{
		printf("%lld\n", solve(m)-solve(n-1));
	}
	return 0;
}
0