Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Завдання 2 туру NetOI-2012 (25.11.2012 -28.12.2012)

Розв'язки приймаються до 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

Пояснення до першого прикладу. Усі способи покриття показано на малюнку.



Завдання підготували Г.Непомнящий, Ю.Пасіхов 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"