Задача NewDomino
Бізнесмен Олігархів відкрив фабрику по виробництву наборів для гри "НОВЕ ДОМІНО". В новому доміно кожна половинка каменя має N точок. У продаж надходили набори по К каменів, деякі з яких могли бути однаковими. Гравці ділять камені порівну і викладають їх на стіл в ланцюг один за одним наприклад [7:4] [4:17] [17:45]... Гра закінчується, коли всі камені лежать на столі. Механізм визначення переможця був вельми незвичайний, це забезпечило велику кількість продажів... Але з часом у Олігархова почалися неприємності. Виявляється, що не кожен набір годиться для гри, деякі ніяк не вдавалося скласти в ланцюжок. Допоможіть управлінню по захисту прав споживачів перевірити, з яких наборів виходить ланцюжок, а з яких - ні.
Технічні умови. Програма читає з клавіатури число К - кількість каменів у наборі, а далі К пар чисел, кожне з яких - кількість точок N на половинці К-го каменя. Всі числа розділені пропусками. 5<=K<=1000, 1<=N<=50 Програма виводить на екран -1, якщо грати з цим набором каменів неможливо, інакше - К пар чисел, кожне з яких - кількість точок на половинці каменя. Для будь-якого і (1<=i<=K-1) друге число пари повинно співпадати з першим числом пари і+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 цілих додатних чисел, Ci(0<Ci<L), що задають місця, в яких потрібно зробити розпили в суворо зростаючому порядку. Програма виводить на екран мінімальну вартість розпилу даної колоди.
Приклад.
Введення> 100 3 25 50 75
Виведення> 200
Задача Army
Військові - серйозні люди. Одного разу прапорщик Пупкін виявив, що солдати в строю розміщені не по росту. Ви можете уявити, який крик він підняв, і як дісталось сержанту Васіну, який був відповідальним за шикування. Щоб не бути розжалуваним у рядові, сержант вирішив показати прапорщику, що було не так вже й багато помилок у шикуванні. Сержант доручив рядовому (до призову - учаснику NetOI) Глюкову порахувати, скількома способами можна вибрати К + 1 солдат, що стоять по росту. Не обов'язково, щоб вони стояли підряд. Сержант бачить, що помилок достатньо, тому запевнив Глюкова, що ця кількість не буде перевищувати 8•1018. Сержант вважає, що це число буде вражаючим, і прапорщик вибачить йому його помилку.
Технічні умови: Програма зчитує з клавіатури число N - кількість солдат у строю (1<= N<=100 000) і число К (0<=К<=10), далі N чисел - номер,який мав би солдат у строю, якби всі стояли на своїх місцях. Всі числа розділені пропусками. У кожного солдата різний зріст, тому є тільки єдиний спосіб вірно розставити солдат.
Програма виводить на екран єдине число - відповідь на поставлену задачу.
Приклад.
Введення> 3 2 1 2 3
Виведення> 1
Задача Lake
У тридев'ятому царстві, в тридесятій державі жив та був Іван – селянський син. Приснився йому якось сон. Нібито зустрів Іван добру чарівницю, і мовила вона: «Одружуватися тобі пора, Іванку. Сідай на коня і їдь за тридев'ять земель до хатинки на курячих ніжках. Тільки дивися, у воду не заходь. І якщо знайдеш найкоротший шлях до хатинки, буде тобі дружиною Василиcа Прекрасна». Прокинувся Іван, а у нього в руках карта тридев'ятого царства, тридесятої держави. Всі водоймища в державі – озера, кожне озеро має форму правильного багатокутника. Жодні два озера не мають спільних точок. Допоможіть Івану дістатися до хатинки.
Технічні умови: Спочатку ви вводите з клавіатури координати будинку Івана і координати хатинки. Потім Ви вводите кількість озер (не більше 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, офіцер з особливих доручень, направив ТТП (термінове таємне повідомлення) у Генеральний штаб. У блямблямськой армії ТТП передаються таким чином: надcилають два пакети, кожен містить деякий текст, ТТП – текст максимальної довжини, що входить цілком в обидва пакети (тобто в обох пакетах є фрагмент, ідентичний ТТП). Допоможіть начальникові штабу прочитати ТТП.
Технічні умови: Ви вводите з клавіатури в першому рядку вміст першого пакету, в другому рядку вміст другого пакету. Довжина тексту в пакеті не перевищує 10000 символів. Ви виводите на екран максимально можливу довжину ТТП.
Приклад.
Введення>
moloko
doloto
Виведення> 3
Г.Кравец, Г.Непомнящий, К.Симонов, Ю.Пасихов
