Новогодняя вечеринка проходит в плоском прямоугольном зале с координатами левого нижнего угла (0, 0),
а правого верхнего — (1000, 1000).
С потолка зала свешивается мишура в виде N прямых тонких вертикальных лент
с координатами нижних концов (xi, yi).
Один из гостей запустил мыльный пузырь радиуса R.
Первоначально центр пузыря находился в точке (x, R).
Пузырь полетел вертикально вверх до столкновения с
лентой мишуры или потолком, после чего лопнул.
Требуется определить, с чем именно он столкнулся.
Формат входного файла
В первой строке входного файла содержатся числа NRx, в следующих N строках
содержатся вещественные числа xiyi.
Числа в строке разделены пробелами. Значения всех xi во входном файле различны.
Формат выходного файла
В выходном файле должно содержаться единственное число — номер ленты (во входном файле), либо 0 (нуль),
если пузырь долетел до потолка. Если пузырь одновременно столкнулся с несколькими лентами (и, возможно, потолком),
вывести номер самой левой ленты.
31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний
ужин, и теперь они с нетерпением ждут Нового года.
Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут
осталось до Нового года. При этом на вычисление у них уходит
много времени.
Поэтому им хотелось бы иметь компьютерную программу, принимающую на вход
текущее время (часы и минуты) и вычисляющую, сколько
времени осталось до Нового года.
Число секунд в текущем времени принять равным 0.
Формат входного файла
Входной файл содержит текущее время — часы и минуты.
Формат выходного файла
Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.
В детском саду города N для празднования Нового Года установили ёлку
и для её украшения закупили K елочных игрушек.
Елочные игрушки характеризуются двумя параметрами — массой и красотой.
Елка характеризуется тремя параметрами — максимальной массой игрушек,
которую она может выдержать, красотой, а также максимальной перегрузкой
в одну из сторон (максимальная разница между суммарной массой игрушек
на левой и на правой стороне).
Красота елки равна сумме красот всех висящих на ней игрушек.
Так как дети хотят удивить Деда мороза, они хотят как можно красивее
украсить ёлку, при этом она не должна упасть.
Вас просят написать программу, которая по заданным параметрам игрушек и ёлки
определит максимально возможную красоту наряженной ёлки.
Формат входного файла
Во входном файле содержатся числа MKΔ — соответственно максимальная
масса игрушек на ёлке, количество купленных игрушек и максимальное отклонение.
За ними следуют K пар чисел viki соответственно вес и красота i-той игрушки.
Формат выходного файла
В выходном файле должно содержаться единственное число - максимально
возможная красота наряженной ёлки.
Последовательность целых чисел b1, b2, …, bK назовём плотной,
если после сортировки по возрастанию она превратится в последовательность
x, x + 1, …, x + K − 1 для некоторого целого x.
Например, последовательности 1, 2 и 7, 6, 8, 5 являются плотными,
а последовательности 1, 1, 2 и 1, 5, 2, 3 — нет.
Дана последовательность из N целых чисел a1, …, aN.
Требуется определить такие два индекса 1 ≤ i ≤ j ≤ N, что:
подпоследовательность ai, ai + 1, …, aj является плотной;
длина подпоследовательности j − i + 1 является максимально возможной;
индекс i — наименьший среди всех подпоследовательностей, удовлетворяющих
предыдущим условиям;
Рекомендуется рассмотреть частичные решения
1 ≤ N ≤ 500
1 ≤ ai ≤ 106
Формат входного файла
Входной файл содержит целое число N, за которым следуют N целых чисел
a1… aN.
Формат выходного файла
Выходной файл должен содержать два целых числа — индексы i и j.
Дима недавно начал изучать информатику.
Одним из первых алгоритмов, который он изучил, был алгоритм Евклида
для нахождения наибольшего общего делителя (НОД) двух чисел.
Напомним, что наибольшим общим делителем двух чисел a и b называется
наибольшее натуральное число x, такое, что и число a,
и число b делится на него без остатка.
Алгоритм Евклида заключается в следующем:
Пусть a, b — числа, НОД которых надо найти.
Если b = 0, то число a — искомый НОД.
Если b > a, то необходимо поменять местами числа a и b.
Присвоить числу a значение a − b.
Вернуться к шагу 2.
Дима достаточно быстро освоил алгоритм Евклида и вычислил с его помощью
много наибольших общих делителей. Наконец, ему пришла идея решить новую задачу.
Пусть заданы числа a, b, c и d.
Требуется узнать, наступит ли в процессе реализации алгоритма Евклида
для заданной пары чисел (a, b) такой момент,
когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.
Рекомендуется рассмотреть частичные решения
a, b ≤ 106
Формат входного файла
Первая строка входного файла содержит количество
наборов входных данных k. Далее идут описания этих наборов.
Каждое описание состоит из двух строк.
Первая из них содержит два целых числа ab, а вторая — два целых числа: cd.
Формат выходного файла
Для каждого набора входных данных выведите в отдельной строке выходного файла
слово "YES", если в процессе применения алгоритма Евклида к паре чисел (a, b)
в какой-то момент получается пара (c, d), или слово "NO" в противном случае.
Новогодняя вечеринка проходит в плоском прямоугольном зале с координатами левого нижнего угла (0, 0),
а правого верхнего — (1000, 1000).
С потолка зала свешивается мишура в виде N прямых тонких вертикальных лент
с координатами нижних концов (xi, yi).
Один из гостей запустил мыльный пузырь радиуса R.
Первоначально центр пузыря находился в точке (x, R).
Пузырь полетел вертикально вверх до столкновения с
лентой мишуры или потолком, после чего лопнул.
Требуется определить, с чем именно он столкнулся.