← 返回题目列表

Codeforces · 113/E

E. 睡觉

中文机器翻译题面 查看原题

有一天,Vasya 躺在床上看着电子钟,希望能更快入睡。

Vasya生活在一个陌生的国家,那里一天有h小时,每小时有m分钟。时钟以十进制数字系统显示时间,格式为 H:M,其中字符串 H 的固定长度始终等于数字 h - 1 的十进制表示形式中的位数。为此,如有必要,会添加前导零。字符串 M 具有类似的格式,其长度始终等于数字 m - 1 的十进制表示形式的位数。例如,如果 h = 17,m = 1000,则等于 13 小时 75 分钟的时间将显示为“13:075”。

Vasya 一直在看时钟,从 h1 小时 m1 分钟到 h2 小时 m2 分钟(含),然后他睡着了。现在他要求你数数他看到时钟上至少 k 个数字同时变化的时刻有多少次。

例如,切换 04:19 → 04:20 时,两位数字会发生变化。当切换 23:59 → 00:00 时,四位数字会发生变化。

考虑一下 Vasya 看钟的时间严格来说还不到一天。请注意,Vasya 在入睡前最后一次看到时钟的时间是“h2:m2”。也就是说,Vasya 没有看到“h2:m2”切换到下一个值的时刻。

输入

输入文件的第一行包含三个空格分隔的整数 h、m 和 k (2 ≤ h、m ≤ 109、1 ≤ k ≤ 20)。第二行包含空格分隔的整数 h1, m1 (0 ≤ h1 < h, 0 ≤ m1 < m)。第三行包含空格分隔的整数 h2, m2 (0 ≤ h2 < h, 0 ≤ m2 < m)。

输出

打印单个数字 — Vasya 看到同时更改至少 k 个数字的时刻的次数。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin 流(您也可以使用 %I64d 指定符)。

示例

输入 #1

5 5 2
4 4
2 1

输出 #1

3

输入 #2

24 60 1
0 0
23 59

输出 #2

1439

输入 #3

24 60 3
23 59
23 59

输出 #3

0

注意

在第一个示例中,Vasya 将看到以下时刻: 4:4 $$\text{图像看起来很模糊,但它似乎包含由于模糊而无法清晰辨别的数学表达式或符号。如果有预期的文本或特定公式,则需要使用更清晰的图像重新渲染。}$$ 0:0 → 0:1 → 0:2 → 0:3 → 0:4 $$\text{图像看起来很模糊,但它似乎包含由于模糊而无法清晰辨别的数学表达式或符号。如果有预期的文本或特定公式,则需要使用更清晰的图像重新渲染。}$$ 1:0 → 1:1 → 1:2 → 1:3 → 1:4 $$\text{图像看起来很模糊,但它似乎包含由于模糊而无法清晰辨别的数学表达式或符号。如果有预期的文本或特定公式,则需要使用更清晰的图像重新渲染。}$$ 2:0 → 2:1 → 2:2 → 2:3 → 2:4。双箭头($$\text{图像看起来很模糊,但它似乎包含由于模糊而无法清晰辨别的数学表达式或符号。如果有预期的文本或特定公式,则需要使用更清晰的图像重新渲染。}$$)标记所寻找的时间时刻(在本例中 - 当 Vasya 看到两个数字同时变化时)。

在第二个示例中,k = 1。任何切换时间都可以接受,因为在时钟切换期间至少有一位数字发生变化。总切换次数等于 24·60 = 1440,但 Vasya 还没有看到其中之一——23:59 的切换 $$\text{图像看起来很模糊,但它似乎包含一个数学表达式或符号,由于模糊而无法清晰辨别。如果有预期的文本或特定公式,则需要使用更清晰的图像重新渲染。}$$ 00:00。

在第三个例子中,Vasya 在开始看时钟后立即睡着了,所以他没有看到任何变化。