#sBXDPlydlt50x5B01. 诗人小G

诗人小G

好的,这是整理好的完整题面,附样例解释,格式规范:


题目描述

小 G 是一位诗人,经常作诗自娱自乐。但他一直被诗的排版问题所困扰。

一首诗包含 NN 个句子,句子顺序固定,且一个句子不能跨行放置。
对于连续的若干个句子,可以用空格隔开放在同一行(一行可以放任意多个句子,但不能改变句子顺序)。

小 G 定义了行标准长度 LL
排版后,每行的实际长度为该行所有句子的长度之和加上句子间的空格(每两个相邻句子间有一个空格)。
如果某行的实际长度为 lenlen,则该行的不协调度为 lenLP|len - L|^PPP 为给定的正整数指数)。
整个排版的不协调度为所有行不协调度的总和

请你对给定的诗进行排版,使得不协调度最小。

注意

  • 一行中相邻句子间有 1 个空格。
  • 行末不能有空格。
  • 句子的内容为可打印 ASCII 字符(码值 33~127,不含 '-')。

输入格式

第一行一个整数 TT,表示诗的数量。
每组数据格式如下:

  • 第一行三个整数 N,L,PN, L, P
  • 接下来 NN 行,每行一个句子。

输出格式

对于每组数据:

  • 若最小不协调度 >1018> 10^{18},输出 Too hard to arrange
  • 否则,先输出最小不协调度,然后在接下来的若干行输出排版方案(相邻句子间用空格隔开)。
    如果有多个最优方案,输出任意一个均可(本题有 special judge)。

每组数据输出结束后,输出一行 --------------------(20 个减号)。


数据范围

共有 10 个测试点,整体范围如下:

测试点 TT NN LL PP
1 ≤10 ≤18 ≤100 ≤5
2,3 ≤2000 ≤60000 ≤10
4,5 ≤5 ≤10⁵ ≤200
6,7 ≤3×10⁶ 2
8~10 ≤10

所有句子长度不超过 30,且 P1P \ge 1


输入样例

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
--------------------

样例解释

第一组数据

N=4,L=9,P=3N=4, L=9, P=3
句子长度(不含换行):

  1. brysj, 长度 6
  2. hhrhl. 长度 6
  3. yqqlm, 长度 6
  4. gsycl. 长度 6

若每句单独一行,则每行实际长度 len=6len = 6
每行不协调度 693=27|6-9|^3 = 27,四行共 27×4=10827\times 4 = 108
若两两句合并,比如第一行长度 6+1+6=136+1+6=13,不协调度更大。
因此最优就是每句一行,输出不协调度 108。


第二组数据

N=4,L=9,P=2N=4, L=9, P=2
最优方案是前两句一行,后两句一行:

  • 第一行:brysj, hhrhl. 长度 6+1+6=136+1+6=13,不协调度 (139)2=16(13-9)^2=16
  • 第二行:yqqlm, gsycl. 长度 6+1+6=136+1+6=13,不协调度 1616
    总不协调度 16+16=3216+16=32

输出 32 并给出对应排版。


第三组数据

N=1,L=1005,P=6N=1, L=1005, P=6
句子 poet 长度 4,若放一行,实际长度 4,不协调度 410056=10016|4-1005|^6 = 1001^6
10016>10181001^6 > 10^{18},所以输出 Too hard to arrange


第四组数据

N=1,L=1004,P=6N=1, L=1004, P=6
句子 poet 长度 4,不协调度 10006=10181000^6 = 10^{18},恰等于 101810^{18},未超过,所以输出 101810^{18} 并输出该句。