Задача A. Разбиение абзаца на строки
Условие
Абзац текста состоит из
n слов длиной
l1,
l2, ...,
ln (длина слова - число символов
в нем). Требуется оптимальным образом разбить его на строки длиной не более
M символов. Оптимальность при этом определяется так: посчитаем число
"лишних" пробелов в каждой строке и сложим кубы этих чисел для всех строк,
кроме последней. Чем больше эта сумма (назовем ее
оценочной суммой),
тем хуже абзац.
Формат входного файла
В первой строке находятся числа
n и
M. Далее следует
n чисел
li.
Формат выходного файла
Выходной файл должен содержать единственное число - значение оценочной суммы
абзаца при оптимальном разбиении на строки.
Ограничения
1 <=
n <= 10000,
1 <=
M <= 100000,
1 <=
li <=
M
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
4 6
2 1 2 5
|
72
|
Задача B. Путешествие из Петербурга в Москву
Условие
Профессор едет по шоссе из Петербурга в Москву, имея при себе карту с
указанием всех
N стоящих на шоссе бензоколонок и расстояний
Di до них от Петербурга. Известно расстояние
S,
которое может проехать машина с полностью заправленным
баком.
Требуется выяснить, на каких бензоколонках нужно заправляться, чтобы
количество заправок было минимально. В начале пути бак полон.
Расстояние от Петербурга до Москвы равно
L.
Формат входного файла
Во входном файле сначала указаны числа
L,
S,
N,
после чего перечислено
N чисел
Di.
Формат выходного файла
Выходной файл должен содержать единственное число - минимальное количество
заправок. Если добраться из Петербурга в Москву невозможно, следует вывести
число -1.
Ограничения
0 <= L <= 10^9
0 <= S <= 10^9
0 <= N <= 500000
0 <= Di <= L
Все числа целые.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
100 60 2
50 30
|
1
|
| 2 |
100 30 3
60 20 50
|
-1
|
Задача C. Топологическая сортировка
Условие
Дан ориентированный ациклический граф. Требуется выполнить топологическую
сортировку его вершин. При этом сначала требуется вывести группу вершин, в которые
не входит ни одного ребра, затем вершины, в которые входят только
рёбра из вершин первой группы, затем те, в тоторые входят только рёбра из вершин
первой и второй групп и т.д. В каждой группе
номера вершин должны быть отсортированы по возрастанию.
Формат входного файла
Сначала указывается количество вершин
V и количество ребер
E.
Далее перечисляется
E пар вершин
(
vi,
vj), задающих ребра. Никакая пара
вершин не встречается дважды.
Формат выходного файла
Необходимо перечислить
V вершин в описанном порядке.
Ограничения
1 <=
V <= 1000000, 0 <=
E <= 1000000
1 <=
vi <=
V
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
6 5
2 3
4 6
3 1
5 1
2 5
|
2 4 3 5 6 1
|
