Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

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

Гвоздики

Динамическое программирование: один параметр

На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так,  чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
 
Входные данные
В первой строке входного файла записано число N - количество гвоздиков (2 <= N <= 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, 
не превосходящие 10000).
 
Выходные данные
В выходной файл нужно вывести единственное число - минимальную суммарную длину всех ниточек.
 
 
Пример входного файла
5
4 10 0 12 2
 
Пример выходного файла
6
 

Камни

Динамическое программирование: один параметр

На столе лежат N камней. За ход игрок может взять
 
1 или 2 камня, если N делится на 3;
1 или 3, если N при делении на 3 дает остаток один;
1, 2 или 3, если N при делении на 3 дает остаток два.
Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.
 
Входные данные
Вводится целое число 0 < N <= 100.
 
Выходные данные
Выведите 1 или 2 – номер игрока, который выиграет при правильной игре.

Ввод Вывод
1 1
3 2