Требуется подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100).

Выходные данные
В выходной файл вывести количество искомых последовательностей.

Пример входного файла
5

Пример выходного файла
13

   Решение

Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v₁ и v₂ и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v₁ в вершину v₂, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам);
2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v₁ в v₂ .

Входные данные
Первая строка входного файла содержит целое число N – количество вершин в графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во входном файле записаны без разделительных пробелов. 

Наконец, строка N+2 содержит номера вершин v₁ и v₂ , а строка N+3 – десятичную запись числа C (1 &le C < 10⁵⁰).

Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи: «Yes», если путь длины C существует, и «No», если нет. Во вторую строку запишите ответ на второй пункт задачи. Если ни одного пути из v₁ в v₂ не существует, ваша программа должна вывести -1.

Пример входного файла
3
010
001
100
1 1
555555555555555555555555555555555

Пример выходного файла
Yes
0

   Решение

Во входном файле записано равенство вида A = B, где A и B – это выражения, содержащие сколь угодно длинные целые числа и знаки операций +, - (бинарный и унарный) и *. Выражения не содержат скобок. Требуется проверить выполнение заданного равенства и вывести в выходной файл результат проверки в форме «Да, выполняется» или «Нет, не выполняется».
Длина входного файла данных не превосходит 60 килобайт. Числа и знаки операций в выражении могут разделяться пробелами и/или символами перевода строки.

Пример входного файла
2
                * 43 = 86

Пример выходного файла
Да, выполняется

   Решение

Темы:    [ Динамическое программирование (прочее) ] [ Длинная арифметика как инструмент ]

Сложность: 3+ Классы: Название задачи: Дырокол .

Прислать комментарий

Условие

Квадратный клетчатый лист бумаги 2^N × 2^N клеток начинают складывать следующим образом. Сначала нижняя половина листа накладывается на верхнюю, затем правая половина листа накладывается на левую. Эту операцию повторяют N-3 раза, в результате чего получается сложенный лист 8 × 8 клеток. Какие-то из клеток этого сложенного листа удаляются при помощи дырокола.

После развертывания исходный лист распадется на некоторое количество связных частей, т.е. таких множеств клеток, что из любой клетки одного множества можно пройти до любой другой, переходя каждый раз на соседнюю по вертикали или горизонтали клетку. Напишите программу, вычисляющую число частей, на которые распадется лист.

Входные данные
Первая строка входного файла содержит целое число N (4 ≤ N ≤ 500). В следующих 8 строках записана матрица 8 × 8 из нулей и единиц, разделенных пробелом. Единицами отмечены клетки, выкалываемые дыроколом из сложенного листа 8 × 8.

Выходные данные
Вывести в выходной файл искомое число частей.

Пример входного файла
4
0 1 0 0 0 0 1 0
1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0

Пример выходного файла
11

Решение

Скачать архив тестов и решений

Каждую связную область сложенного листа (если смотреть на него сверху) закодируем двоичным числом b₃b₂b₁b₀ . А именно, положим b₀ равным единице, если эта область примыкает к нижней границе листа, и нулю в противном случае. Числа b₁ , b₂ и b₃ определим аналогичным образом для верхней, правой и левой границ листа соответственно. Тем самым, все области разбиваются на 16 типов в соответствии с их кодами. Теперь проанализируем, что происходит с областями при развертывании листа. 

Рассмотрим, например, разгибание относительно нижней стороны. Легко заметить, что связная область типа b₃b₂b₁1 перейдет в связную область типа b₃b₂b₁b₁ (действительно, будет ли она прилегать к нижнему краю после разгибания зависит от того, прилегала ли она к верхнему до разгибания). Связная область типа b₃b₂b₁0 после разгибания распадется на две. Одна из них будет иметь тот же тип b₃b₂b₁0, а другая – тип b₃b₂0b₁. Аналогично анализируется разгибание листа относительно правой стороны.

Для решения задачи проделываем 2N разгибаний, обратных произведенным при складывании листа сгибаниям. При этом на каждом шаге пересчитываем количество связных областей каждого из типов.

Источники и прецеденты использования