Единственный способ попасть в Зал Круглых Столов – пройти через Колонный Коридор. Стены Коридора изображаются на карте прямыми линиями, которые параллельны оси OY системы координат. Вход в Коридор находится снизу, а выход из Коридора в Зал – сверху. В Коридоре есть цилиндрические (на карте круглые) Колонны одинакового радиуса R.
Напишите программу, которая по информации о размерах Коридора, и размещения Колонн определяет диаметр наибольшего из Круглых Столов, который можно пронести через такой Коридор, сохраняя поверхность Стола горизонтальной.
В первой строке входного файла заданы два числа XL и XR – x-координаты левой и правой стен Коридора. Во второй строке находится целое число R (1≤R≤1 000 000) – радиус всех Колонн. В третей – целое число N (1≤N≤200), которое задает количество Колонн. Далее следуют N строк, в каждой из которых по два числа – x- и y-координаты центра соответствующей Колонны.
Все входные координаты – целые числа, которые по модулю не превосходят 1 000 000.
Единственная строка выходного файла должна содержать одно число – искомый диаметр наибольшего Стола. Диаметр следует выводить с точностью 3 знака после десятичной точки (даже в случае, когда он окажется целым). Если нельзя пронести ни одного Стола, то ответ должен быть: 0.000
Точность 3 знака после точки, по обычным правилам округления, обозначает, что ответ, который выдается в выходной файл, должен отличаться от точного не более чем на 510-4 (т.е. на 0.0005). Например, если точный ответ 1.234567, то в файле должно находится число 1.235. Если точный ответ 5.0005, то необходимо округлять в большую сторону, т.е. в файл следует выдать 5.001
0 90 3 4 10 10 70 10 50 50 10 90
47.000
>Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных открытий:
Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.
Напишите программу, которая по номерам двух видов вычислит номер вида их ближайшего общего предка в дереве эволюции.
Первая строка входного файла содержит целое число N (1≤N≤100) – количество этапов эволюции, которые произошли на планете Олимпия до текущего времени. Вторая и третья строки файла содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка.
Единственная строка выходного файла должна содержать натуральное число – номер ближайшего предка для двух видов.
4 15 12
3
18 233016 233008
14563
На плоскости заданы N разных окружностей. Две окружности пересекаются, если они имеют хотя бы одну общую точку.
Напишите программу, которая по координатам центров окружностей и их радиусам найдет пару пересекающихся окружностей.
В первой строке входного файла содержится целое числоN (1≤N≤10 000) . В каждой из последующих N строк содержатся три натуральных числа X, Y, R меньших 10 000, которые задают координаты центра окружности (X, Y) и его радиус R.
Единственная строка выходного файла должна содержать пару номеров пересекающихся окружностей, либо единственное число 0, если никакие две окружности не пересекаются. Окружности нумеруются соответственно порядку во входном файле, начиная с 1 до N. Если существует несколько пар пересекающиеся окружностей, выведите любую из них. Элементы пары могут быть выведены в произвольном порядке.
5 5 10 4 6 20 3 10 15 3 12 8 2 13 13 1
5 3
Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости \(N\) квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.
Напишите программу, которая по количеству квадратов \(N\), которые необходимо составить, находит минимальное необходимое для этого количество спичек.
Единственная строка входного файла содержит одно целое число \(N\) (1≤\(N\)≤\(10^9\)).
Единственная строка выходного файла должна содержать одно целое число – минимальное количество спичек требуемых для составления заданного количества квадратов.
4
12
Задано прямоугольную таблицу размером \(M\) строк на \(N\) столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.
Будем снисходительными к Путнику, считая «хорошими» не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на \(K\).
Количество «хороших» путей гарантированно не превышает \(10^9\).
Напишите программу, находящую значение максимально возможной суммы и количества «хороших» путей.
Первая строка входного файла содержит три целых числа \(M\) (2≤\(M\)≤200), N (2≤\(N\)≤200) и \(K\) (0≤\(K\)≤200). Каждая из последующих \(M\) строк содержит \(N\) чисел, записанных в соответствующих клеточках.
Первая строка выходного файла должна содержать максимальную возможную сумму; вторая строка – количество маршрутов, сумма чисел которых отличается от максимальной не более чем на \(K\).
2 3 3 1 9 7 2 5 3
20 2