题目描述

某大型樱桃加工厂使用自动化机械扫描了一批樱桃的尺寸大小。现在获得了直径范围 $[L,H]$ 各个区间所有的樱桃个数统计。现需通过 $m$ 个等级（$m < H - L$）来筛选不同尺寸大小的樱桃，筛选后需使得各等级内的樱桃数量和的标准差最小。

• 输入第一行：两个整数 $n$（樱桃总组数，$2 < n \le 20$）和 $m$（需要的等级数，$2 < m < n$）。
• 输入第二行：长度为 $n$ 的整数序列 $A = [a_0, a_1, \dots, a_{n-1}]$，其中 $a_i$ 表示第 $i$ 组直径对应的樱桃个数（$0 < a_i < 100$）。

输出长度为 $m$ 的序列 $B = [b_0, b_1, \dots, b_{m-1}]$，其中：

题目内容

某大型樱桃加工厂使用自动化机械扫描了一批樱桃的尺寸大小。现在获得了直径范围 $[L,H]$ 各个区间所有的樱桃个数统计。现在需要通过 $m$ 个等级 $(m<H-L)$ 来筛选不同尺寸大小的樱桃，筛选后需使得各等级内的樱桃数目的标准差最小。

输入描述

第一行输入两个数字，第一个数字表示樱桃的总组数 $n(2<n<= 20)$ ，第二个数字 $m$ 表示需要获取的等级数目 $a$ ，$2<a<n$

第二行输入一个长度为 $H-L+1$ 的数列 $A$ ，$a<H-L+1$，其中的第 $i$ 个元素 $a_i$ ；表示直径为 $L+i$ 樱桃个数 $(i∈[0,H-L])，0< a_i <100$.

输出描述

输出长度为 $m$ 的数列 $B$ ，其中的第 $1$ 个元素 $b_0$ 表示顺序从 $A$ 中取 $b_0$ 个元素，将该尺寸范围内的樱桃作为一个分类等级；第 $2$ 个元素 $b$ 表示顺序从 $A$ 中起始点 $b_0$ 开始取 $b_1$ 个元素，将该尺寸范围内的樱桃作为一个分类等级，依次类推。

样例1

输入

9 3
1 2 3 4 5 6 7 8 9

输出

5 2 2

说明

要把 $9$ 组樱桃分为三组，使得三组樱桃数量和的标准差最小

顺序取数列 $5$ 个元素和为 $1+2+3+4+5=15$

再顺序取数列 $2$ 个元素和 $6+7=13$

再顺序取数列 $2$ 个元素和 $8+9=17$

$[15$ $13$ $17]$ 的平均值为 $15$ ，标准差为 $sqrt((15-15)^2+(15-13)^2+(15-17)^2)/3$，为所有筛选方案中的最小值。

样例2

输入

10 4
16 40 37 20 18 30 18 60 50 37

输出

3 3 2 2

说明

顺序取数列 $3$ 个元素和为 $16+40+37=93$

再顺序取数列 $3$ 个元素和 $20+18+30=68$

再顺序取数列 $2$ 个元素和 $18+60=78$

再顺序取数列 $2$ 个元素和 $50+37=87$

$[93,68,78,87]$ 的平均值为 $81.5$ ，标准差为 $sqrt((93-81.5)^2$$+(68-81.5)^2$$+(78-81.5)^2$$+(87-81.5)^2)/4$ ，为所有筛选方案中的最小值。

提示

测试样例保证输出答案唯一