6733: 鸿雁传书

内存限制:125 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

小明给小红写了一封情书,他想把文章变得更完美,所以要进行排版。他一共写了 $N$ 个单词,为了美观,要把 $N$ 个单词分成 $K$ 行。单词的相对顺序不能变化。为了简化问题,无需考虑单词间的空格。小红会喜欢整齐的情书,小明想赢得小红的芳心,所以,他找到你,想让你帮他写一个程序,帮他排版,使得每行字母数的方差最小。请你求出最小的方差。

### 样例输入 #1
```
4 2
xxx xxxxx xxxx xx
(输入的本来是一封情书,被和谐了……)
```
### 样例输出 #1
```
1.0
```

输入格式

第 $1$ 行,两个正整数 $N,K$。第 $2$ 行,$N$ 个空格隔开的单词。

输出格式

一行,一个 $1$ 位小数表示每行字母数的最小方差。

输入样例 复制

4 2
xxx xxxxx xxxx xx

输出样例 复制

1.0

数据范围与提示

样例说明】
```plain
xxx xxxxx
xxxx xx
```
$1 \div 2 \times ((8-7)^2+(6-7)^2) = 1$。



【数据范围】
对于 $30\%$ 数据,$N \leq 100$,$K \leq 3$。对于全部数据,$N \leq 1000$,$K \leq 100$,单词长度 $\leq 20$。