Cutting

题意翻译

## 题目描述 有一个整数序列，其偶数和奇数的数量相同。给定有限的预算，您需要尽可能多地进行切割，使每个结果段具有相同数量的奇数和偶数。 “切割”操作将一个序列分成 $2$ 个连续的段。您可以将每次“切割”看作是序列中两个相邻元素之间的中断。所以在切割之后每个元素恰好属于一个片段。 举个例子，$[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$ 元内，最多可以切割几次？ ## 输入格式 第一行，输入 $2$ 个整数，$n$ 和 $B$（$2\le n\le 100$，$1\le B\le 100$），分别代表元素个数和你目前有的预算。 接下来的一行，输入 $n$ 个整数，$a_1,a_2,\cdots,a_n$，表示整个段内的元素。其中包含相同个数的奇数和偶数。 ## 输出格式 输出最多的“切割”次数，使其可以作出，且支出不超过 $B$ 元。

题目描述

There are a lot of things which could be cut — trees, paper, "the rope". In this problem you are going to cut a sequence of integers. There is a sequence of integers, which contains the equal number of even and odd numbers. Given a limited budget, you need to make maximum possible number of cuts such that each resulting segment will have the same number of odd and even integers. Cuts separate a sequence to continuous (contiguous) segments. You may think about each cut as a break between two adjacent elements in a sequence. So after cutting each element belongs to exactly one segment. Say, $ [4, 1, 2, 3, 4, 5, 4, 4, 5, 5] $ $ \to $ two cuts $ \to $ $ [4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5] $ . On each segment the number of even elements should be equal to the number of odd elements. The cost of the cut between $ x $ and $ y $ numbers is $ |x - y| $ bitcoins. Find the maximum possible number of cuts that can be made while spending no more than $ B $ bitcoins.

输入输出格式

输入格式

First line of the input contains an integer $ n $ ( $ 2 \le n \le 100 $ ) and an integer $ B $ ( $ 1 \le B \le 100 $ ) — the number of elements in the sequence and the number of bitcoins you have. Second line contains $ n $ integers: $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 1 \le a_i \le 100 $ ) — elements of the sequence, which contains the equal number of even and odd numbers

输出格式

Print the maximum possible number of cuts which can be made while spending no more than $ B $ bitcoins.

输入输出样例

输入样例 #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

说明

In the first sample the optimal answer is to split sequence between $ 2 $ and $ 5 $ . Price of this cut is equal to $ 3 $ bitcoins. In the second sample it is not possible to make even one cut even with unlimited number of bitcoins. In the third sample the sequence should be cut between $ 2 $ and $ 3 $ , and between $ 4 $ and $ 5 $ . The total price of the cuts is $ 1 + 1 = 2 $ bitcoins.