Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "stdio.h"
#include "stdlib.h"
char text_buffer[20010];
char * end_of_buffer;
int word_count;
int word_length[10010];
char *(word_pointer[10010]);
int desired_width;
int  badness[10010], start_next_line[10010],length[10010];
int calculate(int n) {
  if (start_next_line[n] == -1) {
    int best_badness, best_start_next_line, best_length;
    int act_badness,  act_start_next_line,  act_length;
    int w; 
    best_badness = 0x7FFFFFFF; 
    act_length = 0;
    act_start_next_line = n;
    w = 0;
   while (1) {
      act_start_next_line++;
      w++;
      if (act_start_next_line > word_count) break;
      act_length += word_length[act_start_next_line - 1];
      if (act_length + w - 1 > desired_width)
	break;
      if (w == 1)
	if (act_length == desired_width) act_badness = 0;
	else act_badness = 500;
      else {
	int spaces_per_gap = (desired_width - act_length) / (w - 1);
	int big_gaps = (desired_width - act_length) % (w - 1);
	act_badness =
	  (spaces_per_gap - 1) * (spaces_per_gap - 1) * (w - 1 - big_gaps)
	  + spaces_per_gap * spaces_per_gap * big_gaps;}
      act_badness += calculate(act_start_next_line);
      if (act_badness <= best_badness) {
	best_badness = act_badness;
	best_start_next_line = act_start_next_line;
	best_length = act_length;}
    }
    start_next_line[n] = best_start_next_line;
    badness[n] = best_badness;
    length[n] = best_length;
  }

  return badness[n];
}

void output_paragraph() {
  int n, next_n;
  int i, j, remainder, gap_size;
  n = 0;
  while (n < word_count) {
    remainder = desired_width - length[n];
    next_n = start_next_line[n];
    for (i = n; i < next_n; i++) {
      if (i > n) {
	gap_size = remainder / (next_n - i);
	for (j = 0; j < gap_size; j++)
	  printf(" ");
	remainder -= gap_size;
      }
      printf("%s", word_pointer[i]);
    }
    printf("\n");
    n = next_n;
  }
}

int main() {
  FILE * f = stdin;
  int new_lines;
  int c;
  while (1) {
    fscanf(f, "%d", &desired_width);
    if (desired_width == 0)
      break;
    
    end_of_buffer = text_buffer;
    word_count = 0;

    while (1) {
      fscanf(f, " %s", end_of_buffer);
      word_length[word_count] = strlen(end_of_buffer);
      word_pointer[word_count] = end_of_buffer;
      start_next_line[word_count] = -1;
      word_count++;
      end_of_buffer += strlen(end_of_buffer) + 1;
      new_lines = 0;
      do {
	c = getc(f);
	if (c == '\n') new_lines++;
      } while (c == ' ' || c == '\n');
      ungetc(c, f);
      if (new_lines > 1) break;
    } 
    start_next_line[word_count] = word_count;
    badness[word_count] = 0;
    calculate(0);
    output_paragraph();
    printf("\n");
 }
  fclose(f);
  return 0;
}