eolymp
bolt
Try our new interface for solving problems
Məsələlər

Text Justi?cation

Text Justi?cation

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

You are hired by the ∀ℑ¶ℵΞρ, an extraterrestrial intelligence, as a programmer of their typesetting system. Your task today is to design an algorithm for text justification.

Text justification is to equalize the line widths as much as possible by inserting line breaks at appropriate positions, given a word sequence called a paragraph and the width of the paper. Since you have not developed an automatic hyphenation algorithm yet, you cannot break a line in the middle of a word. And since their language does not put spaces between words, you do not need to consider about spacing.

To measure how well the text is justified in one configuration (i.e., a set of lines generated by inserting line breaks to a paragraph), you have defined its cost as follows:

  • The total cost of a paragraph is the sum of the cost of each line.

  • The cost for the last line is defined as max(0, s − w).

  • The cost for other lines are given by |s − w|.

where s is the sum of the widths of the words in the line, and w is the width of the paper.

Please design the algorithm which takes a paragraph and calculates the configuration of the minimum cost.

Giriş verilənləri

The input consists of multiple test cases.

The first line of each test case contains two positive integers n and w (0n1000 and 0w1000000). n is the length of paragraph and w is the width of the used paper. Each of the following n lines contains one positive integer a_i which indicates the width of the i-th word in the paragraph. Here it is guaranteed that 0a_iw.

The input terminates with the line containing two zeros. This is not a part of any test case and should not be processed.

Çıxış verilənləri

For each test case, print the case number and the minimum cost for the paragraph.

Mənbə Winter Camp for ACM-ICPC World Finals 2008, JAG, Practice Contest II