|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Олимпиада по программированию
Условия задач олимпиады
Архив задач в формате MS-WORD: Скачать [16048 байт, архив WinRar]. Имена входных файлов ко всем задачам - INPUT.TXT.
ЗАДАЧИ: Задача A. Слоники.
Расставьте на шахматной доске N x N минимальное количество слонов так, чтобы они били все поле (любая клетка должна находиться на одной диагонали хотя бы с одним слоном). Формат входных данных: В файле записано единственное целое число 0 <= N <= 1000. Формат выходных данных: На первой строке выведите минимальное количество слонов. Строки с номерами 2...N + 1 содержат описание доски, 0 - соответствующая клетка пуста, 1 - в клетке стоит слон. Числа необходимо разделять пробелами. Примеры:
Задача B. Единицы и нули.
На листе бумаге N x N стоят единицы и нули. За одно действие разрешается выбрать N клеток, по одной в каждом столбце и каждой строке, и изменить в них цифры (единицы на нули и наоборот). С помощью таких действий получите на листе расстановку чисел, в которой количество единиц меньше N. Формат входных данных: На первой строке записано нечетное число 1 <= N <= 101. На следующих N строках находится описание листа. Формат выходных данных: K-ая строка выходного файла описывает k-ое действие: она должна содержать N чисел, среди которых i-ое число является номером столбца, выбранной в i-ой строке клетки. Количество действий не должно превосходить 100 000. В конце файла выведите -1. На первой строке выведите минимальное количество слонов. Примеры:
Задача C. Многоугольники.
Назовем суммой двух многоугольников А и В множество всех точек плоскости с координатами (x, y), для которых существуют такие точки (x1, y1) и (x2, y2), принадлежащие соответственно А и В, что x = x1 + x2 и y = y1 + y2. Суммой выпуклых многоугольников является выпуклый многоугольник. Во входном файле дано описание двух выпуклых многоугольников, найдите их сумму. Формат входных данных: В первой строке записано количество вершин многоугольника 3 <= N <= 100. На следующих N строках находятся координаты вершин в порядке обхода против часовой стрелки. Далее в том же формате описывается второй многоугольник. Все числа во входном файле целые и по абсолютной величине не превосходят 10000. Формат выходных данных: В описанном выше формате выведите сумму многоугольников. Вершины должны следовать в порядке обхода против часовой стрелки, никакие две соседние стороны не могут лежать на одной прямой. Примеры:
Задача D. Факториал.
N! = 1 * 2 * 3 ... * N. Вычислите остаток от деления N! на N + 1. Формат входных данных: На первой строке входного файла записано число 1 <= N <= 2 000 000 000. Формат выходных данных: Выведите остаток от деления N! на N + 1. Примеры:
Задача E. Длинное число.
Вычеркните из натурального числа одну цифру так, чтобы получившееся число было минимальным и не имело ведущих нулей. Формат входных данных: На первой строке записано натуральное число в десятичной системе счисления, количество цифр которого не превосходит 200 000. Формат выходных данных: Выведите число, получившееся после вычеркивания цифры. Примеры:
Задача F. Промежутки.
Найдите объединение двух промежутков. Формат входных данных: Первая и вторая строки описывают промежутки: [a,b] - отрезок от a до b, (a,b) - интервал от a до b, [a,b) или (a,b] - полузамкнутые интервалы. -10000 <= a, b <= 10000. Ни один из промежутков не является пустым множеством. Пробелы между числами, скобками и запятыми отсутствуют. Все числа во входном файле целые. Формат выходных данных: Если объединение можно записать в виде одного промежутка, выведите этот промежуток. Если нет, выведите два промежутка в формате $a,b$ + $c,d$, a < c - здесь знак $ обозначает соответствующую скобку - [, ], ( или ). Пробелы между числами, скобками и запятыми необязательны. Примеры:
Задача G. Сумма.
Во входном файле записаны целые неотрицательные числа. Найдите минимальное целое неотрицательное число, которое нельзя представить в виде суммы этих чисел (каждое число можно использовать не более одного раза). Формат входных данных: На первой строке записано количество чисел 1 <= N <= 10000. На второй строке находятся сами числа. Формат выходных данных: Выведите искомое число. Примеры:
Задача H. Простой факториал.
Простым факториалом простого числа N называется произведение всех простых чисел от 2 до N. Определите, является ли данное число разностью двух простых факториалов. Формат входных данных: На первой строке записано натуральное число, количество цифр в котором не превосходит 5000. Формат выходных данных: Если данное число является разностью простых факториалов А и В (А > В), то выведите А. Если нет, то выведите -1. Примеры:
Комментарий:
Задача I. Эффект бабочки.
Во дворе находятся две круглые клумбы, устройство которых позволяет им пересекаться. Бабочка летит по прямой и хочет, чтобы ее путь имел ровно одну общую точку с каждой из клумб. Каким образом можно исполнить ее желание? Формат входных данных: В первой строке записаны координаты центра и радиус одной клумбы, на второй - координаты центра и радиус другой. Все числа целые и не превосходят по модулю 1000000. Формат выходных данных: На первой строке выведите количество различных путей. Если таких путей бесконечно много, выходном файле должно быть выведено единственное число -1. Будем задавать прямую уравнением a x + b y = c. Следующие строки должны содержать по три коэффициента - a, b и c, - описывающих прямые. Ответ будет проверяться с точностью до четырех знаков после запятой. Примеры:
Трансляция олимпиады, монитор соревнований, а также протокол сдачи решений будет осуществляться на сайте Физико-математического лицея № 30:
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|