bzoj#P2390. 序列划分

序列划分

题目描述

最近小风沉醉于研究数。

由于他对 00 情有独钟(经常暴 00……),因此他认为非 00 数都是不和谐的。

于是他研究上了二进制数,因为里面的非 00 数只有 11

即便如此,11 还是令他很不爽……

于是他想把所有的 kk 位二进制数 0,1,,2k10,1,\dots, 2^k-1 划分成 mm 组,每一组都是连续的一些数。设 Si(1im)S_i(1\le i\le m) 表示第 ii 组中所有数中的 11 的个数和。

小风想知道,所有的划分方案中,max{Si}\max\{S_i\} 的最小值是多少。

输入格式

有且仅有一行:两个数 k,mk,m,用一个空格分开。

输出格式

有且仅有一行:一个数,表示 max{Si}\max\{S_i\} 的最小值。

样例输入

3 4

样例输出

4

样例说明

分成如下 44 组最优:

$$000,001,010,011\\ 100,101\\ 110\\ 111\\ S_1 = 4,S_2 = 3,S_3 = 2,S_4 = 3\\ \max\{S_i\} = 4 $$

数据规模与约定

20%20\% 的数据中,k20k \le 20

100%100\% 的数据中,1k1001 \le k \le 100, 1m1001 \le m \le 100m2km\le 2^k