(1-4 февраля 2008 г.)

Задача A. Числовая последовательность

Дима недавно поступил на работу в научно-исследовательский институт «Числовые Последовательности». Как следует из названия этого института, основным направлением его работы является проведение различных исследований в области числовых последовательностей.

Недавно руководитель отдела, где начал работать Дима, при решении одной из проблем столкнулся с весьма интересной последовательностью чисел a₁, a₂, …, a_n, …, которая определяется следующим образом: a₁ = 0 и каждое последующее число a_i (1 < i ≤ n) определяется как наименьшее большее натуральное число, десятичная запись которого не содержит цифр, представленных в десятичной записи a_i-1.

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

Входные данные

Входной файл INPUT.TXT содержит натуральное число N (N<=500).

Выходные данные

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

Примеры

Задача B. Вписанная окружность

Очень интересными объектами, которые изучаются в планиметрии, являются вписанные и описанные окружности. Известно, например, что вокруг любого треугольника можно описать окружность и в любой треугольник можно вписать окружность. А что будет, если вместо треугольника задан выпуклый многоугольник?

Требуется написать программу, которая определяет, можно ли в заданный выпуклый многоугольник вписать окружность, и, если это можно сделать, то вычисляет координаты ее центра и радиус.

Входные данные

Первая строка входного файла INPUT.TXT содержит количество вершин многоугольника n (3 ≤ n ≤ 8). Последующие n строк содержат координаты вершин многоугольника в порядке обхода против часовой стрелки, каждая i-ая из них содержит два целых числа: x_i и y_i, значения которых не превосходят 1000 по абсолютной величине.

Выходные данные

В первой строке выходного файла OUTPUT.TXT необходимо вывести YES, если окружность, вписанная в заданный многоугольник, существует, в противном случае следует вывести слово NO . В случае положительного ответа во второй строке следует указать координаты центра окружности и ее радиус. Числа следует выводить с тремя знаками после точки (даже если там нули), округляя их до 10^-3 по математическим правилам. Число «0.000» следует выводить без знака «-».

Примеры

Задача C. Укладка плиток

Вы являетесь одним из разработчиков нового архитектурного пакета прикладных программ «CadArch». Одной из его функций является проектирование укладки половых плиток. В настоящее время вы занимаетесь программной реализацией модуля, который отвечает за укладку плиток в прямоугольных помещениях.

Для простоты будем считать, что пол помещения представляет собой прямоугольник размером n на m метров, разбитый на m∙n квадратиков со стороной по 1 метру. Кроме этого, будем считать, что имеется четыре типа плиток, показанные в таблице. Каждая из плиток представляет собой квадрат размером 2 на 2 метра, из которого вырезан один квадратик размером 1 на 1 метр.

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

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

Входные данные

Первая строка входного файла INPUT.TXT содержит два числа n и m — высота и ширина пола помещения (1 ≤ m, n ≤ 50). Вторая строка содержит число k — количество команд, которые необходимо обработать. Каждая из последующих k строк содержит описание одной команды из набора команд. Описание команды состоит из трех чисел. Первое число определяет тип плитки (число от 1 до 4), а два других - координаты левого верхнего квадрата (y,x) размером 2 на 2, в который вписана соответствующая плитка (0 ≤ x, y, k ≤ 1000).

Выходные данные

В выходной файл OUTPUT.TXT необходимо вывести одно число, определяющее площадь, покрытую плитками после выполнения заданной во входном файле последовательности команд.

Пример

Задача D. Ближайшие точки

Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: «На числовой прямой задано n точек. Необходимо найти среди них две ближайшие». Расстояние между двумя точками числовой прямой x и y равно |x - y|.

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

Входные данные

Первая строка входного файла INPUT.TXT содержит количество точек n (2 ≤ n ≤ 10⁵). Вторая строка содержит n различных целых чисел x_i – координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значения всех координат x_i не превосходят 10⁹ по абсолютной величине.

Выходные данные

В первой строке выходного файла OUTPUT.TXT необходимо вывести минимальное расстояние между двумя точками, заданными во входном файле. Во второй строке выходного файла необходимо вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от 1 до n в том порядке, в котором они заданы во входном файле. Если ответов несколько, выведите тот из них, в котором точки расположены левее других на числовой прямой. Первым выводится номер левой точки, далее через пробел – номер правой точки.

Пример

Задача E. Рекурсия

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

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

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

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

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

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число n — количество процедур в программе (1 ≤ n ≤ 100). Далее следуют n блоков, описывающих процедуры. После каждого блока следует строка, которая содержит 5 символов «*».

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

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

Выходные данные

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

Пример

Задача F. Сумма двух чисел

Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c.

Входные данные

Входной файл INPUT.TXT содержит три целых числа: a, b, c (0 < a, b, c < 10⁹). Числа разделены пробелом.

Выходные данные

В выходной файл OUTPUT.TXT следует вывести YES, если искомая перестановка цифр возможна, в противном случае необходимо вывести NO. При положительном ответе во второй строке следует вывести число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y при выводе не должны содержать ведущих нулей. Числа в строке разделены пробелом. Если решений несколько, то следует вывести ту пару, в которой число x минимально.

Примеры