P83843

小Z的 k 紧凑数

难度 6 级 动态规划入门 数位
讨论 统计 1通过 2提交 50%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

小 Z 在草稿纸上列出了很多数,他觉得相邻两位数字差的绝对值不超过 k 的整数特别奇特,称其为 k 紧凑数。

现在小 Z 想知道 [l,r] 内有多少个 k 紧凑数,希望你帮帮他。

输入

第一行包含三个整数 l,r,k。

输出

第一行包含一个整数,表示 [l,r] 内 k 紧凑数的个数。

样例

样例 1
输入
1 13 1
输出
12

提示

对于 100% 的数据,1 ≤ l ≤ r ≤ 10^18,0 ≤ k ≤ 8。

来源

luogu

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交