結果

問題 No.319 happy b1rthday 2 me
ユーザー NekosyndromeNekosyndrome
提出日時 2015-12-12 00:51:21
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,866 bytes
コンパイル時間 1,240 ms
コンパイル使用メモリ 145,928 KB
実行使用メモリ 150,276 KB
最終ジャッジ日時 2023-10-13 11:32:09
合計ジャッジ時間 4,801 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 1 ms
4,352 KB
testcase_02 AC 1 ms
4,352 KB
testcase_03 AC 1 ms
4,352 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘LL solve(LL)’:
main.cpp:68:9: warning: ‘b’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  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