CF Educational Codeforces Round 50 C. Classy Numbers

Let's call some positive integer classy if its decimal representation contains no more than $3$ non-zero digits. For example, numbers $4$ , $200000$ , $10203$ are classy and numbers $4231$ , $102306$ , $7277420000$ are not.

You are given a segment $[L; R]$ . Count the number of classy integers $x$ such that $L \leq x \leq R$ .

Each testcase contains several segments, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer $T$ ( $1 \leq T \leq 10^{4}$ ) — the number of segments in a testcase.

Each of the next $T$ lines contains two integers $L_{i}$ and $R_{i}$ ( $1 \leq L_{i} \leq R_{i} \leq 10^{18}$ ).

Output

Print $T$ lines — the $i$ -th line should contain the number of classy integers on a segment $[L_{i}; R_{i}]$ .

Example

input

Copy

41 10001024 102465536 65536999999 1000001

output

Copy

题目大意：找出N以内的不超过3个位置为0的数的个数。

考虑数位dp，但是考场上的写法太复杂了，其实只需要用不加任何限制的减去前面高位都是和N一样的方案数就可以了。

但是其实还是复杂了，这道题可以直接dfs出所有合法的数，然后二分答案，考虑这样的数大概不会超过1e6个。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;

LL dp[25][4][2], x, l, r;
int dig[25], cnt, q;

void indig(LL n) {
	while(n) {
		dig[++cnt] = n % 10;
		n /= 10;
	}
}

LL GetAns(LL n) {
	memset(dp, 0, sizeof(dp));
	if(n == 0) return 1;
	cnt = 0, indig(n);
	dp[cnt + 1][0][1] = 1;
	for(register int i = cnt + 1; i > 1; --i) {
		for(register int j = 0; j <= 2; ++j) {
				dp[i - 1][j][0] += dp[i][j][0];
				dp[i - 1][j + 1][0] += dp[i][j][0] * 9;
				if(dig[i - 1] > 1)
					dp[i - 1][j + 1][0] += dp[i][j][1] * (dig[i - 1] - 1);
				if(dig[i - 1] > 0) {
					dp[i - 1][j + 1][1] += dp[i][j][1];
					dp[i - 1][j][0] += dp[i][j][1];
				}
				else dp[i - 1][j][1] += dp[i][j][1];				
		}
		if(dig[i - 1] > 1) {
			dp[i - 1][3][0] += dp[i][3][1];
		} else dp[i - 1][3][1] += dp[i][3][1];
		dp[i - 1][3][0] += dp[i][3][0];
	}
	LL ans = 0;
	for(register int i = 0; i <= 1; ++i)
		ans += dp[1][0][i] + dp[1][1][i] + dp[1][2][i] + dp[1][3][i];
	return ans;
}

int main() {
	scanf("%d", &q);
	while(q--) {
		scanf("%I64d%I64d", &l, &r);
		//printf("%I64d\n%I64d\n", GetAns(r), GetAns(l - 1));
		printf("%I64d\n", GetAns(r) - GetAns(l - 1));
	}
	return 0;
}

Rockdu's Blog

题目大意：找出N以内的不超过3个位置为0的数的个数。

考虑数位dp，但是考场上的写法太复杂了，其实只需要用不加任何限制的减去前面高位都是和N一样的方案数就可以了。

但是其实还是复杂了，这道题可以直接dfs出所有合法的数，然后二分答案，考虑这样的数大概不会超过1e6个。

导航

最近发表

大佬们的友链