103322: [Atcoder]ABC332 C - T-shirts
Description
Score : $300$ points
Problem Statement
AtCoder Inc. sells T-shirts with its logo.
You are given Takahashi's schedule for $N$ days as a string $S$ of length $N$ consisting of 0, 1, and 2.
Specifically, for an integer $i$ satisfying $1\leq i\leq N$,
- if the $i$-th character of $S$ is
0, he has no plan scheduled for the $i$-th day; - if the $i$-th character of $S$ is
1, he plans to go out for a meal on the $i$-th day; - if the $i$-th character of $S$ is
2, he plans to attend a competitive programming event on the $i$-th day.
Takahashi has $M$ plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.
- On days he goes out for a meal, he will wear a plain or logo T-shirt.
- On days he attends a competitive programming event, he will wear a logo T-shirt.
- On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
- Once he wears a T-shirt, he cannot wear it again until he washes it.
Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the $N$ days. If he does not need to buy new T-shirts, print $0$.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.
Constraints
- $1\leq M\leq N\leq 1000$
- $S$ is a string of length $N$ consisting of
0,1, and2. - $N$ and $M$ are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $S$
Output
Print the minimum number of T-shirts Takahashi needs to buy to be able to satisfy the conditions in the problem statement.
If he does not need to buy new T-shirts, print $0$.
Sample Input 1
6 1 112022
Sample Output 1
2
If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:
- On the first day, he wears a logo T-shirt to go out for a meal.
- On the second day, he wears a plain T-shirt to go out for a meal.
- On the third day, he wears a logo T-shirt to attend a competitive programming event.
- On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
- On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
- On the sixth day, he wears a logo T-shirt to attend a competitive programming event.
If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print $2$.
Sample Input 2
3 1 222
Sample Output 2
3
Sample Input 3
2 1 01
Sample Output 3
0
He does not need to buy new T-shirts.
Input
Output
分数：300分
问题描述
AtCoder Inc. 销售带有其徽标的T恤衫。
你会得到高桥君在 $N$ 天的日程安排，这是一个长度为 $N$ 的由 0、1 和 2 组成的字符串 $S$。
- 如果字符串 $S$ 的第 $i$ 个字符是
0，那么他第 $i$ 天没有计划； - 如果字符串 $S$ 的第 $i$ 个字符是
1，那么他计划在第 $i$ 天出去吃饭； - 如果字符串 $S$ 的第 $i$ 个字符是
2，那么他计划在第 $i$ 天参加编程比赛。
高桥君有 $M$ 件普通T恤衫，都在第一天开始前洗好并准备好了穿。此外，为了满足以下条件，他会买几件带有AtCoder徽标的T恤衫。
- 在他出去吃饭的那天，他会穿普通或带有徽标的T恤衫。
- 在他参加编程比赛的那天，他会穿带有徽标的T恤衫。
- 在他没有计划的那天，他不会穿任何T恤衫。此外，他会在那一刻洗掉所有穿过的T恤衫。从第二天开始，他可以再次穿上它们。
- 一旦他穿上一件T恤衫，他就不能在不洗的情况下再次穿上它。
确定高桥君需要购买的最少T恤衫数量，以便在 $N$ 天内的所有预定日期都能穿上合适的T恤衫。如果他不需要购买新T恤衫，打印 $0$。假设购买的T恤衫也在第一天开始前洗好并准备好使用。
约束条件
- $1\leq M\leq N\leq 1000$
- $S$ 是一个长度为 $N$ 的由
0、1和2组成的字符串。 - $N$ 和 $M$ 是整数。
输入
输入从标准输入以以下格式给出：
$N$ $M$ $S$
输出
打印高桥君需要购买的最少T恤衫数量，以便满足问题描述中的条件。如果他不需要购买新T恤衫，打印 $0$。
样例输入1
6 1 112022
样例输出1
2
如果高桥君购买两件带有徽标的T恤衫，他可以按照以下方式穿T恤衫：
- 在第一天，他穿带有徽标的T恤衫出去吃饭。
- 在第二天，他穿普通T恤衫出去吃饭。
- 在第三天，他穿带有徽标的T恤衫参加编程比赛。
- 在第四天，他没有计划，所以他洗掉所有穿过的T恤衫。这使他能够在第一天、第二天和第三天再次使用穿过的T恤衫。
- 在第五天，他穿带有徽标的T恤衫参加编程比赛。
- 在第六天，他穿带有徽标的T恤衫参加编程比赛。
如果他购买一件或更少带有徽标的T恤衫，无论他如何使用，都无法满足条件。因此，打印 $2$。
样例输入2
3 1 222
样例输出2
3
样例输入3
2 1 01
样例输出3
0
他不需要购买新T恤衫。