Задача Unizero. Першокласнику Матвію серед усіх цифр найбільше подобаються одиниця та нуль. Він намагається визначити кількість різних послідовностей цифр довжиною n з такими властивостями: між будь-якою парою сусідніх одиниць у кожній послідовності повинна знаходитися одна й та ж кількість нулів (не менше від одного). Послідовність може починатися і з нуля, і з одиниці. Допоможіть Матвію.

Технічні умови. Програма Unizero читає з пристрою стандартного введення єдине натуральне число n (3<=n<=5000000). Програма виводить на пристрій стандартного виведення шукану величину – кількість можливих послідовностей.

Приклад

Введення 4

Виведення 3

КОМЕНТАР ДО ПРИКЛАДУ. Послідовності, які задовольняють умові задачі при n=4: 1010 0101 1001.

=====================================================

Задача Walk. На початку експерименту Робот стоїть спиною до глибокої ями на самому краєчку. Робот може робити один крок щосекунди або вперед, або назад, стояти під час експерименту на місці він не може. Підрахуйте, скількома способами робот може опинитися в ямі під час експерименту. (Опинитися в ямі означає опинитися хоча б на крок позаду від початкового положення робота)

Технічні умови. Програма Walk читає з пристрою стандартного введення єдине натуральне число – час експерименту t (0<t<=1000). Програма виводить на пристрій стандартного виведення  шукану кількість способів по модулю 10⁹+7

Приклад

Введення: 5

Виведення: 4

Коментар до прикладу: 4 «прогулянки» робота тривалістю не більшеніж 5 секунд закінчуються падінням у яму (правда, він на те й робот, щоб не розбитися і взяти участь в наступному експерименті…)

1.<-

2. -><- <-

3. -> -><- <- <-

4.-><- -><- <-

====================================================

Задача Hanoy2015. Герой задачі Hanoysotf Вася Пупкін вирішив удосконалити свої Ханойські вежі. Він замовив N дисків та три стержні, але коли отримав замовлення, здивуванню Васі не було межі. Деякі диски виявились однаковими! Вася вирішив, що при перекладанні можна диск покласти на диск не меншого розміру. Допоможіть Васі обчислити мінімальну кількість перекладань дисків з першого стержня на другий. Нагадаємо, що за один хід можна перекласти лише один диск. Дозволено перекладати диск з будь-якого стержня на будь-який, але заборонено класти більший диск на менший.

Технічні умови. Програма Hanoy2015 читає з клавіатури кількість дисків N (1<=N<=64) і далі N натуральних чисел, не більших 10000 – діаметри дисків. Програма виводить на екран шукану мінімальну кількість перекладань.

Приклад.

Введення 7 3 5 3 5 3 3 3

Виведення 12

Коментар. На початку на першому стержні буде розміщено 2 диски діаметром 5, а на них 5 дисків діаметром 3. Перекладаємо 5 менших дисків на третій стержень, потім 2 більших диски на стержень 2, потім 5 менших дисків з третього стержня на другий.

====================================================

Задача Schoolnet2015n. Лабораторія ІКТ ФМГ17 ініціювала розбудову оптоволоконних каналів зв’язку між школами. Усіх шкіл у місті 2<N<1000. На практиці це виглядає так: при наявності коштів між деякими двома школами прокладається оптоволоконний кабель. Коштів мало, робота довготривала, швидко завершити її не вдається. Але якщо школа №1 має прокладений прямий канал до школи №123, то може мати з нею спільну локальну мережу, а якщо ще проклали кабель від школи №123 до школи №27, то ця мережа включає вже 3 школи, а її системний адміністратор може обслуговувати ці 3 школи, тобто школа може створити спільну мережу з тими школами, з якими з'єднана або «напряму», або через іншу школу. Скільки шкіл входять до найбільшої «міжшкільної» локальної мережі? Який мінімальний номер школи, адміністратор якої може обслуговувати найбільшу кількість шкіл?

Технічні умови. Програма Schoolnet2015n читає з пристрою стандартного введення число шкіл N, а далі Nрядків по N чисел n(і,j) у кожному. Якщо між школами з номерами і та j прокладено кабель, n(і,j)=1, якщо ні, тоn(і,j)=0. Всі числа у рядку розділено пропусками. Програма виводить на пристрій стандартного виведення кількість шкіл у найбільшій мережі та через пропуск мінімальний номер школи, адміністратор якої може обслуговувати найбільшу кількість шкіл.

Приклад.

Введення

5

0 1 0 0 0

1 0 0 0 0

0 0 0 1 0

0 0 1 0 1

0 0 0 1 0

Виведення 3 3

=====================================================

Задача FactZero. Знайти кількість нулів, якими закінчується запис числа n! у системі числення з основою k.

Технічні умови. Програма FactZero читає з пристрою стандартного введення два цілих числа n і k через пропуск (0<=n<=10⁹, 2<=k<=1000). Програма виводить на пристрій стандартного виведення єдине число – шукану величину.

Приклади

Введення 10 10

Виведення 2

Коментар: 10! = 3628800₁₀.

Введення 15 8

Виведення 3

Коментар: 15! = 1307674368000₁₀ = 23016735654000₈

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