Розв'язки приймаються до 0 годин 28 грудня 2012 р.
Задача Hanoysoft
Герой NetOI Василь Пупкін вирішив трохи підробити на своєму вмінні розв’язувати складні задачі з інформатики. Щоб влаштуватись до компанії Megasoft, Вася прийшов на співбесіду, де йому запропонували розкласти ханойські вежі. Вася почав розкладати і виявив, що тут щось не так – жоден диск неможливо перекласти з першого стержня на третій і навпаки. Вася все ж переклав усі диски, але довести Головному Директору фірми Гіллу Бейтсу, що кількість перекладань мінімальна, не зміг. Допоможіть Гіллу Бейтсу і Васі визначити мінімальну кількість ходів.
Технічні умови. Програма Hanoysoft читає з клавіатури кількість дисків N (1<=N<=10000), далі через пропуск номери початкового і кінцевого стержнів A B (1<=A, B<=3, A<>B). Програма виводить на екран мінімальну кількість перекладань дисків за модулем 1000000007.
Приклади
Введення
2 1 2
Виведення
4
Введення
3 3 1
Виведення
26
Задача Upgrade
Як і у будь якому великому місті, у нашому досить багато шкіл, кожна має свій сервер. Деякі із них з’єднані між собою каналами двостороннього прямого зв’язку. Кожен із каналів сполучає безпосередньо 2 школи, будь-які дві школи з’єднані не більше, ніж одним каналом. Освіта не має багато коштів, тому до кожної школи веде не більше, ніж 2 канали. В процесі роботи інформація передається з сервера-«відправника» на сервер – «отримувач» через деякі із наявних каналів, при чому неважливо, через які. Але багато каналів облаштовано давно і не призначено для передачі інформації з великою швидкістю. Наша лабораторія прийняла рішення замінити частину каналів на оптоволоконні таким чином: якщо інформація могла потрапляти із сервера A на сервер B, то тепер вона зможе пройти з А на В через оптоволоконні канали. Звичайно, оптичне волокно коштує дорого, тому ми хочемо замінити мінімальну кількість старих «мідних» каналів на нові оптоволоконні, а надлишкові «мідні» законсервувати. Зрозуміло, що кожен сервер уміє, як і раніше, «роутити» інформацію, тобто пропускати її далі, якщо існує канал зв’язку.
Дуже хочеться знати, скільки існує різних способів заміни мінімальної кількості каналів. Два способи вважатимуться різними, якщо існує канал, який замінено в одному із способів, і не замінено у іншому. Допоможіть нам.
Технічні умови. Програма UPGRADE читає з клавіатури 2 числа n і m (1<=n<=105 0<=m<=105) – кількість шкіл та кількість каналів відповідно. Далі програма читає в m рядках канали, по одному у рядку. Кожен канал задано двома цілими числами Аі та Ві (1<= Аі, Ві <=n, Аі <> Ві) – номери шкіл, які з’єднує канал із номером і. Гарантовано, що кожний канал задано не більше одного разу. Програма виводить на екран єдине число – кількість способів заміни. Так як число може бути вельми велике, виводити треба по модулю 109+7 (тобто – остачу від ділення на це число)
Приклади
|
Введення
5 4
1 2
2 3
1 3
4 5
|
Виведення
3
|
Введення
2 1
1 2
|
Виведення
1
|
|
Пояснення до прикладу. Існує три способи заміни каналів:
{1,2,4},{1,3,4},{2,3,4}
|
Задача Digits2
Є натуральне число L. Над цим числом означено операції: «ПОПОЛАМ» (розділити число на 2, та «-05» (відняти 0,5). Операції виконуються одна за одною у довільному порядку, але з однією умовою; якщо перед операцією число було не цілим, то наступною може бути лише операція «-05». Після виконання К операцій число може мати різне значення Lі. Скільки можливих значень матиме число Lі ?
Технічні умови.
Програма Digits2читає з клавіатури два числа L – початкове значення числа, і К – кількість операцій (1 <= L,K <=· 1000). Програма виводить на екран кількість значень, що їх може мати Lі
Приклад
Введення Виведення
6 1 2
Задача Chocolate
Маленькому хлопчику Васі на день народження подарували шоколадну брилу, яка має форму паралелепіпеда розмірами M*N*K. Від будь-якої грані можна відпиляти шоколадку лише товщиною 1. Вася ніколи не ламає отримані таким чином шоколадки і пиляє шоколадну брилу доти, доки це можливо. Скільки різних наборів шоколадок може вийти у Васі? Набори вважаються різними, якщо в них різна кількість шоколадок хоча б одного розміру. Шоколадки x*y та y*x вважаються однаковими.
Технічні умови. Програма Chocolate читає з клавіатури розміри шоколадки M, N, K (1<=M,N,K<=100) і виводить на екран шукану кількість шоколадок за модулем 1000007.
Приклади
Введення 2 2 4
Виведення 3
Введення 2 2 2
Виведення 1
Введення 3 2 4
Виведення 7
Коментар до першого прикладу
Брилу 2*2*4 можна розрізати на 2 шоколадки 1*2*4, або на 4 шоколадки 1*2*2, або на одну 1*2*2 і дві 1*2*3.
Задача Trimino
Знайдіть кількість способів покриття прямокутника 4*N фігурками «Триміно». «Триміно» - це квадрат 2*2 з однією вирізаною клітинкою.
Технічні умови
Програма Trimino читає з клавіатури натуральне число N (1<=N<=100000) і виводить на екран шукану кількість способів за модулем 1000000007.
Приклади
Введення 3
Виведення 4
Введення 7
Виведення 0
Пояснення до першого прикладу. Усі способи покриття показано на малюнку.
Завдання підготували Г.Непомнящий, Ю.Пасіхов
|
