#sBXDPlydlt50x5B01. 诗人小G
诗人小G
好的,这是整理好的完整题面,附样例解释,格式规范:
题目描述
小 G 是一位诗人,经常作诗自娱自乐。但他一直被诗的排版问题所困扰。
一首诗包含 个句子,句子顺序固定,且一个句子不能跨行放置。
对于连续的若干个句子,可以用空格隔开放在同一行(一行可以放任意多个句子,但不能改变句子顺序)。
小 G 定义了行标准长度 。
排版后,每行的实际长度为该行所有句子的长度之和加上句子间的空格(每两个相邻句子间有一个空格)。
如果某行的实际长度为 ,则该行的不协调度为 ( 为给定的正整数指数)。
整个排版的不协调度为所有行不协调度的总和。
请你对给定的诗进行排版,使得不协调度最小。
注意:
- 一行中相邻句子间有 1 个空格。
- 行末不能有空格。
- 句子的内容为可打印 ASCII 字符(码值 33~127,不含
'-')。
输入格式
第一行一个整数 ,表示诗的数量。
每组数据格式如下:
- 第一行三个整数 。
- 接下来 行,每行一个句子。
输出格式
对于每组数据:
- 若最小不协调度 ,输出
Too hard to arrange。 - 否则,先输出最小不协调度,然后在接下来的若干行输出排版方案(相邻句子间用空格隔开)。
如果有多个最优方案,输出任意一个均可(本题有 special judge)。
每组数据输出结束后,输出一行 --------------------(20 个减号)。
数据范围
共有 10 个测试点,整体范围如下:
| 测试点 | ||||
|---|---|---|---|---|
| 1 | ≤10 | ≤18 | ≤100 | ≤5 |
| 2,3 | ≤2000 | ≤60000 | ≤10 | |
| 4,5 | ≤5 | ≤10⁵ | ≤200 | |
| 6,7 | ≤3×10⁶ | 2 | ||
| 8~10 | ≤10 |
所有句子长度不超过 30,且 。
输入样例
4
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet
输出样例
108
brysj,
hhrhl.
yqqlm,
gsycl.
--------------------
32
brysj, hhrhl.
yqqlm, gsycl.
--------------------
Too hard to arrange
--------------------
1000000000000000000
poet
--------------------
样例解释
第一组数据
句子长度(不含换行):
brysj,长度 6hhrhl.长度 6yqqlm,长度 6gsycl.长度 6
若每句单独一行,则每行实际长度 ,
每行不协调度 ,四行共 。
若两两句合并,比如第一行长度 ,不协调度更大。
因此最优就是每句一行,输出不协调度 108。
第二组数据
最优方案是前两句一行,后两句一行:
- 第一行:
brysj, hhrhl.长度 ,不协调度 - 第二行:
yqqlm, gsycl.长度 ,不协调度
总不协调度 。
输出 32 并给出对应排版。
第三组数据
句子 poet 长度 4,若放一行,实际长度 4,不协调度 。
,所以输出 Too hard to arrange。
第四组数据
句子 poet 长度 4,不协调度 ,恰等于 ,未超过,所以输出 并输出该句。