Задача Unizero
Первокласснику Матвею среди всех цифр больше всего нравятся единица и нуль. Он пытается определить количество разных последовательностей цифр длиной n, причем между любой парой соседних единиц в каждой последовательности должно находиться одно и то же количество нулей (не меньше одного). Последовательность может начинаться и с нуля, и c единицы. Помогите Матвею.
Технические условия. Программа Unizero читает c устройства стандартного ввода единственное натуральное число n (3<=n<=5000000). Программа выводит на устройство стандартного вывода искомую величину - количество возможных последовательностей.
Пример
Ввод 4
Вывод 3
КОММЕНТАРИЙ К ПРИМЕРУ. Последовательности, удовлетворяющие условию задачи при n=4, : 1010 0101 1001.
=====================================================
Задача Walk.В начале эксперимента Робот стоит спиной к глубокой яме на самом ее краю. Робот может делать один шаг ежесекундно или вперед, или назад, стоять во время эксперимента на месте он не может. Подсчитайте, сколькими способами робот может оказаться в яме во время эксперимента. (Оказаться в яме значит очутиться хотя бы на шаг назад от начального положения робота)
Технические условия. Программа Walk читает с устройства стандартного ввода единственное натуральное число - время эксперимента t (0<t<=1000). Программа выводит на устройство стандартного вывода искомое количество способов по модулю 109+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(i, j) в каждой. Если между школами с номерами i и j проложен кабель, n(i,j)=1, если нет, то n(i,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 <= 109, 2 <= k <= 1000). Программа выводит на устройство стандартного вывода единственное число - искомую величину.
Примеры
Ввод 10 10
Вывод 2
Комментарий: 10! = 362880010.
Ввод 15 8
Вывод 3
Комментарий: 15! = 130767436800010 = 230167356540008
Задания подготовили И.Энтин, Г.Непомнящий, А.Островский, Ю.Пасихов
| 
