|
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).
Вихідні дані
Файл має містити єдине ціле число – кількість способів.
Приклад.
|
input.txt
|
output.txt
|
|
10
4
|
2
0
|
Задача 2. Текстовий рядок (100 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 5с.
Задано текстовий рядок S, що складається виключно з маленьких літер латинського алфавіту. Над рядком можна виконувати наступні операції:
- вставляти будь-яку літеру з діапазону 'a' - 'z' в будь-яке місце рядка за час TI;
- видаляти будь-яку літеру з будь-якої позиції рядка за час TD;
- замінювати будь-яку літеру в будь-якій позиції рядка іншою літерою з діапазону 'a' - 'z' за час TR;
- міняти місцями будь-які дві сусідні літери рядка за час TE.
Необхідно написати програму, що визначає мінімальний час перетворення початково-го текстового рядка в інший текстовий рядок D.
Вхідні дані.
У першому рядку файлу міститься чотири цілих числа TI, TD, TR, TE (1 ≤ TI,TD,TR,TE ≤ 100, 2×TE ≥ TI + TD).
В наступних двох рядках файлу містяться текстові рядки S та D, довжини яких знаходяться в інтервалі від 1 до 4000 літер включно.
Вихідні дані.
Файл має містити єдине ціле число – найменший час перетворення текстового рядка S в D.
Приклад.
|
input.txt
|
output.txt
|
|
2 4 10 3
ab
ba
|
3
|
|
1 10 20 30
a
za
|
1
|
|
