На открытие магистрали собрались все грешники (в Аду не часто происходит что-то новое). Они сразу же разбрелись по ней и стали изучать, как устроена магистраль. Один из дозорных ангелов сразу же заметил, что в аду как-то пусто, и немедленно доложил об этом главному надзирателю. Главный надзиратель не растерялся и тут же отдал приказ уничтожить пустые круги Ада, который тотчас же был исполнен.
Дьяволу это крайне не понравилось, и он решил определить новое место на магистрали и создать новые круги Ада. Для оптимизации работ все грешники должны сразу оказаться на каких-то кругах, чтобы их потом не пришлось перемещать туда-сюда. Конечно, создание каждого круга требует много сил, поэтому Дьявол решил создать минимальное количество кругов (мы всё ещё помним, что они являются окружностями), причём центры кругов должны находиться ровно в той новой точке, которую определил Дьявол.
С учетом сказанного, необходимо помочь Дьяволу найти такую новую точку.
Требуется написать программу, которая решает поставленную задачу.
Формат входных данных
Первая строка входного файла содержит число грешников п (1 ≤ п ≤ 200 000). На следующей строке заданы п целых чисел — координаты грешников на магистрали, по модулю не превосходящие 60 000.
Формат выходных данных
В первой строке выходного файла требуется вывести вещественную координату новой тоски, выбранной Дьяволом. Вторая строка должна содержать минимальное количество кругов, необходимое для возвращения всех грешников на круги своя. В третьей строке требуется разместить разделённые пробелами вещественные радиусы кругов.
Следует заметить, что круги могут иметь нулевой радиус.
Если правильных ответов несколько, можно вывести любой из них. Для всех точек минимальное расстояние до найденных окружностей не должно превышать 10-6.
Примеры
Задача D. Слон на тороидальной шахматной доске
Имя входного файла: torobishop. in
Имя выходного файла: torobishop. out
Ограничение по времени: 2 секунда
Ограничение по памяти: 256 мебибайт
Как известно, не все спортивные программисты любят шахматы. Ещё меньше поклонников среди участников олимпиад по программированию у шахмат на тороидальной доске. Тем не менее, рассмотрим тороидальную шахматную доску размера п × т. От обыкновенной доски того же размера она отличается тем, что ее верхняя горизонталь соединена с нижней, а левая вертикаль с правой.
Горизонтали и вертикали тороидальной доски пронумерованы последовательно натуральными числами от 1 до п снизу вверх и от 1 до т слева направо, соответственно. Каждая клетка имеет координату, образованную упорядоченной парой (номер горизонтали, номер вертикали).
В клетку с координатой (x1, y1) поместим слона. Напомним, слоны в шахматах перемещаются по диагонали на любое количество клеток за ход. К тому же, диагонали на тороидальной доске не такие, как на обычной. Например, из клетки (п, т) можно попасть в клетку (1, 1) за один ход (на одну клетку по диагонали вправо вверх).
Если требуется переместить слона из клетки (x1, y1) в клетку (x2, y2) как можно быстрее (за наименьшее количество ходов), то возникает вопрос, какое минимальное количество ходов требуется сделать слоном, чтобы он оказался в новой клетке. Если попасть в клетку (x2, y2) из клетки (x1, y1) коню невозможно, то необходимо знать об этом заранее, чтобы не перемещать слона зря.
Требуется написать программу, которая позволит решить поставленную задачу.
Формат входных данных
В одном входном файле может описываться сразу несколько ситуаций.
Первая строка входного файла содержит число t — количество описанных ситуаций (1 ≤ t ≤ 100).
Каждая ситуация задаётся на трёх строках следующим образом:
в первой строке через пробел записаны два целых числа п (1 ≤ п ≤ 105) и т (1 ≤ т ≤ 105);
во второй строке записаны координаты слона (x1, y1);
в третьей строке записаны координаты клетки (x2, y2) (1 ≤ xi ≤ п, 1 ≤ yi ≤ т).
Формат выходных данных
Для каждой ситуации необходимо вывести единственное число — минимальное количество ходов, которое требуется на то, чтобы слону попасть из начального положения в клетку (x2, y2). Если слону попасть в клетку (x2, y2) невозможно, то следует вывести число –1.
Примеры
5. Описание заданий для пятого интернет-тура
На пятом туре было предложено 5 задач: задача A «Ориентированный граф», задача B «Какуро», задача C «Решётка», задача D «Кактусы» и задача E «Разбиения на пары». Тексты задач представлены ниже.
Задача A. Ориентированный граф
Имя входного файла: graph. in
Имя выходного файла: graph. out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мебибайта
На уроке информатики изучается ориентированный граф. Изначально граф пустой. Каждый раз у графа появляется новое направленное ребро, и ученики могут поинтересоваться кратчайшим расстоянием от первой вершины графа до заданной вершины.
Требуется написать программу, которая дает ответ на поставленный вопрос.
Формат входных данных
В первой строке записаны два числа – количество вершин в графе п (1 ≤ п ≤ 1000) и т (1 ≤ т ≤ 300 000).
Каждая из последующих т строк может быть одного из следующих двух типов:
1) «+ i j» означает добавление к графу ребра, идущего из вершины i в вершину j (1 ≤ i, j ≤ п).
2) «? i» означает запрос учеников о кратчайшем расстоянии (выраженном числом рёбер) от вершины 1 до вершины i.
Формат выходных данных
Ответы на запросы учеников о расстояниях выводятся по одному на строке. В случае если в момент запроса путь от вершины 1 до указанной вершины не существует, необходимо вывести в соответствующей строке число (–1).
Пример
Какуро
Имя входного файла: kakuro. in
Имя выходного файла: kakuro. out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мебибайта
Какуро — головоломка с числами, которую можно назвать математическим аналогом кроссворда. Название Какуро происходит от сокращения японского названия kasan kurosu (перекрёстное сложение). В США головоломка также известна под названием «Cross Sums» («Пересекающиеся суммы»).
Игра заключается в следующем. Поле состоит из клеток чёрного и белого цвета. Несколько белых клеток, идущих подряд по горизонтали или по вертикали, называются блоком. Про каждый блок известна сумма цифр, которые должны стоять в этом блоке.
Во все белые клетки нужно вписать по одной цифре от 1 до 9 так, чтобы, во-первых, сумма цифр в каждом блоке сошлась с указанным числом, а во-вторых, чтобы в каждом блоке все цифры были различны.
Требуется написать программу, решающую данную задачу.
Формат входных данных
В первой строке входного файла заданы два целых числа W и Н — количество столбцов и строк, соответственно. Во второй строке находится целое число N — количество блоков в головоломке.
В каждой из следующих N строк находятся описания блоков, по одному в строке. Каждое описание состоит из пяти целых чисел. Первые четыре из них задают нижнюю-левую и верхнюю-правую клетки блока, пятое — сумму цифр в этом блоке. Нумерация ведется от 1 до W по горизонтали и от 1 до Н по вертикали.
Ограничения: 2 ≤ W, Н ≤ 11, 1 ≤ N ≤ 25.
Одна из размерностей каждого блока равна 1, другая всегда больше 1. Блоки одинаковой ориентации не могут иметь общих клеток.
Формат выходных данных
Если решение существует, необходимо вывести Н строк по W чисел. Если на соответствующей клетке в решении стоит одна из цифр от 1 до 9, следует вывести её. Иначе на этой позиции следует вывести 0.
Если решение неоднозначно, разрешается выводить любое.
Если решения не существует, следует вывести «No solution» (без кавычек).
Программы, всегда выводящие «No solution», будут оценены в 0 баллов.
Примеры
Задача C. Решётка
Имя входного файла: lattice. in
Имя выходного файла: lattice. out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мебибайта
Рассмотрим на плоскости два линейно независимых целочисленных вектора a и b. Назовем решёткой множество векторов вида pa + qb, где p и q — целые числа.
Требуется написать программу, которая находит в описанной решетке кратчайший ненулевой вектор.
Формат входных данных
В первой строке входного файла находятся четыре целых числа—координаты векторов a и b соответственно (ax, ay, bx, by). Все координаты не превосходят по модулю 1050.
Формат выходных данных
Выходной файл должен содержать числа p и q, которые задают кратчайший ненулевой вектор. Гарантируется, что существует такой оптимальный ответ, что p и q по модулю не превышают 10200. Именно такие p и q необходимо выводить.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 |
