305082: CF962B. Students in Railway Carriage

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Students in Railway Carriage

题意翻译

有一个长度为 $n$ 的只含 `*.` 的字符串,你可以把其中的 `.` 换成 `A` 或 `B`,要求 `A` 不超过 $a$ 个, `B` 不超过 $b$ 个,且连续两个字符不能同时是 `A` 或者 `B`,求最多有多少个 `.` 被替换掉。 输入第一行三个整数表示 $n,a,b$,第二行表示给定字符串;输出一个整数表示结果。

题目描述

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 $ student-athletes. Determine the largest number of students from all $ a+b $ students, which you can put in the railway carriage so that: - no student-programmer is sitting next to the student-programmer; - and no student-athlete is sitting next to the student-athlete. In the other words, there should not be two consecutive (adjacent) places where two student-athletes or two student-programmers are sitting. Consider that initially occupied seat places are occupied by jury members (who obviously are not students at all).

输入输出格式

输入格式


The 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. The 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.

输出格式


Print 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.

输入输出样例

输入样例 #1

5 1 1
*...*

输出样例 #1

2

输入样例 #2

6 2 3
*...*.

输出样例 #2

4

输入样例 #3

11 3 10
.*....**.*.

输出样例 #3

7

输入样例 #4

3 2 3
***

输出样例 #4

0

说明

In the first example you can put all student, for example, in the following way: \*.AB\* In the second example you can put four students, for example, in the following way: \*BAB\*B In the third example you can put seven students, for example, in the following way: B\*ABAB\*\*A\*B The letter A means a student-programmer, and the letter B — student-athlete.

Input

题意翻译

有一个长度为 $n$ 的只含 `*.` 的字符串,你可以把其中的 `.` 换成 `A` 或 `B`,要求 `A` 不超过 $a$ 个, `B` 不超过 $b$ 个,且连续两个字符不能同时是 `A` 或者 `B`,求最多有多少个 `.` 被替换掉。 输入第一行三个整数表示 $n,a,b$,第二行表示给定字符串;输出一个整数表示结果。

加入题单

上一题 下一题 算法标签: