National Olympiad in Informatics, China, 2009

Day 1, Problem 2 - Little G the Poet

Little G is an outstanding poet who frequently writes poetry for his own pleasure and entertainment. However, one issue has constantly been troubling him, and that is the issue of typesetting his poems.

A poem contains many sentences. For some consecutive short sentences, he can separate them using spaces and place them onto one line. Note that there is no limit to the number of sentences that he can place on one line. Little G defined for each poem a standard line length (the length of a line is the total number of characters on the line), and wishes for each line's length after typesetting to not be far from its standard line length. Clearly when typesetting, one should not change the order of the original sentences, and little G does not allow a line to be split up between two or more lines. Satisfying these two conditions, little G would like to define for each line a level of disproportion, being the absolute value of the difference between the actual length of the line and its standard line length, raised to the P-th power. The overall level of disproportion for a typeset is the sum of the levels of disproportion for all of its lines.

Little G just wrote some more poems, and now invites you to typeset them, making their line lengths as proportionate as possible (i.e. minimizing the level of disproportion), finally providing him with the result.

Input Format

Each test case will contain multiple datasets. The first line of input contains the integer T, representing the number of datasets. There will be T datasets to follow.

Each dataset will describe a poem. The first line of each dataset will contain three space-separated integers N, L, and P. Here, N is the total number of sentences in the poem, L is the standard length for the poem's lines, and P is the power used to calculate the level of disproportion. In the following N lines of the dataset, each line will contain one sentence made up of alphabetical letters, numbers, punctuation, and other characters (ASCII 33~127, but excluding '-').

Output Format

For each dataset, if the minimum level of disproportion doesn't exceed 10¹⁸, then you should output a single integer on one line representing the level of disproportion, followed by some number of lines containing the poem itself. Note: Adjacent sentences on the same line must be separated by a single space. If there are multiple different typesets that all produce the minimum level of disproportion, you may output any one of them. Otherwise if the minimum level of disproportion exceeds 10¹⁸, then output "Too hard to arrange" (without quotes). After the output of each dataset, output a line containing "--------------------" (without quotes), a total of 20 '-' characters (ASCII 45). Please avoid printing excess lines or spaces.

Sample Input

4
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet

Sample Output

108
brysj,
hhrhl.
yqqlm,
gsycl.
--------------------
32
brysj, hhrhl.
yqqlm, gsycl.
--------------------
Too hard to arrange
--------------------
1000000000000000000
poet
--------------------

Explanation

The first two datasets in the sample input each have standard line lengths of 6. The last two datasets each have standard line lengths of 4. The space that separates adjacent sentences is counted towards the total length of the line (refer to the second dataset in the sample). There are no trailing spaces in any line.

Scoring

For each test case, if your program produces the correct minimal level of disproportion for all of the datasets, then you will score 70% of points for the test case. Under this circumstance, if the typesetting scheme for all of the dataset in the test case matches the levels of disproportion that you have outputted, then you will score the remaining 30% of points. Note: formatting errors in your output can result in no points for the test case.

Constraints

There are 10 total test cases, their constraints satisfy:

In all of the test cases, the length of sentences will never exceed 30.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 5.00s
Memory Limit: 256M
Added: Aug 04, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)