9596. Текстовый процессор

Бесси работает над эссе для урока письма. Поскольку её почерк оставляет желать лучшего, она решает набрать эссе в текстовом процессоре.

Эссе состоит из n слов, разделённых одиночными пробелами. Длина каждого слова составляет от 1 до 15 символов включительно; слова содержат только строчные и заглавные латинские буквы. Согласно инструкции к заданию, эссе должно быть отформатировано строго определённым образом: каждая строка должна содержать не более k символов, не считая пробелов. К счастью, текстовый процессор Бесси способен выполнять это требование следующим образом:

· Если при добавлении очередного слова оно помещается в текущую строку, то это слово дописывается в неё.

· В противном случае слово переносится на следующую строку, и заполнение продолжается уже в ней.

Разумеется, любые два соседних слова в одной строке должны быть разделены ровно одним пробелом. В конце строк пробелы недопустимы.

К несчастью, текстовый процессор Бесси только что сломался. Помогите ей отформатировать эссе в соответствии с описанными выше правилами.

Вход. Первая строка содержит два целых числа n (1 ≤ n ≤ 100) и k (1 ≤ k ≤ 80).  Во второй строке записаны n слов. Ни одно слово не превосходит k символов – максимального допустимого числа символов в одной строке.

Выход. Выведите эссе Бесси, оформленное надлежащим образом.

Пример входа	Пример выхода
10 7 hello my name is Bessie and this is my essay	hello my name is Bessie and this is my essay

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Последовательно читаем входные слова. Очередное слово выводим в текущей строке, если суммарная длина выводимых в строке слов не превышает k. Если при добавлении слова длина строки становится больше k, то это слово выводим на новой строке.

Реализация алгоритма

Входные слова читаем в массив s.

char s[100];

Читаем входные данные.

scanf("%d %d", &n, &k);

Переменная ptr хранит текущую длину выводимой строки.

ptr = 0;

Последовательно читаем n слов.

while (n--)

{

Читаем очередное слово s и находим его длину len.

scanf("%s", s);

len = strlen(s);

Если ptr + len ≤ k, то слово s можно вывести в текущей строке. Длина выводимой строки не превысит k символов.

if (ptr + len <= k)

{

ptr += len;

printf("%s ", s);

}

Иначе слово s следует вывести в новой строке. Длину ptr новой строки положим равной len.

else

{

ptr = len;

printf("\n%s ", s);

}

}

Реализация алгоритма – string

Читаем входные данные.

cin >> n >> k;

Переменная ptr хранит текущую длину выводимой строки.

ptr = 0;

Последовательно читаем n слов.

while (n--)

{

Читаем очередное слово s и находим его длину len.

cin >> s;

len = s.size();

Если ptr + len ≤ k, то слово s можно вывести в текущей строке. Длина выводимой строки не превысит k символов.

if (ptr + len <= k)

{

ptr += len;

cout << s << " ";

}

Иначе слово s следует вывести в новой строке. Длину ptr новой строки положим равной len.

else

{

ptr = len;

cout << endl << s << " ";

}

}

Python реализация

Читаем входные данные.

n, k = map(int, input().split())

s = input().split()

Переменная ptr хранит текущую длину выводимой строки.

ptr = 0

Перебираем слова w в списке s.

for w in s:

Вычисляем длину слова w.

lw = len(w)

Если ptr + lw ≤ k, то слово w можно вывести в текущей строке. Длина выводимой строки не превысит k символов.

if ptr + lw <= k:

ptr += lw

print(w, end=" ")

Иначе слово w следует вывести в новой строке. Длину ptr новой строки положим равной lw.

else:

ptr = lw

print()

print(w, end=" ")