Задача 4 « Разрезание прямоугольника »

На координатной плоскости задан прямоугольник, высота которого h, а ширина — w. Внутри прямоугольника заданы отрезки, параллельные осям координат и с концами, имеющими целочисленные координаты.

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

Требуется написать программу, позволяющую найти количество способов разрезания исходного прямоугольника на k частей вертикальными и горизонтальными разрезами. Способы, отличающиеся порядком проведения разрезов, считаются различными.

Формат входных данных

Первая строка входного файла содержит размеры прямоугольника – целые числа h и w (1 ≤ h, w ≤ 8). Вторая строка входного файла содержит целое число k – количество частей, на которые требуется разрезать прямоугольник (1 ≤ k ≤ hw). Третья строка содержит целое число cnt (0 ≤ cnt ≤ 10) — количество заданных внутри прямоугольника отрезков. Последующие cnt строк содержат описания этих отрезков, то есть, каждая строка содержит четыре целых числа x₁, y₁, x₂, y₂ (0 ≤ x₁ ≤ x₂ ≤ w, 0 ≤ y₁ ≤ y₂ ≤ h) — координаты концов отрезка. Все числа в строках разделены пробелом.

Формат выходных данных

В выходной файл необходимо вывести одно целое число — искомое количество способов разрезания исходного прямоугольника. Ответ должен быть представлен по
модулю 2³⁰.

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

Задача 5 « Рекурсия »

«Чтобы понять рекурсию, надо понять рекурсию»

Фольклор

Одним из важных понятий, используемых в теории алгоритмов, является рекурсия. Неформально ее можно определить как использование в описании объекта самого себя. Если речь идет о процедуре, то в процессе исполнении эта процедура напрямую или косвенно (через другие процедуры) вызывает сама себя.

Рекурсия является очень «мощным» методом построения алгоритмов, но таит в себе некоторые опасности. Например, неаккуратно написанная рекурсивная процедура может войти в бесконечную рекурсию, то есть, никогда не закончить свое выполнение (на самом деле, выполнение закончится с переполнением стека).

Поскольку рекурсия может быть косвенной (процедура вызывает сама себя через другие процедуры), то задача определения того факта, является ли данная процедура рекурсивной, достаточно сложна. Попробуем решить более простую задачу.

Рассмотрим программу, состоящую из n процедур P₁, P₂, …, P_n. Пусть для каждой процедуры известны процедуры, которые она может вызывать. Процедура P называется потенциально рекурсивной, если существует такая последовательность процедур Q₀, Q₁, …, Q_k, что Q₀ = Q_k = P и для i = 1…k–1 процедура Q_i-1 может вызвать процедуру Q_i. В этом случае задача будет заключаться в определении для каждой из заданных процедур, является ли она потенциально рекурсивной.

Требуется написать программу, которая позволит решить названную задачу.

Формат входных данных

Первая строка входного файла содержит целое число n — количество процедур в программе (1 ≤ n ≤ 100).

Далее следуют n блоков, описывающих процедуры. Блоки отделены друг от друга и от первой строки входного файла строками, каждая из которых содержит по 5 символов «*».

Описание процедуры начинается со строки, содержащий ее идентификатор, состоящий только из маленьких букв латинского алфавита и цифр. Идентификатор непуст, и его длина не превосходит 100 символов. Далее идет строка, содержащая число k (k ≤ n ) — количество процедур, которые могут быть вызваны описываемой процедурой. Последующие k строк содержат идентификаторы этих процедур — по одному идентификатору на строке.

Различные процедуры имеют различные идентификаторы. При этом ни одна процедура не может вызвать процедуру, которая не описана во входном файле.

Формат выходных данных

Для каждой процедуры, присутствующей во входном файле, необходимо вывести слово YES, если она является потенциально рекурсивной, и слово NO – в противном случае.

Следуйте формату вывода, приведенному в примере. Процедуры в выходном файле должны быть выведены в том же порядке, в каком они перечислены во входном файле.

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

Поиск по сайту: