{"problem":{"name":"B. Students in Railway Carriage","description":{"content":"There are $n$ consecutive seat places in a railway carriage. Each place is either empty or occupied by a passenger. The university team for the Olympiad consists of $a$ student-programmers and $b$ st","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF962B"},"statements":[{"statement_type":"Markdown","content":"There are $n$ consecutive seat places in a railway carriage. Each place is either empty or occupied by a passenger.\n\nThe university team for the Olympiad consists of $a$ student-programmers and $b$ student-athletes. Determine the largest number of students from all $a+b$ students, which you can put in the railway carriage so that:\n\n*   no student-programmer is sitting next to the student-programmer;\n*   and no student-athlete is sitting next to the student-athlete.\n\nIn the other words, there should not be two consecutive (adjacent) places where two student-athletes or two student-programmers are sitting.\n\nConsider that initially occupied seat places are occupied by jury members (who obviously are not students at all).\n\n## Input\n\nThe first line contain three integers $n$, $a$ and $b$ ($1 \\le n \\le 2\\cdot10^{5}$, $0 \\le a, b \\le 2\\cdot10^{5}$, $a + b > 0$) — total number of seat places in the railway carriage, the number of student-programmers and the number of student-athletes.\n\nThe second line contains a string with length $n$, consisting of characters \"_._\" and \"_*_\". The dot means that the corresponding place is empty. The asterisk means that the corresponding place is occupied by the jury member.\n\n## Output\n\nPrint the largest number of students, which you can put in the railway carriage so that no student-programmer is sitting next to a student-programmer and no student-athlete is sitting next to a student-athlete.\n\n[samples]\n\n## Note\n\nIn the first example you can put all student, for example, in the following way: _*.AB*_\n\nIn the second example you can put four students, for example, in the following way: _*BAB*B_\n\nIn the third example you can put seven students, for example, in the following way: _B*ABAB**A*B_\n\nThe letter _A_ means a student-programmer, and the letter _B_ — student-athlete.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"铁轨车厢中有 $n$ 个连续的座位。每个座位要么为空，要么被一名乘客占用。\n\n大学奥赛队由 $a$ 名学生程序员和 $b$ 名学生运动员组成。请确定最多可以将多少名学生（来自全部 $a + b$ 名学生）安排进车厢，使得：\n\n换句话说，不能有两个相邻的座位同时被两名学生运动员或两名学生程序员占据。\n\n假设初始已被占用的座位均由裁判（显然不是学生）占据。\n\n第一行包含三个整数 $n$、$a$ 和 $b$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$0 lt.eq a, b lt.eq 2 dot.op 10^5$，$a + b > 0$）——分别表示车厢中的座位总数、学生程序员人数和学生运动员人数。\n\n第二行是一个长度为 $n$ 的字符串，由字符 \"_._\" 和 \"_*_\" 组成。点号表示对应座位为空，星号表示对应座位被裁判占用。\n\n请输出最多可以安排进车厢的学生人数，使得没有两名学生程序员相邻，也没有两名学生运动员相邻。\n\n在第一个例子中，你可以安排所有学生，例如：_*.AB*_\n\n在第二个例子中，你可以安排四名学生，例如：_*BAB*B_\n\n在第三个例子中，你可以安排七名学生，例如：_B*ABAB**A*B_\n\n其中字母 _A_ 表示学生程序员，字母 _B_ 表示学生运动员。\n\n## Input\n\n第一行包含三个整数 $n$、$a$ 和 $b$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$0 lt.eq a, b lt.eq 2 dot.op 10^5$，$a + b > 0$）——分别表示车厢中的座位总数、学生程序员人数和学生运动员人数。第二行是一个长度为 $n$ 的字符串，由字符 \"_._\" 和 \"_*_\" 组成。点号表示对应座位为空，星号表示对应座位被裁判占用。\n\n## Output\n\n请输出最多可以安排进车厢的学生人数，使得没有两名学生程序员相邻，也没有两名学生运动员相邻。\n\n[samples]\n\n## Note\n\n在第一个例子中，你可以安排所有学生，例如：_*.AB*_\n\n在第二个例子中，你可以安排四名学生，例如：_*BAB*B_\n\n在第三个例子中，你可以安排七名学生，例如：_B*ABAB**A*B_\n\n其中字母 _A_ 表示学生程序员，字母 _B_ 表示学生运动员。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of consecutive seats.  \nLet $ a, b \\in \\mathbb{Z}_{\\geq 0} $ be the number of student-programmers and student-athletes, respectively, with $ a + b > 0 $.  \nLet $ S \\in \\{ \\text{.}, \\text{*} \\}^n $ be a string representing seat occupancy:  \n- $ \\text{.} $ denotes an empty seat (available for students),  \n- $ \\text{*} $ denotes an occupied seat (by jury, unavailable).  \n\nLet $ I \\subseteq \\{1, 2, \\dots, n\\} $ be the set of indices where seats are available (i.e., $ S_i = \\text{.} $).  \nLet $ m = |I| $ be the number of available seats.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 0 \\leq a, b \\leq 2 \\cdot 10^5 $, $ a + b > 0 $  \n3. The available seats form contiguous or non-contiguous segments; adjacency is defined by consecutive indices in $ \\{1, \\dots, n\\} $.  \n\n**Objective**  \nMaximize the total number of students $ x = x_a + x_b $ placed on available seats, where:  \n- $ x_a \\leq a $, $ x_b \\leq b $,  \n- No two adjacent available seats are assigned to two student-programmers,  \n- No two adjacent available seats are assigned to two student-athletes.  \n\nEquivalently, the assignment to adjacent available seats must alternate between programmer (A) and athlete (B).  \n\n**Key Insight**  \nThe problem reduces to:  \n- Partition the available seats into maximal contiguous blocks of consecutive `.`.  \n- For each contiguous block of length $ L $, the maximum number of students that can be placed is $ L $, under the alternating constraint.  \n- The maximum number of A’s and B’s in a block of length $ L $ is:  \n  $$\n  \\left\\lceil \\frac{L}{2} \\right\\rceil \\text{ of one type}, \\quad \\left\\lfloor \\frac{L}{2} \\right\\rfloor \\text{ of the other}\n  $$  \n  (and we can choose which type starts).  \n- Thus, over all blocks, the total maximum possible A’s and B’s are bounded by:  \n  $$\n  A_{\\max} = \\sum_{\\text{blocks}} \\left\\lceil \\frac{L_i}{2} \\right\\rceil, \\quad\n  B_{\\max} = \\sum_{\\text{blocks}} \\left\\lfloor \\frac{L_i}{2} \\right\\rfloor\n  $$  \n  (or vice versa, since we can flip the assignment per block).  \n- The optimal total is:  \n  $$\n  \\min(a + b,\\; m,\\; \\max_{\\text{assignments}} (x_a + x_b))\n  $$  \n  where $ x_a \\leq \\min(a, A_{\\max} + B_{\\max} - B_{\\min}) $, etc. — but more simply:  \n\n**Final Formulation**  \nLet $ \\text{blocks} = \\{L_1, L_2, \\dots, L_k\\} $ be the lengths of maximal contiguous available seat segments.  \nDefine:  \n$$\nA_{\\text{total}} = \\sum_{i=1}^k \\left\\lceil \\frac{L_i}{2} \\right\\rceil, \\quad\nB_{\\text{total}} = \\sum_{i=1}^k \\left\\lfloor \\frac{L_i}{2} \\right\\rfloor\n$$  \nThen the maximum number of students that can be seated is:  \n$$\n\\min(a + b,\\; m,\\; \\min(a, A_{\\text{total}}) + \\min(b, B_{\\text{total}}))\n$$  \n**But wait**: since we can *choose* for each block whether to start with A or B, the optimal is:  \n$$\n\\min(a + b,\\; m,\\; \\min(a + b,\\; A_{\\text{total}} + B_{\\text{total}}),\\; \\max_{x_a + x_b} \\{ x_a \\leq a, x_b \\leq b, x_a \\leq A_{\\text{total}}, x_b \\leq B_{\\text{total}}, x_a + x_b \\leq m \\})\n$$  \n\nActually, since $ A_{\\text{total}} + B_{\\text{total}} = m $, and we can assign optimally per block (i.e., assign more A’s to blocks where we need them), the maximum number of students is:  \n$$\n\\min(a + b,\\; m,\\; \\min(a, A_{\\text{total}}) + \\min(b, B_{\\text{total}}))\n$$  \nis **incorrect** because we can swap A/B per block.\n\nThe correct and known optimal approach is:  \nLet $ T = \\sum_{i=1}^k \\left\\lfloor \\frac{L_i}{2} \\right\\rfloor $, and $ R = \\sum_{i=1}^k (L_i \\bmod 2) $ (number of blocks with odd length).  \nThen, maximum A’s we can place is $ T + R $, maximum B’s is $ T $, or vice versa.  \nSo total possible under alternating constraint is $ T + R = m $, and we can distribute up to $ T + R $ of one type and $ T $ of the other.\n\nThus, the maximum number of students we can place is:  \n$$\n\\min(a + b,\\; m,\\; \\min(a, T + R) + \\min(b, T)) \\quad \\text{or} \\quad \\min(a + b,\\; m,\\; \\min(a, T) + \\min(b, T + R))\n$$  \nSo the maximum is:  \n$$\n\\min(a + b,\\; m,\\; \\min(a, T + R) + \\min(b, T),\\; \\min(a, T) + \\min(b, T + R))\n$$  \nBut since $ \\min(a, T + R) + \\min(b, T) \\geq \\min(a, T) + \\min(b, T + R) $ is not guaranteed, we take the **maximum** of the two assignments:\n\n$$\n\\boxed{\n\\min\\left(a + b,\\; m,\\; \\max\\left( \\min(a, T + R) + \\min(b, T),\\; \\min(a, T) + \\min(b, T + R) \\right) \\right)\n}\n$$\n\nWhere:  \n- $ m = $ number of available seats (dots),  \n- $ T = \\sum_{i} \\left\\lfloor \\frac{L_i}{2} \\right\\rfloor $,  \n- $ R = $ number of blocks with odd length $ L_i $,  \n- $ T + R = \\sum_{i} \\left\\lceil \\frac{L_i}{2} \\right\\rceil $.\n\nThis is the formal mathematical formulation.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF962B","tags":["constructive algorithms","greedy","implementation"],"sample_group":[["5 1 1\n*...*","2"],["6 2 3\n*...*.","4"],["11 3 10\n.*....**.*.","7"],["3 2 3\n***","0"]],"created_at":"2026-03-03 11:00:39"}}