結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 1 ms
4,352 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 1 ms
4,356 KB
testcase_08 AC 1 ms
4,352 KB
testcase_09 AC 2 ms
4,352 KB
testcase_10 AC 1 ms
4,352 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 1 ms
4,352 KB
testcase_16 AC 1 ms
4,352 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 2 ms
4,352 KB
testcase_22 AC 2 ms
4,356 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 2 ms
4,352 KB
testcase_27 WA -
testcase_28 AC 1 ms
4,352 KB
testcase_29 AC 2 ms
4,352 KB
testcase_30 AC 1 ms
4,352 KB
testcase_31 AC 2 ms
4,348 KB
testcase_32 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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<10) 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