#include #include #include #define MAX_SLOV 100000 typedef struct { char *sl; int delka; double cena_zlomu; /* Optimální cena řešení pro část textu před tímto slovem, jestliže před ním provedeme zlom. */ int predchozi_zlom; /* Předchozí zlom pro tuto optimální cenu. */ int zlomit; /* Pomocná proměnná pro výpis řešení. */ } slovo; static slovo text[MAX_SLOV]; static int pocet_slov; /* Vypíše řešení s optimální chybou takové, že poslední zlom se provede před slovem číslo POSLEDNI_ZLOM. */ static void vypis(int posledni_zlom) { int z = posledni_zlom, i; const char *sep = ""; while (z > 0) { text[z].zlomit = 1; z = text[z].predchozi_zlom; } for (i = 0; i < pocet_slov; i++) { if (text[i].zlomit) sep = "\n"; printf("%s%s", sep, text[i].sl); sep = " "; } printf("\n"); } /* Vrátí chybu za řádek obsahující celkem ZNAKU znaků, z nichž MEZER jsou mezery. */ static double chyba_radku(int znaku, int mezer) { double delka_mezery = (60.0 - znaku + mezer) / mezer; double chyba_mezery = delka_mezery - 1; return mezer * chyba_mezery * chyba_mezery; } /* Určí nejmenší chybu za délky mezer v části textu skládající se z prvních PRED slov textu (poslední řádek se nechová speciálně). */ static void nejmensi_chyba(int pred) { int znaku = text[pred - 1].delka; int mezer = 0; double nejlepsi_cena = INFINITY, akt_cena; int nejlepsi_zlom = -1, apred; for (apred = pred - 2; apred >= 0; apred--) { znaku += 1 + text[apred].delka; if (znaku > 60) break; mezer++; akt_cena = text[apred].cena_zlomu + chyba_radku(znaku, mezer); if (akt_cena < nejlepsi_cena) { nejlepsi_cena = akt_cena; nejlepsi_zlom = apred; } } text[pred].cena_zlomu = nejlepsi_cena; text[pred].predchozi_zlom = nejlepsi_zlom; } int main(void) { char buf[100]; int i, posledni, nejlepsi_zlom; double nejlepsi_cena; while (scanf("%s", buf) == 1) { text[pocet_slov].sl = strdup(buf); text[pocet_slov].delka = strlen(buf); pocet_slov++; } /* Určeme optimální chybu pro všechny prefixy textu. */ text[0].cena_zlomu = 0; text[1].cena_zlomu = INFINITY; for (i = 2; i < pocet_slov; i++) nejmensi_chyba(i); /* Vyzkoušejme všechy možnosti pro poslední řádek. */ nejlepsi_cena = text[pocet_slov - 1].cena_zlomu; nejlepsi_zlom = pocet_slov - 1; posledni = text[pocet_slov - 1].delka; for (i = pocet_slov - 2; i >= 0; i--) { posledni += 1 + text[i].delka; if (posledni > 60) break; if (text[i].cena_zlomu < nejlepsi_cena) { nejlepsi_cena = text[i].cena_zlomu; nejlepsi_zlom = i; } } vypis(nejlepsi_zlom); return 0; }