Решения принимаются до 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 школы, любые две школы соединены не более, чем одним каналом. Образование не имеет достаточно средств, потому к каждой школе ведет не более двух каналов. В процессе работы информация передается с сервера-«отправителя» на сервер– «получатель» через некоторые из наявных каналов, причем неважно, через какие. Но многие из существующих каналов обустроены давно и не предназначены для передачи информации с большой скоростью. Наша лаборатория приняла решенние заменить часть каналов оптоволоконными таким образом: если информация могла попадать с сервера 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
Комментарий к первому примеру: все способы покрытия указаны на рисунке.
Задания подготовили Г.Непомнящий, Ю.Пасихов
|
