#P3539. [Usaco2014 Open]Odometer

    ID: 2749 传统题 1000ms 512MiB 尝试: 52 已通过: 28 难度: 6 上传者: 标签>难度分类提高动态规划数位 DP组合数学容斥原理前导零状态上界限制状态记忆化搜索CF2000SilverBy

[Usaco2014 Open]Odometer

[USACO14OPEN] Odometer S

题目描述

奶牛们正在公路上旅行。里程表从 XX 开始,依次显示每个整数里程,最后显示 YY。每显示一个有趣的数,奶牛们就叫一声,起点和终点都算在内。

去掉一个数的十进制前导零后,若存在一种数字,其出现次数至少占总位数的一半,则这个数有趣。例如,32233223 和 110110 有趣,9779197791 和 123123 则无趣。一个数满足条件时只叫一声。

求奶牛们在旅途中一共叫了多少声。

输入格式

一行两个整数 X,YX,Y。

输出格式

一行一个整数,表示闭区间 [X,Y][X,Y] 内有趣的数的个数。

样例 #1

110 133
14

这些数是 110110 至 119119,以及 121,122,131,133121,122,131,133。

数据范围

100≤X≤Y≤1018100\le X\le Y\le10^{18}。