← 返回题目列表

Codeforces · 1198/A

A. MP3音频

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

将声音数字化的一种常见方法是记录特定时刻的声音强度。对于每个时刻,强度被记录为非负整数。因此,我们可以将声音文件表示为 $$$n$$$ 非负整数数组。

如果数组中正好有 $$$K$$$ 不同的值,那么我们需要 $$$k = \lceil \log_{2} K \rceil$$$ 位来存储每个值。然后需要 $$$nk$$$ 位来存储整个文件。

为了减少内存消耗,我们需要应用一些压缩。一种常见的方法是减少可能的强度值的数量。我们选择两个整数 $$$l \le r$$$,之后所有强度值都按以下方式更改:如果强度值在 $$$[l;r]$$$ 范围内,我们不更改它。如果小于$$$l$$$,我们将其改为$$$l$$$;如果它大于$$$r$$$,我们将其更改为$$$r$$$。您可以看到我们失去了一些低强度和一些高强度。

您的任务是应用此压缩,使文件适合大小为 $$$I$$$ 字节的磁盘,并且数组中更改的元素数量尽可能最少。

我们提醒您,$$$1$$$ 字节包含 $$$8$$$ 位。

$$$k = \lceil log_{2} K \rceil$$$ 是满足 $$$K \le 2^{k}$$$ 的最小整数。特别是,如果 $$$K = 1$$$,则 $$$k = 0$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$I$$$ ($$$1 \le n \le 4 \cdot 10^{5}$$$, $$$1 \le I \le 10^{8}$$$) - 分别是数组的长度和磁盘的大小(以字节为单位)。

下一行包含 $$$n$$$ 整数 $$$a_{i}$$$ ($$$0 \le a_{i} \le 10^{9}$$$) — 表示声音文件的数组。

输出

打印单个整数——更改元素的最小可能数量。

示例

输入 #1

6 1
2 1 2 3 4 3

输出 #1

2

输入 #2

6 2
2 1 2 3 4 3

输出 #2

0

输入 #3

6 1
1 1 2 2 3 3

输出 #3

2

注意

在第一个例子中我们可以选择$$$l=2, r=3$$$。该数组变为 2 2 2 3 3 3,不同元素的数量为 $$$K=2$$$,并且声音文件适合磁盘。仅更改两个值。

在第二个示例中,磁盘较大,因此初始文件适合它,不需要进行任何更改。

在第三个示例中,我们必须更改两个 1 或两个 3。