Rapasoft.eu

//-----------------------------------------------------------
// Pretty text / paragraph formatting algorithm in O(m*n) 
// where m is line length and n is total count of words.
// This algorithm uses dynamic programming. 
//
// coding: Pavol Rajzák
// special thanks: Ján Jerguš, Maroš Andrejko, Marek Daňko
// happy birthday LM
//-----------------------------------------------------------

import java.util.*;

public class TextFormatting {

    public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    for (int i = 0; i < n; i++) {
        int M = s.nextInt();
        String p = s.next();
        String text = s.nextLine();
        format(M, p+text);
        System.out.println();
//        Testovacie vzorky pre rychle overenie (treba zakomentovat predchadzajucu cast a odkomentovat tuto)
//        int M = 30;
//        String text = "This text is allowed to be wider. To fill multiple lines, we need lots of words.";
//        format(M, text);
//        System.out.println();
//        M = 13;
//        text = "Sometimes the solution requires more thought.";
//        format(M, text);
//        System.out.println();
//        M = 11;
//        text = "The short words are the best. And the old words, when short, are best of all. (Churchill)";
//        format(M, text);
//        System.out.println();
    }
    }

    public static void format(int M, String word){
    //Priprava slov, urcenie poctu slov, zapamätanie si povodneho M
    String[] words = word.split(" "); 
    int cntWords = words.length;
    int MP = M;
    
    //jedna tabulka sluzi na pamätanie docasnych vysledkov, druha
    //uchovava informacie pre neskorsie vybudovanie cesty
    int[] matrix = new int[cntWords+1];
    int[] rebuild = new int[cntWords+1];
    
    //Nastavenie pola hodnot, na maximalne hodnoty
    for (int i = 0; i < matrix.length; i++) {
        matrix[i] = Integer.MAX_VALUE;
    }
    
    //priznak urcujuci, ci spracuvavame posledny riadok    
    boolean last = true;
    
    //cyklus zacina pri poslednom slove
    for(int i = cntWords; i > 0; i--){
        
        //Ak spracuvava posledny riadok, t.j. je mozne umiestnit slovo
        //do posledneho riadku, nastavi hodnotu v matici na 0 pre dane
        //slovo. To znamena, ze skaredost spojena s tymto slovom bude
        //nulova, pretoze je v poslednom riadku
        if(last){
        if(M - words[i-1].length() >= 0){
            matrix[i] = 0;
            M = M - words[i-1].length() - 1;
        } else {
            last = false;
            M = MP;
            i++;
        }
        } 
        //Ak presiel na spracovanie ostatnych riadkov, zistuje, aka je
        //minimalna skaredost pre dane j-te slovo, ak zacina v danom 
        //riadku. Potom sa snazi pridavat dalsie slova, ak sa zmestia
        //do daneho riadku a zistuje, ci skaredost po pridani daneho 
        //slova nebude mensia ako pred tym. Ak ano, tak vymeni hodnoty
        //a do tabulky rebuild prepise povodnu hodnotu, ktora bude
        //znacit az kam sa moze z daneho slova dostat.
        else {
        int j = i;
        rebuild[i] = 1;
        while(true){
            if(M - words[j-1].length() >= 0){
            M = M - words[j-1].length() - 1;
            if(matrix[i]<(matrix[j+1] + (int)Math.pow(M+1,2))){
            } else {
                matrix[i] = matrix[j+1] + (int)Math.pow(M+1,2);
                rebuild[i] = j;
            }
            j++;
            } else {
            break;
            }
        }
        M = MP;
        }
    }
    
    //Postupne pride az ku rieseniu, ktore sa nachadza v prvom poli tabulky
    System.out.println(matrix[1]);
    
    //Samotny vypis bude fungovat tak, ze si zisti, na ktore slovo sa
    //vie dostat z aktualneho slova. Napr. ak sa vie dostat z prveho 
    //slova na sieste, tak vypise prvych sest slov do jedneho riadku,
    //prejde na dalsi riadok a pozrie sa kam sa az moze dostat zo
    //siesteho slova. Bud tam bude mat hodnotu kam sa az moze dostat
    //alebo nulu, co znaci, ze moze vypisovat slova az do konca.
    int next = rebuild[1];
    for (int i = 0; i < words.length; i++) {
        if(i
        System.out.print(words[i]+" ");
        } else {
        System.out.println();
        System.out.print(words[i]+" ");
        next=rebuild[next+1];
        if(next==0)
            next=cntWords;
        }
    }
    
    }

}