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 + len ≤ k, то слово w можно вывести в текущей строке. Длина выводимой строки не превысит k символов.

if ptr + lw <= k:

ptr += lw

print(w, end=" ")

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

else:

ptr = lw

print()

print(w, end=" ")