2

Условие задачи:

Дано натуральное число K и строка текста, состоящая из слов, отделенных пробелами. Требуется разбить входную строку на строки длины K. В очередной строке должно быть выведено максимальное количество очередных слов входной строки, которые целиком помещаются в строку длины K (при условии, что слова разделены хотя бы одним пробелом). При этом, требуется каждую выходную строку отформатировать следующим образом. Необходимо, чтобы среднеквадратическое отклонение длин пробельных серий в каждой такой строке было минимальным (пробельная серия - непрерывная последовательность пробелов между двумя словами). То есть, если в строке есть n пробельных серий длины li и среднее арифметическое этих длин равно L, то среднее арифметическое величин (li - L)^2 должно быть минимально для результирующей строки.

Если в строку входит больше одного слова, дополнять пробелами разрешается только промежутки между двумя словами. При возможности добавить пробел в несколько промежутков, выбирать следует тот промежуток, который расположен ближе всего к началу строки. Если же только одно очередное слово входной строки входит в очередную выходную строку, то необходимо вывести сначала это слово, а потом дополнить длину очередной выходной строки пробелами до K символов.

На стандартном потоке ввода в первой строке задано число K (K ≥ 1, K ≤ 10^6), во второй строке задана последовательность символов (строка) S, состоящая из пробелов и букв латинского алфавита, признак окончания которой - символ перевода строки. Известно, что длина строки S ≤ 10^6. Строка состоит из слов, разделенных пробельными символами (по одному пробелу между двумя словами). Строка начинается и кончается словами, либо является одним словом. В строке содержится по крайней мере одно слово. Известно, что любое слово входной последоватьности имеет длину не больше K.

На стандартный поток вывода напечатайте результат описанного выше преобразования. Каждую выходную строку следует завершать символом перевода строки '\n'.

Вот мое решение, язык C:

#include <stdio.h>
#include <string.h>

void print_line(int k, char w[1000002][k + 2], int l, int r) {
    int amount_w = r - l + 1;
    int w_len = 0;
    for (int i = l; i <= r; ++i)
        w_len += strlen(w[i]);
    int amount_sp = k - w_len;
    int curr_sum = 0;
    printf("%s", w[l]);
    for (int i = 0; i < amount_w - 1; ++i) {
        int x = (amount_sp - curr_sum) / (amount_w - 1 - i);
        if ((amount_sp - curr_sum) % (amount_w - 1 - i))
            ++x;
        curr_sum += x;
        for (int j = 0; j < x; ++j)
            printf(" ");
        printf("%s", w[l + i + 1]);
    }
    if (r == l) {
        for (int i = 0; i < amount_sp; ++i)
            printf(" ");
    }
    printf("\n");
}

int main(void) {
    int k;
    scanf("%d\n", &k);
    char s[1000002];
    fgets(s, 1000002, stdin);
    if (s[strlen(s) - 1] == '\n')
        s[strlen(s) - 1] = '\0';
    int amount = 0, curr = 0;
    char w[1000002][k + 2];
    for (int i = 0; i < strlen(s); ++i) {
        if (s[i] != ' ') {
            w[amount][curr++] = s[i];
        } else {
            w[amount++][curr] = '\0';
            curr = 0;
        }
    }
    ++amount;
    int len_curr = 0, l_curr = 0, r_curr = 0;
    while (l_curr < amount) {
        len_curr += strlen(w[l_curr]);
        r_curr = l_curr;
        while (r_curr < amount - 1) {
            int t = strlen(w[r_curr + 1]);
            if (len_curr + 1 + t > k) {
                break;
            }
            len_curr += 1 + t;
            ++r_curr;
        }
        if (r_curr == amount)
            --r_curr;
        print_line(k, w, l_curr, r_curr);
        l_curr = r_curr + 1;
        len_curr = 0;
    }
    return 0;
}

В функции main я сначала считываю число и строку, потом создаю массив слов. После в цикле нахожу, сколько слов помещается в очередную строку и передаю левую и правую границу в функцию print_line, которая печатает очередную строку, считая, сколько пробелов нужно между словами.

Мое решение проходит 10 тестов в системе, а потом происходит "Ошбика выполнения". Мне сказали, что это либо деление на 0, либо выход за границы массива. Но ни того, ни другого я у себя никак не могу найти.

Я пробовал менять размер массивов, увеличивая его, но это не дало никакого эффекта.

Мой друг, успешно решивший эту задачу немного по-другому, проверил результаты наших программ на множестве небольших тестов и не нашел в них ошибок.

7
  • Вы преднамеренно здесь: char w[1000002][k + 2]; используете VLA массив? Вы уверены, что при этом не сносите стек при определенных значениях k?
    – Vladimir
    17 ноя 2020 в 21:37
  • Не уверен. Видимо лучше не создавать такой массив слов, он получается слишком большой, должно быть, и не влезает в ограничения.
    – dg mishee
    17 ноя 2020 в 21:44
  • Если нужен большой массив, то лучше создайте его как динамический на куче. А так... Размер стека, если правильно помню, по умолчанию 2 Мб для 32-битной Windows и 8Мб для 64-битной. А у Вас там одна размерность в массиве примерно 1 Мб...
    – Vladimir
    17 ноя 2020 в 21:46
  • Вообще ограничение по памяти в этой задаче 64М стоит, по времени 1 с
    – dg mishee
    17 ноя 2020 в 21:56
  • Ну так это же, наверное, ограничение на суммарный объем памяти: и на стеке, и в куче. Не думаю, что они ради Вас будут специально выделять 64Мб именно для стека...
    – Vladimir
    17 ноя 2020 в 21:58

1 ответ 1

0

А зачем Вами все эти гигантские массивы?! (char w[1000002][k + 2]) Я эту задачу решал ещё на ЕС-1022 у которой вся память была 128 КБ (КИЛО байт!!!) Только там были условия маленько посложнее - надо было учитывать отступ в первой строке абзаца и т.н. "повисшие строки" - попадание последней строки абзаца на следующую страницу.

Ну а по сути. Единственный массив, который нужен для решения этой задачи - массив символов, длиной в одну строку документа. В вашем задании написано, что строка может быть длиной в миллион символов. По моему, это бред, но всё равно - выделить один мегабайт памяти не составляет проблемы.

А дальше алгоритм такой:

  1. Читаем последовательно слова из входного потока.
  2. Каждое введённое слово размещаем в выходной буфер с интервалом в один пробел.
  3. Если очередное введённое слово не помещается, запоминаем его и выполняем форматирование по правилам, которые Вы используете.
  4. После этого сбрасываем выходной буфер и помещаем в него запомненное слово.
  5. Возвращаемся к п. 1.

Форматирование тоже не требует никаких особых затрат памяти:

  1. Повторяем до тех пор, пока в выходном буфере есть пробелы справа
  2. Переходим на конец очередного слова и вставляем там пробел

При таком алгоритме правило распределения пробелов, которое установлено в Вашем задании, выполняется автоматически. Здесь не учитывается последняя строка абзаца, но у Вас этого нет.

1
  • Спасибо за ответ, решил в итоге примерно так же без массива
    – dg mishee
    18 ноя 2020 в 17:51

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.