C. Mister B and Boring Game

Codeforces

IDCF820C

Time2000ms

Memory256MB

Difficulty—

gamesgreedy

English · Original

Chinese · Translation

Formal · Original

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 ≤ 109]），分别表示每位玩家每次追加的字母数和子段的边界。输出一个整数，表示在字符串 #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 ≤ 109]），分别表示每位玩家每次追加的字母数和子段的边界。 ## 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 = \text{a}\text{b}\cdots\text{a} $ (first $ a $ lowercase English letters). - Players alternate turns, starting with Mister B. - On each turn, Mister B appends exactly $ b $ arbitrary letters. - On each opponent turn, the computer appends a string $ t $ of length $ a $, where: - $ t $ consists of $ a $ distinct letters. - No letter in $ t $ appears in the last $ a $ characters of $ s $. - $ t $ is lexicographically minimal among all such strings. **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] $, over all possible choices Mister B can make on his turns. Output this minimum number.

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": "C. Mister B and Boring Game",
    "description": {
      "content": "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 Engli",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF820C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\nAll characters in this game are lowercase Engli...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有时，Mister B 在空闲的晚上不知道该做什么。幸运的是，Mister B 发现了一个新游戏，玩家可以与外星人对战。\n\n该游戏中的所有字符均为小写英文字母。共有两名玩家：Mister B 和他的对手。\n\n初始时，两名玩家拥有一个字符串 #cf_span[s]，它由按字母顺序排列的前 #cf_span[a] 个英文字母组成（例如，若 #cf_span[a = 5]，则 #cf_span[s] 为...",
      "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 $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments