Суть репозитория заключается в решении олимпиадных задач по программированию двумя способами: медленным и дианмическим программированием. Условия задач:
- Гвоздики:
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
Входные данные: В первой строке входного файла INPUT.TXT записано число N - количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
Выходные данные: В выходной файл OUTPUT.TXT нужно вывести единственное число - минимальную суммарную длину всех ниточек.
- Минимальный путь в таблице:
В прямоугольной таблице N×M (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути). Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.
Входные данные: Во входном файле INPUT.TXT задано два числа N и M - размеры таблицы (1 ≤ N ≤ 20, 1 ≤ M ≤ 20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).
Выходные данные: В выходной файл OUTPUT.TXT выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.
- Садовник-художник:
Садовник посадил N деревьев в один ряд. После посадки деревьев садовнику нужно их покрасить. В его распоряжении есть краска трех цветов: белая, синяя и оранжевая. Сколько способов покраски деревьев есть у него, если никакие два соседних дерева нельзя красить в одинаковый цвет?
Входные данные: В единственной строке входного файла INPUT.TXT записано одно натуральное число - количество деревьев N (1 ≤ N ≤ 50).
Выходные данные: В единственную строку выходного файла OUTPUT.TXT нужно вывести одно число - количество способов покраски.
- Магазин:
На расстоянии N шагов от магазина стоит человек. Каждую минуту он выбирает, куда сделать шаг: к магазину или в противоположном направлении. Требуется написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов и оказавшись в магазине только после выполнения последнего шага.
Входные данные: Входной файл INPUT.TXT содержит два числа N и K, записанные через пробел. Известно, что 1 ≤ N ≤ K ≤ 37.
Выходные данные: Выходной файл OUTPUT.TXT должен содержать одно число – количество способов попадания в магазин.