English · Original
Chinese · Translation
Formal · Original
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.
## Input
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
## Output
Print the maximum possible number of cuts which can be made while spending no more than $B$ bitcoins.
[samples]
## Note
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.
有许多东西可以被切割——树木、纸张、"绳子"。在本题中，你要切割一个整数序列。
有一个整数序列，其中偶数和奇数的个数相等。在预算有限的情况下，你需要进行尽可能多的切割，使得每个 resulting segment（结果段）中奇数和偶数的个数相同。
切割将序列分割为连续（相邻）的段。你可以将每次切割视为序列中两个相邻元素之间的断开。切割后，每个元素恰好属于一个段。例如，$[ 4, 1, 2, 3, 4, 5, 4, 4, 5, 5 ]$ $arrow.r$ 两次切割 $arrow.r$ $[ 4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5 ]$。在每个段中，偶数的个数必须等于奇数的个数。
在数字 $x$ 和 $y$ 之间进行切割的代价是 $| x -y |$ 比特币。求在总花费不超过 $B$ 比特币的前提下，最多能进行多少次切割。
输入的第一行包含两个整数 $n$ ($2 lt.eq n lt.eq 100$) 和 $B$ ($1 lt.eq B lt.eq 100$) —— 序列中元素的个数和你拥有的比特币数量。
第二行包含 $n$ 个整数：$a_1$, $a_2$, ..., $a_n$ ($1 lt.eq a_i lt.eq 100$) —— 序列的元素，其中偶数和奇数的个数相等。
请输出在花费不超过 $B$ 比特币的前提下，最多能进行的切割次数。
在第一个样例中，最优解是在 $2$ 和 $5$ 之间切割。这次切割的代价为 $3$ 比特币。
在第二个样例中，即使拥有无限多的比特币，也无法进行任何一次切割。
在第三个样例中，应在 $2$ 和 $3$ 之间以及 $4$ 和 $5$ 之间进行切割。切割的总代价为 $1 + 1 = 2$ 比特币。
## Input
输入的第一行包含两个整数 $n$ ($2 lt.eq n lt.eq 100$) 和 $B$ ($1 lt.eq B lt.eq 100$) —— 序列中元素的个数和你拥有的比特币数量。第二行包含 $n$ 个整数：$a_1$, $a_2$, ..., $a_n$ ($1 lt.eq a_i lt.eq 100$) —— 序列的元素，其中偶数和奇数的个数相等
## Output
请输出在花费不超过 $B$ 比特币的前提下，最多能进行的切割次数。
[samples]
## Note
在第一个样例中，最优解是在 $2$ 和 $5$ 之间切割。这次切割的代价为 $3$ 比特币。在第二个样例中，即使拥有无限多的比特币，也无法进行任何一次切割。在第三个样例中，应在 $2$ 和 $3$ 之间以及 $4$ 和 $5$ 之间进行切割。切割的总代价为 $1 + 1 = 2$ 比特币。
**Definitions**
Let $ n \in \mathbb{Z} $ be the length of the sequence, and $ B \in \mathbb{Z} $ be the budget.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, with exactly $ \frac{n}{2} $ even and $ \frac{n}{2} $ odd integers.
For each position $ i \in \{1, 2, \dots, n-1\} $, define a **cut candidate** at index $ i $ (between $ a_i $ and $ a_{i+1} $) with cost $ c_i = |a_i - a_{i+1}| $.
Define the **prefix balance** at position $ i $ as:
$$
b_i = (\text{number of odd elements in } a_1, \dots, a_i) - (\text{number of even elements in } a_1, \dots, a_i)
$$
A cut at position $ i $ is **valid** if $ b_i = 0 $.
**Constraints**
1. $ 2 \leq n \leq 100 $
2. $ 1 \leq B \leq 100 $
3. $ 1 \leq a_i \leq 100 $ for all $ i \in \{1, \dots, n\} $
4. The sequence contains equal numbers of even and odd integers: $ \sum_{i=1}^n \mathbf{1}_{\{a_i \text{ odd}\}} = \sum_{i=1}^n \mathbf{1}_{\{a_i \text{ even}\}} = \frac{n}{2} $
**Objective**
Find the maximum number of valid cuts $ k $ such that:
- Each cut is at a position $ i \in \{1, \dots, n-1\} $ with $ b_i = 0 $,
- The sum of costs of selected cuts $ \leq B $,
- Cuts are chosen to maximize $ k $.
That is, let $ C = \{ c_i \mid i \in \{1, \dots, n-1\}, b_i = 0 \} $.
Find the maximum $ k $ such that there exists a subset of $ k $ elements from $ C $ whose sum is $ \leq B $.
API Response (JSON)
{
"problem": {
"name": "B. Cutting",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF998B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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.\n\nThere is a sequence of integers, which contains the equal number ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "有许多东西可以被切割——树木、纸张、\"绳子\"。在本题中，你要切割一个整数序列。\n\n有一个整数序列，其中偶数和奇数的个数相等。在预算有限的情况下，你需要进行尽可能多的切割，使得每个 resulting segment（结果段）中奇数和偶数的个数相同。\n\n切割将序列分割为连续（相邻）的段。你可以将每次切割视为序列中两个相邻元素之间的断开。切割后，每个元素恰好属于一个段。例如，$[ 4, 1, 2, 3...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the length of the sequence, and $ B \\in \\mathbb{Z} $ be the budget. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, with exactly $ \\frac{n...",
"is_translate": false,
"language": "Formal"
}
]
}