5 тур - з 17.11 по 23.11.2014

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

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

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

Задача 1. Фіналісти (20 балів)

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

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

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

Під час проведення чергового сезону шоу "Україна має талант" перед суддями стала проблема вибору трійки фіналістів з поміж N учасників – наскільки сильними вони були. Тому судді вирішили покластись на такий алгоритм вибору: картки з прізвищами учасників розкладають в одну лінію і, поки їх в лінії залишається більше трьох, судді прибирають всі картки, що знаходяться виключно на парних або непарних місцях. Так має продовжуватись до тих пір, поки не залишаться три або менше карток – карток з прізвищами фіналістів.

Необхідно написати програму для підрахунку кількості способів вибору трійки фіналістів таким чином.

Вхідні дані

Файл містить єдине ціле число N (1 ≤ N ≤ 1000000).

Вихідні дані

Файл має містити єдине ціле число – кількість способів.

Приклад.

Задача 2. Текстовий рядок (100 балів)

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

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

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

Задано текстовий рядок S, що складається виключно з маленьких літер латинського алфавіту. Над рядком можна виконувати наступні операції:

- вставляти будь-яку літеру з діапазону 'a' - 'z' в будь-яке місце рядка за час T_I;

- видаляти будь-яку літеру з будь-якої позиції рядка за час T_D;

- замінювати будь-яку літеру в будь-якій позиції рядка іншою літерою з діапазону 'a' - 'z' за час T_R;

- міняти місцями будь-які дві сусідні літери рядка за час T_E.

Необхідно написати програму, що визначає мінімальний час перетворення початково-го текстового рядка в інший текстовий рядок D.

Вхідні дані.

У першому рядку файлу міститься чотири цілих числа T_I, T_D, T_R, T_E (1 ≤ T_I,T_D,T_R,T_E ≤ 100, 2×T_E ≥ T_I + T_D).

В наступних двох рядках файлу містяться текстові рядки S та D, довжини яких знаходяться в інтервалі від 1 до 4000 літер включно.

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

Файл має містити єдине ціле число – найменший час перетворення текстового рядка S в D.

Приклад.