← 返回题目列表

Codeforces · 998/B

B. 切割

中文机器翻译题面 查看原题

有很多东西可以砍伐——树木、纸张、“绳子”。在这个问题中,您将切割一个整数序列。

有一个整数序列,其中包含相同数量的偶数和奇数。在预算有限的情况下,您需要进行尽可能多的切割,以便每个结果段都具有相同数量的奇数和偶数整数。

将序列剪切为连续(连续)的片段。您可以将每次剪切视为序列中两个相邻元素之间的中断。因此,切割后每个元素都属于一个片段。比如说,$$$[4, 1, 2, 3, 4, 5, 4, 4, 5, 5]$$$ $$$\to$$$ 两次切割 $$$\to$$$ $$$[4, 1 | 2、3、4、5 | 4, 4, 5, 5]$$$。每个段上偶数元素的数量应等于奇数元素的数量。

$$$x$$$ 和 $$$y$$$ 数字之间的削减成本为 $$$|x - y|$$$ 比特币。找出在花费不超过 $$$B$$$ 比特币的情况下可以进行的最大可能削减次数。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) 和一个整数 $$$B$$$ ($$$1 \le B \le 100$$$) - 序列中的元素数量和您拥有的比特币数量。

第二行包含 $$$n$$$ 整数:$$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 100$$$) — 序列的元素,其中包含相同数量的偶数和奇数

输出

打印花费不超过 $$$B$$$ 比特币时可以进行的最大可能削减次数。

示例

输入 #1

6 4
1 2 5 10 15 20

输出 #1

1

输入 #2

4 10
1 3 2 4

输出 #2

0

输入 #3

6 100
1 2 3 4 5 6

输出 #3

2

注意

在第一个示例中,最佳答案是在 $$$2$$$ 和 $$$5$$$ 之间分割序列。此次削减的价格相当于 $$$3$$$ 比特币。

在第二个样本中,即使有无限数量的比特币,也不可能进行一次切割。

在第三个示例中,序列应在 $$$2$$$ 和 $$$3$$$ 之间以及 $$$4$$$ 和 $$$5$$$ 之间剪切。削减的总价格为 $$$1 + 1 = 2$$$ 比特币。