← 返回题目列表

Codeforces · 820/C

C. B先生和无聊的游戏

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

有时,B 先生晚上有空闲时间,但他不知道该做什么。幸运的是,B先生发现了一个新游戏,玩家可以在其中与外星人对战。

本游戏中所有角色均为小写英文字母。有两个玩家:B 先生和他的竞争对手。

最初,玩家有一个字符串 s,其中按字母顺序排列第一个 a 英文字母(例如,如果 a = 5,则 s 等于“abcde”)。

玩家轮流将字母附加到字符串 s 上。 B先生先行动。

B 先生必须​​在他的每一步棋中准确地附加 b 个字母。他可以任意选择这些字母。他的对手在每一步棋中都精确地添加了一个字母。

B先生很快就明白了,他的对手只是一台使用简单算法的计算机。计算机每轮都会考虑长度为 a 的字符串 s 的后缀,并生成长度为 a 的字符串 t,使得字符串 t 中的所有字母都是不同的,并且不会出现在所考虑的后缀中。从 t 的多个变体中,选择字典顺序最小的(如果 a = 4 并且后缀为“bfdd”,则计算机选择等于“aceg”的字符串 t)。之后,将所选字符串 t 附加到 s 的末尾。

B 先生很快发现这个游戏很无聊,并提出了以下问题:在位置 l 和 r(含)之间的段上,字符串 s 中不同字母的最小可能数量是多少。字符串 s 的字母从 1 开始编号。

输入

第一行也是唯一一行包含四个空格分隔的整数:a、b、l 和 r (1 ≤ a, b ≤ 12, 1 ≤ l ≤ r ≤ 109) — 每个玩家附加的字母数量和段的边界。

输出

打印一个整数 — 字符串 s 中从位置 l 到位置 r(含)的段中不同字母的最小可能数量。

示例

输入 #1

1 1 1 8

输出 #1

2

输入 #2

4 2 2 6

输出 #2

3

输入 #3

3 7 4 6

输出 #3

1

注意

在第一个示例测试中,最佳策略之一生成字符串 s =“abababab...”,这就是答案为 2 的原因。

在第二个样本测试字符串 s = "abcdbcaefg..." 中可以得到,选择的段将看起来像 "bcdbc",这就是为什么答案是 3。

在第三个样本测试字符串 s = "abczzzacad..." 中可以得到,选择,段将看起来像 "zzz",这就是为什么答案是 1。