{"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 English letters. There are two players: Mister B and his competitor.\n\nInitially 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_\").\n\nThe players take turns appending letters to string _s_. Mister B moves first.\n\nMister 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.\n\nMister 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_.\n\nMister 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.\n\n## Input\n\nFirst 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.\n\n## Output\n\nPrint one integer — the minimum possible number of different letters in the segment from position _l_ to position _r_, inclusive, in string _s_.\n\n[samples]\n\n## Note\n\nIn the first sample test one of optimal strategies generate string _s_ = \"_abababab..._\", that's why answer is 2.\n\nIn the second sample test string _s_ = \"_abcdbcaefg..._\" can be obtained, chosen segment will look like \"_bcdbc_\", that's why answer is 3.\n\nIn the third sample test string _s_ = \"_abczzzacad..._\" can be obtained, chosen, segment will look like \"_zzz_\", that's why answer is 1.","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] 为 \"_abcde_\"）。\n\n两名玩家轮流向字符串 #cf_span[s] 末尾追加字母。Mister B 先手。\n\nMister B 每次必须恰好追加 #cf_span[b] 个字母，他可以任意选择这些字母。他的对手每次则恰好追加 #cf_span[a] 个字母。\n\nMister 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] 的末尾。\n\nMister B 很快觉得这个游戏无聊，于是提出了一个问题：在字符串 #cf_span[s] 的第 #cf_span[l] 到第 #cf_span[r] 个位置（包含两端）的子段中，最少可能有多少个不同的字母？字符串 #cf_span[s] 的字母编号从 #cf_span[1] 开始。\n\n输入仅一行，包含四个用空格分隔的整数：#cf_span[a], #cf_span[b], #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ a, b ≤ 12]，#cf_span[1 ≤ l ≤ r ≤ 109]），分别表示每位玩家每次追加的字母数和子段的边界。\n\n输出一个整数，表示在字符串 #cf_span[s] 的第 #cf_span[l] 到第 #cf_span[r] 个位置（包含两端）的子段中，最少可能的不同字母数量。\n\n在第一个样例中，一种最优策略生成的字符串为 #cf_span[s = ]\"_abababab..._\"，因此答案为 #cf_span[2]。\n\n在第二个样例中，可以得到字符串 #cf_span[s = ]\"_abcdbcaefg..._\"，所选子段为 \"_bcdbc_\"，因此答案为 #cf_span[3]。\n\n在第三个样例中，可以得到字符串 #cf_span[s = ]\"_abczzzacad..._\"，所选子段为 \"_zzz_\"，因此答案为 #cf_span[1]。\n\n## Input\n\n第一行仅包含四个用空格分隔的整数：#cf_span[a], #cf_span[b], #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ a, b ≤ 12]，#cf_span[1 ≤ l ≤ r ≤ 109]），分别表示每位玩家每次追加的字母数和子段的边界。\n\n## Output\n\n输出一个整数，表示在字符串 #cf_span[s] 的第 #cf_span[l] 到第 #cf_span[r] 个位置（包含两端）的子段中，最少可能的不同字母数量。\n\n[samples]\n\n## Note\n\n在第一个样例中，一种最优策略生成的字符串为 #cf_span[s = ]\"_abababab..._\"，因此答案为 #cf_span[2]。在第二个样例中，可以得到字符串 #cf_span[s = ]\"_abcdbcaefg..._\"，所选子段为 \"_bcdbc_\"，因此答案为 #cf_span[3]。在第三个样例中，可以得到字符串 #cf_span[s = ]\"_abczzzacad..._\"，所选子段为 \"_zzz_\"，因此答案为 #cf_span[1]。","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 $ \\Sigma = \\{ \\text{a}, \\text{b}, \\dots \\} $, constructed as follows:  \n- Initially, $ s = \\text{a}\\text{b}\\cdots\\text{a} $ (first $ a $ lowercase English letters).  \n- Players alternate turns, starting with Mister B.  \n- On each turn, Mister B appends exactly $ b $ arbitrary letters.  \n- On each opponent turn, the computer appends a string $ t $ of length $ a $, where:  \n  - $ t $ consists of $ a $ distinct letters.  \n  - No letter in $ t $ appears in the last $ a $ characters of $ s $.  \n  - $ t $ is lexicographically minimal among all such strings.  \n\n**Constraints**  \n1. $ 1 \\leq a, b \\leq 12 $  \n2. $ 1 \\leq l \\leq r \\leq 10^9 $  \n\n**Objective**  \nMinimize the number of distinct letters in the substring $ s[l:r] $, over all possible choices Mister B can make on his turns.  \nOutput this minimum number.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF820C","tags":["games","greedy"],"sample_group":[["1 1 1 8","2"],["4 2 2 6","3"],["3 7 4 6","1"]],"created_at":"2026-03-03 11:00:39"}}