Задача NewDomino

Бизнесмен Олигархов открыл фабрику по производству наборов для игры "НОВОЕ ДОМИНО". В новом домино каждая половинка камня имеет N точек. В продажу поступали наборы по К камней, некоторые из которых могли быть одинаковыми. Игроки делят камни поровну и выкладывают их на стол в цепочку друг за другом, например [7:4] [4:17] [17:45]... Игра заканчиватся,когда все камни лежат на столе. Механизм определения победителя был весьма необычен, это обеспечило бошльшое количество продаж.... Но в скорм времени у Олигархова начались непрятности. Оказывется, не каждый набор годится для игры. Некотороые никак не удавалось сложить в цепочку... Помогите управлению по защите прав потребителей проверить, из каких наборов получается цепочка, а из каких - нет.

Технические условия. Программа читает с клавиатуры число K - количество камней в наборе, а далее К пар чисел, каждое из которых - количество точек N на половинке К-того камня. Все числа разделены пробелами. 5<=K<=1000, 1<=N<=50 Программа выводит на экран -1, если играть с этим набором камней невозможно, в противном случае - К пар чисел, каждое из которых - количество точек на половинке камня. Для любого i (1<=i<=K-1) второе число пары должно совпадать с первым числом пары i+1. Кроме того, второе число пары К должно равняться первому числу пары 1. Если камни могут быть расположены в разной последовательности, подойдет любая.

Примеры.

Ввод> 5 1 2 2 3 3 4 4 5 5 6
Вывод> -1

Ввод> 5 2 1 2 2 3 4 3 1 2 4
Вывод> 2 1 1 3 3 4 4 2 2 2

Задача DSP2

Бревна нужно распилить поперек на куски нужной длины. Стоимость распиловки зависит от начальной длинны бревна. Например, бревно длиной 10 метров нужно распилить на расстоянии 2, 4 и 7 м, считая от одного конца. Это можно сделать несколькими способами. Можно распилить на отметке 2 м,потом - 4 и потом 7 м, это приведет к стоимости 10+8+6=24 ( сначала бревно имело длину 10 м, после первого распила - 8 м, после второго - 6 м). Однако можно пилить и иначе - сначала на отметке 4 м,потом - 2 и затем 7 м. Это приведет к стоимости 10+4+6=20, что, естественно, дешевле. Напишите программу, которая определяет минимальную стоимость распиловки для любого бревна указанной длины.

Технические условия. Программа считывает с клавиатуры целое положительное число L<1000 - начальную длину бревна, далее- число N<50 - количество распилов, которые нужно сделать, далее - N целых положительных чисел Cі(0<Ci<L), задающие места, в которых нужно сделать распилы в строго возрастающем порядке. Программа выводит на экран минимальную стоимость распиловки данного бревна.

Пример.

Ввод> 100 3 25 50 75
Вывод> 200

Задача Army

Военные - серьезные люди. Однажды прапорщик Пупкин обнаружил, что солдаты в строю расположены вовсе не по росту. Вы можете представить, какой крик он поднял, и как досталось сержанту Васину, который был ответственным за построение. Чтобы не быть разжалованным в рядовые, сержант решил показать прапорщику, что было не так уж много ошибок в построении. Сержант поручил рядовому (до призыва - участнику NetOI) Глюкову посчитать, сколькими способами можно выбрать К + 1 солдат, стоящих по росту. Не обязательно, чтобы они стояли подряд. Сержант видит, что ошибок предостаточно, поэтому заверил Глюкова, что это количество не будет превосходить 8•10¹⁸. Сержант думает, что это число будет впечатляющим, и прапорщик простит ему его ошибку.

Технические условия: Программа считывет с клавиатуры число N — количество солдат в строю (1 <= N <= 100 000) и число К (0 <= К <= 10), далее N чисел - номер, который бы имел солдат в строю, если бы все стояли на своем месте. Все числа разделены пробелами. У каждого солдата разный рост, поэтому есть только единственный способ правильно расставить солдат. Программа выводит на экран единственное число — ответ на поставленную задачу.

Пример.

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

Задача Lake

В тридевятом царстве, в тридесятом государстве жил да был Иван – крестьянский сын. Приснился ему как-то сон. Будто бы встретил Иван добрую волшебницу, и молвила она: «Жениться тебе пора, Иванушка. Садись на коня и езжай за тридевять земель к избушке на курьих ножках. Только смотри, в воду не заходи. И если найдешь кратчайший путь к избушке, будет тебе женой Василиса Прекрасная». Проснулся Иван, а у него в руках карта тридевятого царства, тридесятого государства. Все водоемы в государстве – озера, каждое озеро имеет форму правильного многоугольника. Никакие два озера не имеют общих точек. Помогите Ивану добраться до избушки.

Технические условия: Сначала вы вводите с клавиатуры координаты дома Ивана и координаты избушки. Затем Вы вводите количество озер (не более 10). Затем для каждого озера Вы вводите количество сторон (от 3 до 20), координаты центра и координаты одной вершины. Все числа разделены пробелом. Все координаты – вещественные числа, не превосходящие по модулю 1000000. Вы выводите на экран длину кратчайшего пути.

Пример.

Ввод> -20 10 -19 -6 2 6 -30 -12 -25 -12 4 -20.5 2.5 -16 7
Вывод> 19.0000000

Комментарий. Два озера: шестиугольное и квадратное. Искомый путь проходит по берегу квадратного озера.

Задача Message

Герой задачи blamblam, офицер по особым поручениям, направил ССС (срочное секретное сообщение) в Генеральный штаб. В блямблямской армии ССС передаются следующим образом: посылают два пакета, каждый содержит некоторый текст, ССС – текст максимальной длины, входящий целиком в оба пакета (то есть в обоих пакетах есть фрагмент, идентичный ССС). Помогите начальнику штаба прочитать ССС.

Технические условия: Вы вводите с клавиатуры в первой строке содержимое первого пакета, во второй строке содержимое второго пакета. Длина текста в пакете не превосходит 10000 символов. Вы выводите на экран максимально возможную длину ССС.

Пример.

Ввод>
moloko
doloto
Вывод> 3

Г.Кравец, Г.Непомнящий, К.Симонов, Ю.Пасихов