A. Mister B and Boring Game

Codeforces

IDCF819A

Time2000ms

Memory256MB

Difficulty—

gamesgreedy

English · Original

Chinese · Translation

Formal · Original

**Unfortunately, a mistake was found in the proof of the author's solution to this problem. Currently, we don't know the absolutely correct solution. However, you can solve this task, but if your solution passes all the tests, it is not guaranteed to be correct. If your solution has passed all the tests, and you are sure that it is correct, you can write to one of the contest authors about it.** Sometimes Mister B has free evenings when he doesn't know what to do. Fortunately, Mister B found a new game, where the player can play against aliens. All characters in this game are lowercase English letters. There are two players: Mister B and his competitor. Initially the players have a string _s_ consisting of the first _a_ English letters in alphabetical order (for example, if _a_ = 5, then _s_ equals to "_abcde_"). The players take turns appending letters to string _s_. Mister B moves first. Mister B must append exactly _b_ letters on each his move. He can arbitrary choose these letters. His opponent adds exactly _a_ letters on each move. Mister B quickly understood that his opponent was just a computer that used a simple algorithm. The computer on each turn considers the suffix of string _s_ of length _a_ and generates a string _t_ of length _a_ such that all letters in the string _t_ are distinct and don't appear in the considered suffix. From multiple variants of _t_ lexicographically minimal is chosen (if _a_ = 4 and the suffix is "_bfdd_", the computer chooses string _t_ equal to "_aceg_"). After that the chosen string _t_ is appended to the end of _s_. Mister B soon found the game boring and came up with the following question: what can be the minimum possible number of different letters in string _s_ on the segment between positions _l_ and _r_, inclusive. Letters of string _s_ are numerated starting from 1. ## Input First and only line contains four space-separated integers: _a_, _b_, _l_ and _r_ (1 ≤ _a_, _b_ ≤ 12, 1 ≤ _l_ ≤ _r_ ≤ 109) — the numbers of letters each player appends and the bounds of the segment. ## Output Print one integer — the minimum possible number of different letters in the segment from position _l_ to position _r_, inclusive, in string _s_. [samples] ## Note In the first sample test one of optimal strategies generate string _s_ = "_abababab..._", that's why answer is 2. In the second sample test string _s_ = "_abcdbcaefg..._" can be obtained, chosen segment will look like "_bcdbc_", that's why answer is 3. In the third sample test string _s_ = "_abczzzacad..._" can be obtained, chosen, segment will look like "_zzz_", that's why answer is 1.

*不幸的是，本题作者解法的证明中发现了一个错误。目前我们尚不知晓绝对正确的解法。然而，你可以解决此题，但即使你的解法通过了所有测试用例，也不能保证其正确性。如果你的解法通过了所有测试用例，且你确信其正确，可以向比赛作者之一反馈。* 有时，Mister B 在晚上有空闲时间，却不知道该做什么。幸运的是，Mister B 发现了一款新游戏，玩家可以与外星人对战。游戏中所有字符均为小写英文字母。共有两名玩家：Mister B 和他的对手。初始时，两名玩家拥有一串 #cf_span[s]，由按字母顺序排列的前 #cf_span[a] 个英文字母组成（例如，若 #cf_span[a = 5]，则 #cf_span[s] 为 "_abcde_"）。两名玩家轮流向字符串 #cf_span[s] 末尾添加字母，Mister B 先手。 Mister B 每次必须恰好添加 #cf_span[b] 个字母，可任意选择这些字母。他的对手每次则恰好添加 #cf_span[a] 个字母。 Mister B 很快发现，他的对手只是一个使用简单算法的计算机。该计算机每回合会考虑字符串 #cf_span[s] 长度为 #cf_span[a] 的后缀，并生成一个长度为 #cf_span[a] 的字符串 #cf_span[t]，满足：#cf_span[t] 中所有字母互不相同，且均未出现在该后缀中。在所有满足条件的 #cf_span[t] 中，选择字典序最小者（例如，若 #cf_span[a = 4] 且后缀为 "_bfdd_"，则计算机选择 #cf_span[t] 为 "_aceg_"）。随后，将选出的字符串 #cf_span[t] 追加到 #cf_span[s] 末尾。 Mister B 觉得这个游戏无聊，于是提出了一个问题：在字符串 #cf_span[s] 的第 #cf_span[l] 到第 #cf_span[r] 位（含）这一段中，最少可能有多少个不同的字母？字符串 #cf_span[s] 的字母编号从 #cf_span[1] 开始。输入仅一行，包含四个用空格分隔的整数：#cf_span[a], #cf_span[b], #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ a, b ≤ 12]，#cf_span[1 ≤ l ≤ r ≤ 10^9]），分别表示每位玩家每次添加的字母数和所查询区间的左右端点。输出一个整数——在字符串 #cf_span[s] 的第 #cf_span[l] 到第 #cf_span[r] 位（含）这一段中，可能的最少不同字母数。在第一个样例中，一种最优策略生成的字符串为 #cf_span[s = ]"_abababab..._"，因此答案为 #cf_span[2]。在第二个样例中，可以得到字符串 #cf_span[s = ]"_abcdbcaefg..._"，所选区间为 "_bcdbc_"，因此答案为 #cf_span[3]。在第三个样例中，可以得到字符串 #cf_span[s = ]"_abczzzacad..._"，所选区间为 "_zzz_"，因此答案为 #cf_span[1]。 ## Input 第一行仅包含四个用空格分隔的整数：#cf_span[a], #cf_span[b], #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ a, b ≤ 12]，#cf_span[1 ≤ l ≤ r ≤ 10^9]），分别表示每位玩家每次添加的字母数和所查询区间的左右端点。 ## Output 输出一个整数——在字符串 #cf_span[s] 的第 #cf_span[l] 到第 #cf_span[r] 位（含）这一段中，可能的最少不同字母数。 [samples] ## Note 在第一个样例中，一种最优策略生成的字符串为 #cf_span[s = ]"_abababab..._"，因此答案为 #cf_span[2]。在第二个样例中，可以得到字符串 #cf_span[s = ]"_abcdbcaefg..._"，所选区间为 "_bcdbc_"，因此答案为 #cf_span[3]。在第三个样例中，可以得到字符串 #cf_span[s = ]"_abczzzacad..._"，所选区间为 "_zzz_"，因此答案为 #cf_span[1]。

**Definitions** Let $ a, b \in \mathbb{Z}^+ $ with $ 1 \leq a, b \leq 12 $. Let $ l, r \in \mathbb{Z} $ with $ 1 \leq l \leq r \leq 10^9 $. Let $ s $ be an infinite string over the alphabet $ \Sigma = \{ \text{a}, \text{b}, \dots \} $, constructed as follows: - Initially, $ s_0 = \text{a}\text{b}\cdots\text{a} $ (first $ a $ distinct lowercase letters). - Players alternate turns, with Mister B first. - On each of Mister B’s turns, he appends exactly $ b $ **arbitrary** letters. - On each opponent’s turn, the computer appends a string $ t $ of length $ a $, chosen as the **lexicographically minimal** string of $ a $ **distinct** letters, none of which appear in the last $ a $ characters of $ s $. **Constraints** 1. $ 1 \leq a, b \leq 12 $ 2. $ 1 \leq l \leq r \leq 10^9 $ **Objective** Minimize the number of **distinct letters** in the substring $ s[l:r] $ (inclusive), over all possible choices Mister B can make during his turns. Output: $ \min_{\text{Mister B's strategies}} \left| \{ s[i] \mid i \in [l, r] \} \right| $

Samples

Input #1

1 1 1 8

Output #1

Input #2

4 2 2 6

Output #2

Input #3

3 7 4 6

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Mister B and Boring Game",
    "description": {
      "content": "**Unfortunately, a mistake was found in the proof of the author's solution to this problem. Currently, we don't know the absolutely correct solution. However, you can solve this task, but if your solu",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF819A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**Unfortunately, a mistake was found in the proof of the author's solution to this problem. Currently, we don't know the absolutely correct solution. However, you can solve this task, but if your solu...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "*不幸的是，本题作者解法的证明中发现了一个错误。目前我们尚不知晓绝对正确的解法。然而，你可以解决此题，但即使你的解法通过了所有测试用例，也不能保证其正确性。如果你的解法通过了所有测试用例，且你确信其正确，可以向比赛作者之一反馈。*\n\n有时，Mister B 在晚上有空闲时间，却不知道该做什么。幸运的是，Mister B 发现了一款新游戏，玩家可以与外星人对战。\n\n游戏中所有字符均为小写英文字母。共...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b \\in \\mathbb{Z}^+ $ with $ 1 \\leq a, b \\leq 12 $.  \nLet $ l, r \\in \\mathbb{Z} $ with $ 1 \\leq l \\leq r \\leq 10^9 $.  \nLet $ s $ be an infinite string over the alphabet $ \\S...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments