103322: [Atcoder]ABC332 C - T-shirts

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

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, and 2.
  • $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$ 的由 012 组成的字符串 $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$ 的由 012 组成的字符串。
  • $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恤衫。

加入题单

上一题 下一题 算法标签: