4 тур - з 10.11 по 16.11.2014

точка входу для відправлення розв'язків:

http://176.31.28.231/cgi-bin/new-client?contest_id=18

скачати умови задач четвертого туру (*.docx)

Задача 1. Покупка квитків (20 балів)

Ім’я вхідного файлу: input.txt

Ім’я вхідного файлу: output.txt

Ліміт часу: 1с.

За квитками на прем'єру нового мюзіклу вишикувалась черга з n человік, кожен з яких хоче купити один квиток. На всю чергу працювала лише одна каса,  тому продаж квитків йшов дуже повільно, приводячи "постояльців"  черги у відчай. Найкмітливіші швидко помітили, що, як правило, кілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються по одному. Тому вони запропонували декільком людям, які стоять поспіль, віддавати гроші першому з них, щоб він купив квитки на всіх.

Однак для боротьби зі спекулянтами касир продавав не більше п'яти квитків в одні руки, тому домовитися таким чином між собою могли лише дві, три, чотири і навіть п'ять людей, які стоять поруч.

Відомно, что на продажу i-й людині з черги одного квитка касир витрачає ai секунд, на продажу двох квитків bi секунд, трьох квитків ci секунд, чотирьох квитків di секунд,  п'ятьох квитків еi секунд . Напишіть програму, яка підрахує мінімальний час, за який можна обслужити усіх покупців.

Зверніть увагу, що квитки на групу людей, що об'єдналися, завжди купляє перший з них. Також ніхто з метою прискорення не купує зайвих квитків (тобто квитків, які нікому не потрібні).

Вхідні дані

Перше число містить кількість покупців у черзі n (1 ≤ n ≤ 5000). Далі йде n п'ятsырок натуральних чисел ai, bi, ci, di, ei. Кожне з цих чисел не перевищує 3600. Люди у черзі нумеруються починаючи від каси.

Вихідні дані

Вивести мінімальний час у секундах, за який можна обслужити усіх покупців.

Задача 2. Мережа АЗС (100 балів)

Ім’я вхідного файлу: input.txt

Ім’я вхідного файлу: output.txt

Ліміт часу: 5с.

Керівництво мережі автозаправних станцій (АЗС) для зручності обслуговування клієнтів, вирішило підключити всі АЗС до глобальної мережі Інтернет. Провайдер Інтернет надає послуги через системи  супутникового зв'язку, яке встановлюється безпосередньо на АЗС, але можливості поставити обладнання на всіх АЗС немає.

Було прийнято рішення, щоб до АЗС на якій немає супутникового обладнання протягнути окремий кабель, від найближчого супутникового обладнання.

Всі АЗС знаходять на прямій дорозі, положення якої визначається N-тим кілометром, який відповідає номеру АЗС.

Необхідно написати програму, що визначає номера АЗС, на яких необхідно поставити супутникове обладнання, так щоб довжина кабелю була мінімальною.

Вхідні дані.

У першому рядку файлу міститься два числа: кількість АЗС (1≤K≤500) та кількість супутникового обладнання (1≤S≤50, S≤K).

В другому рядку номера АЗС (1≤N≤1000) .

Вихідні дані.

У першому рядку міститься довжина кабелю. В другому рядку номера АЗС в порядку зростання.

Приклад.