1. Арифметическая прогрессия (Российский Оргкомитет, 10 баллов). Задана последовательность натуральных чисел из диапазона [1; 2147483647]. Количество чисел в последовательности не превышает 10000. Необходимо определить, можно ли выстроить эти числа в отрезок неубывающей арифметической прогрессии. Если да, то вывести “Да”, первый член и разность прогрессии, иначе вывести “Нет”. При необходимости порядок чисел в последовательности можно изменять.
Пример правильно работающей программы:
Количество членов: 10
Последовательность: 10 30 40 20 60 50 70 90 80 100
Ответ: Да 10 10
2. Нечего делать внутри… (Брызгалов Е.В., 20 баллов) На плоскости расположено N (2 <= N <= 20) точек, заданных своими координатами. Требуется найти круг минимальной площади, содержащий все эти точки, и вывести координаты его центра и радиус.
Техническое замечание: результат представить как число с фиксированной точкой с не менее чем пятью знаками после запятой.
Пример работы правильной программы:
Введите количество точек: 4
Введите координаты 1-ой точки: 3 4
Введите координаты 2-ой точки: –5 0
Введите координаты 3-ой точки: 0 –5
Введите координаты 4-ой точки: 2.5 1.4
Центр — (0.00000, 0.00000), радиус — 5.00000.
3. “Лягушка-путешественница” (Деменев А.Г., 25 баллов). На заданных N клетках шахматной доски установлены кубики, линейный размер которых совпадает с размером клетки. На одну клетку может быть установлено не более 8 кубиков. На заданную клетку сверху положили лягушку. Она может путешествовать по доске, перепрыгивая с клетки на клетку, если они имеют общую сторону, но ей непосильны прыжки высотой более чем в один кубик. Будем называть клетку потенциально недоступной, если к ней не существует посильного для лягушки маршрута. Примечания: лягушка может прыгать вниз с любой высоты, не может выходить за пределы доски, маршрут может быть нулевой длины.
Требуется написать программу, которая по заданным координатам клеток и количеству установленных на них кубиков выдаст количество недоступных клеток.
Технические требования
Формат входных данных: в первой строке — координата клетки, где сидит лягушка; во второй — количество клеток N, закрытых кубиками; в каждой из N следующих строк координата клетки и через пробел количество кубиков на ней.
Формат выходных данных: одна строка с числом недоступных клеток.
Пример входных данных:
a1
4
a2 4
a1 2
b2 4
c1 2
Пример выходных данных:
62
4. Возрастающая подпоследовательность (Шестаков А.П., из книги А. Шеня, 25 баллов). Дан целочисленный одномерный массив. Найти наименьшее число К элементов, которые можно выкинуть из массива, чтобы осталась возрастающая последовательность. Порядок следования элементов в возрастающей последовательности остается тем же, что и в исходной. Если возможных решений несколько, вывести одно из них.
Техническое требование. В качестве ответа вывести образовавшуюся возрастающую последовательность, количество исключенных элементов и исключенные элементы.
Пример работы правильной программы
Введите количество элементов: 8
Введите последовательность: 2 1 2 –3 3 3 4 7
Оставшийся массив: 1 2 3 4 7
Исключено 3 элемента: 2 –3 3
5. Умножение периодической дроби (Российский Оргкомитет, 30 баллов). Задана некоторая положительная правильная периодическая дробь Q и натуральное число N. Q и N таковы, что количество цифр, используемых для их описания, не превосходит 100. При изображении дроби Q периодическая часть заключается в круглые скобки.
Требуется написать программу, которая определяет результат умножения Q на N, то есть непериодическую часть и минимальный период числа Q * N.
В случае получения результата умножения в виде конечной дроби скобки опускаются.
Пример работы правильной программы
Введите периодическую дробь: 0.1(6)
Введите натуральное число: 2
Ответ: 0.(3)