Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Дом у дороги#29479

Министерство дорожного транспорта решило построить себе новый офис. Поскольку министр регулярно выезжает с инспекцией наиболее важных трасс, было решено, что офис министерства не должен располагаться слишком далеко от них.

Наиболее важные трассы представляют собой прямые на плоскости. Министерство хочет выбрать такое расположение для своего офиса, чтобы максимум из расстояний от офиса до трасс был как можно меньше.

Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта.

Входные данные

Первая строка входного файла содержит одно целое число n — количество наиболее важных трасс (1 ≤ n ≤ 10⁴ ).

Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x₁, y₁, x₂ и y₂ и представляет собой прямую, проходящую через точки (x₁, y₁) и (x₂, y₂) . Координаты заданных точек не превышают по модулю 10⁴. Точки (x₁ , y₁) и (x₂ , y₂) ни для какой прямой не совпадают.

Выходные данные

Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать 10⁹, гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.

Ответ должен иметь абсолютную или относительную погрешность не более 10⁻⁶, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения | x − y | / max(1, |y| ) не превышает 10⁻⁶.

Ввод	Вывод
4 0 0 0 1 0 0 1 0 1 1 2 1 1 1 1 2	0.5000000004656613 0.4999999995343387
7 376 -9811 376 -4207 6930 -3493 6930 -8337 1963 -251 1963 -5008 -1055 9990 -684 9990 3775 -348 3775 1336 7706 -2550 7706 -8412 -9589 8339 -4875 8339	4040.9996151750674 12003.999615175067

Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача D

Вычислительная геометрия Тернарный поиск

✓ 2✗ 381 300средняяВойти и решать

Про любовь...#29478

Паук и паучиха плывут по озеру на двух веточках. Плавать они не умеют, поэтому смогут встретиться только тогда, когда веточки соприкоснутся.

Считая, что веточки имеют форму отрезков, и что они плывут с постоянными скоростями, определите, сколько осталось ждать встречи несчастным членистоногим.

Входные данные

Входной файл содержит 12 чисел: x₁, y₁, x₂, y₂, x₃, y₃, x₄, y₄, v_1x, v_1y, v_2x, v_2y. Координаты вершин первого отрезка: (x₁, y₁) и (x₂, y₂), координаты вершин второго отрезка: (x₃, y₃) и (x₄, y₄), скорость первого отрезка (v1x, v1y), скорость второго отрезка (v2x, v2y). Все числа целые и не превосходят по модулю 104. В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.

Выходные данные

Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более 10⁻⁴. Если веточки не соприкоснутся никогда, выведите число -1.

Ввод	Вывод
0 0 -1 3 4 4 7 7 3 0 0 -1	1.6
0 0 -1 3 4 4 7 7 1 0 0 -3	-1

Тернарный поиск

✓ 11✗ 1001 300средняяВойти и решать

Архимедова спираль#29477

Дима недавно поступил на работу в НИИ Плоских Кривых. Как следует из названия этого научно- исследовательского института, он занимается различными исследованиями в области плоских кривых. Недавно Димин начальник Георгий столкнулся с весьма интересной кривой, которая, как выяснилось после некоторого исследования, известна под названием Архимедовой спирали. Архимедова спираль плоская кривая, изображающая траекторию точки M, которая равномерно движется вдоль луча OK с началом в O, в то время как сам луч OK равномерно вращается вокруг точки O (см. рисунок). Другими словами, расстояние до начала координат ρ = OM линейно зависит от угла поворота φ луча OK. При этом повороту луча OK на один и тот же угол соответствует одно и то же приращение расстояния ρ.

Движение точки M можно задать с помощью ряда параметров:

• начального угла поворота α луча OK (измеряется в градусах против часовой стрелки относительно положительного направления оси OX);

• угловой скорости вращения ω луча OK (измеряется в градусах за единицу времени);

• начального расстояния R от точки M до начала координат (точки O);

• скорости движения V точки M по лучу OK.

Если, задав эти параметры, не ограничить время движения точки M, то получится бесконечная кривая, исследовать которую достаточно трудно. Поэтому Дима решил ограничиться исследованием некоторой части этой кривой той, которая получается при движении точки M от нулевого момента времени до момента времени T. Задача, которую решает Дима состоит в поиске прямоугольника минимальной площади со сторонами, параллельными осям координат, в который ее можно вписать.

Требуется написать программу, которая найдет искомый прямоугольник

Входные данные

Входной файл содержит четыре целых числа: ω (1 ≤ ω ≤ 100), V (1 ≤ V ≤ 100), R (0 ≤ R ≤ 100) и T (1 ≤ T ≤ 1000). В этой задаче считается, что начальный угол поворота α равен нулю.

Выходные данные

В первой строке выходного файла выведите два вещественных числа — координаты левого нижнего угла искомого прямоугольника, а во второй строке — координаты правого верхнего угла искомого прямоугольника.

Ответ будет считаться правильным, если значение каждой из координат будет отличаться от истинного значения не более чем на 10-5.

Тернарный поиск

✓ 9✗ 261 200средняяВойти и решать

Самый младший#29446

В некотором списке записана информация о годе рождения каждого из N человек. Определить наибольший порядковый номер самого младшего по возрасту человека (считая с 1).

Входные данные
В первой строке задается число N - число человек (0<N<=50). Во второй строке задаются года рождения N человек (N чисел).

Выходные данные
Выведите наибольший номер самого младшего человека.

Пример

№	Входные данные	Выходные данные
1	5 1904 1903 1905 1905 1903	4

Алгоритмы обработки Линейный поиск Одномерные массивы

✓ 5 314✗ 16 008300лёгкаяВойти и решать

Проверка подпоследовательности#28420

Проверить, является ли последовательность подпоследовательностью заданного массива.

Входные данные

В первой строке входных данных содержится число N – длина заданной последовательности (1 ≤ N ≤ 10000). Во второй строке заданы члены исходной последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число M – длина подпоследовательности (1 ≤ M ≤ 10000). В четвертой строке задаются члены подпоследовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

Выходные данные
Вывести "YES" если последовательность заданная в 4-ой строке является подпоследовательность заданного массива и "NO", если не является.

Ввод	Вывод
10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 5 4 6 7 8 9 10	NO
10 1 2 3 4 5 6 7 8 9 10 9 1 2 3 5 6 7 8 9 10	YES

Пояснение.
Не путать "подпоследовательность" с "подстрокой".

"Два указателя"

✓ 364✗ 785500лёгкаяВойти и решать

Точки на прямой#28417

Маленький Петя очень любит точки. Недавно мама подарила ему n точек, лежащих на прямой OX. Пете стало интересно, сколькими способами он может выбрать три различные точки так, чтобы расстояние между двумя самыми удаленными из выбранных точек не превышало d.

Обратите внимание, что порядок точек внутри выбранной тройки значения не имеет.

Входные данные

Первая строка содержит два целых числа: n и d (1 ≤ n ≤ 10⁵; 1 ≤ d ≤ 10⁹). Следующая строка содержит n целых чисел x1, x2, ..., xn, по модулю не превосходящих 10⁹ — x-координаты точек, подаренных Пете.

Гарантируется, что координаты точек во входных данных строго возрастают.

Выходные данные

Выведите единственное целое число — количество троек точек, в которых расстояние между двумя самыми удаленными точками не превосходит d.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Ввод	Вывод
4 3 1 2 3 4	4
4 2 -3 -2 -1 0	2
5 19 1 10 20 30 50	1

В первом примере нам подходит любая тройка различных точек.

Во втором примере нам подходят всего 2 тройки: {-3, -2, -1} и {-2, -1, 0}.

В третьем примере нам подходит одна тройка: {1, 10, 20}.

"Два указателя"Комбинаторика

✓ 354✗ 711600лёгкаяВойти и решать

Расстояние между точками#28346

На окружности заданы N точек, надо найти пару точек, расстояние между которыми (по хорде окружности) максимально.

Входные данные

В первой строке задано N (1 <= N <= 100 000).

В следующей строке даны N пар вещественных чисел. Сначала описывается координата x, потом – y.

Выходные данные

Вывести два числа – номера точек, расстояние между которыми максимально. Сначала идет наименьшее число, потом наибольшее.

Ввод	Вывод
3 1.4142 1.4142 0 2 -1.4142 -1.4142	1 3

"Два указателя"геометрия сортировки

✓ 1✗ 4141 400средняяВойти и решать

Два одинаковых массива#28345

На вход подаются два массива A и В, отсортированных по неубыванию. Вам нужно узнать, существует ли такое число, которое содержится в обоих массивах. Если такое число существует, выведите 1, иначе выведите 0.

Входные данные
В первой строке записано натуральные числа N и M– количество элементов первого и второго массива соответственно, (1 <= N, M <= 10⁸). В следующих двух строках записаны элементы массива A и B. Во второй строке - элементы массива A, в третьей - элементы массива B. Все элементы массива неотрицательные числа, не превышающие 10¹⁸.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	4 4 1 2 3 4 2 4 7 8	1

"Два указателя"Хеш

✓ 815✗ 1 981500лёгкаяВойти и решать

Пары точек#28344

На прямой находятся N точек. Требуется подсчитать количество пар индексов (i, j) таких, что i не равно j и |a_i - a_j| <= D.

Формат входных данных
В первой строке находятся два числа N и D (1 <= N <= 10⁵, 1 <= D <= 10⁹). Во второй строке находится N неотрицательных чисел, каждое из котороых не более чем 2*10⁹.

Формат выходных данных
Выведите на экран ответ на задачу.

"Два указателя"Использование сортировки

✓ 530✗ 2 802600лёгкаяВойти и решать

Метод двух указателей#28341

Дан массив из N положительных чисел. Найти в нем минимальное количество подряд идущих чисел, таких что их сумма больше K.

Входные данные
В первой строке записано число N, во второй - K (0<N<= 10⁶, 0<=K<= 10⁹). В третьей строке записаны натуральные числа последовательности.

Выходные данные
Выведите длину наименьшей последовательности чисел, сумма которых больше K. Если такой последовательности найдено не будет, то выведите -1.

Примеры

№	Входные данные	Выходные данные
1	6 7 3 1 3 2 4 3	3

"Два указателя"

✓ 940✗ 3 654400лёгкаяВойти и решать

Стильная одежда - 2#28333

Глеб обожает шоппинг. Как-то раз он загорелся идеей подобрать себе кепку, майку, штаны и ботинки так, чтобы выглядеть в них максимально стильно. В понимании Глеба стильность одежды тем больше, чем меньше разница в цвете элементов его одежды.

В наличии имеется \(N_1\) кепок, \(N_2\) маек, \(N_3\) штанов и \(N_4\) пар ботинок (\(1 \le N_i \le 100\,000\)). Про каждый элемент одежды известен его цвет (целое число от 1 до \(100\,000\)). Комплект одежды — это одна кепка, майка, штаны и одна пара ботинок. Каждый комплект характеризуется максимальной разницей между любыми двумя его элементами. Помогите Глебу выбрать максимально стильный комплект, то есть комплект с минимальной разницей цветов.

Формат входных данных
Для каждого типа одежды \(i\) (\(i = 1, 2, 3, 4\)) сначала вводится количество \(N_i\) элементов одежды этого типа, далее в следующей строке — последовательность из \(N_i\) целых чисел, описывающих цвета элементов. Все четыре типа подаются на вход последовательно, начиная с кепок и заканчивая ботинками. Все вводимые числа целые, положительные и не превосходят \(100\,000\).

Формат выходных данных
Выведите четыре целых числа — цвета соответственно для кепки, майки, штанов и ботинок, которые должен выбрать Глеб из имеющихся для того, чтобы выглядеть наиболее стильно. Если ответов несколько, выведите любой.

"Два указателя"

✓ 247✗ 450700средняяВойти и решать

Город Че#28332

В центре города Че есть пешеходная улица - одно из самых популярных мест для прогулок жителей города. По этой улице очень приятно гулять, ведь вдоль улицы расположено n забавных памятников.

Девочке Маше из города Че нравятся два мальчика из ее школы, и она никак не может сделать выбор между ними. Чтобы принять окончательное решение, она решила назначить обоим мальчикам свидание в одно и то же время. Маша хочет выбрать два памятника на пешеходной улице, около которых мальчики будут ее ждать. При этом она хочет выбрать такие памятники, чтобы мальчики не увидели друг друга. Маша знает, что из-за тумана мальчики увидят друг друга только в том случае, если они будут на расстоянии не более r метров.

Маше заинтересовалась, а сколько способов есть выбрать два различных памятника для организации свиданий.

Входные данные

В первой строке находятся два целых числа n и r (2<=n<=300 000, 1<=r<=10⁹) - количество памятников и максимальное расстояние, на котором мальчики могут увидеть друг друга.

Во второй строке задано n положительных чисел d1 ... dn, где di - расстояние от i-го памятника до начала улицы. Все памятники находятся на разном расстоянии от начала улицы. Памятники приведены в порядке возрастания расстояния от начала улицы (1<=d1 <d2< ... < dn<=10⁹).

Выходные данные

Выведите одно число - число способов выбрать два памятника для организации свиданий.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 4 1 3 5 8	2	В приведенном примере Маша может выбрать памятники 1 и 4 или памятники 2 и 4.

"Два указателя"

✓ 541✗ 1 138500лёгкаяВойти и решать

Красота превыше всего#28331

В парке города Питсбурга есть чудесная аллея, состоящая из N посаженных в один ряд деревьев, каждое одного из K сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из K видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.

Входные данные

В первой строке входного файла находятся два числа N и K ( 1 ≤ N , K ≤ 250000 ). Во второй строке входного файла следуют N чисел (разделенных пробелами), i -ое число второй строки задает цвет i -ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета

Выходные данные

В выходной файл выведите два числа, координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите любой.

Ввод	Вывод
5 3 1 2 1 3 2	2 4
6 4 2 4 2 3 3 1	2 6

"Два указателя"

✓ 222✗ 833800средняяВойти и решать

Ближайшее число#28311

Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.

Формат входных данных

В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке содержатся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000). В третьей строке вводится одно целое число x, не превосходящее по модулю 1000.

Формат выходных данных
Вывести значение элемента массива, ближайшее к x. Если таких чисел несколько, выведите любое из них.

Бинарный поиск

✓ 1 515✗ 4 930400лёгкаяВойти и решать

27309#27309

Вы должны реализовать алгоритм или структуру данных, эффективно реализующих следующие запросы:

1)Добавление в массив элемента

2)Извлечение k-того по величине элемента массива (первым по величине будет считаться наименьший элемент)

Гарантируется, что каждый элемент встречается в массиве всего один раз

Входные данные:

В первой строке указано натуральное число n, за ним следует n целых чисел.

Далее вводится натуральное m - количеств запросов.

В каждой из следующих m строк содержится слово "add" или "get" и целое число k.

Все численные значения по модулю не превосходят 1000.

В первом случае вы должны дополнить массив элементом со значением k. Иначе - вывести k-тый элемент отсортированного текущего массива (индексация с единицы).

Выходные даннные:

Вы должны ответить на запрос извлечения k-того элемента массива, а именно вывести его значение на экран.

Двоичное дерево поиска Порядковые статистики

✓ 0✗ 41 300средняяВойти и решать

Ski Course Rating#27302

Лыжный маршрут описывается M x N решеткой высот (1 <= M,N <= 500), каждая высота в интервале 0 .. 1,000,000,000.

Некоторые из этих ячеек помечены как стартовые точки маршрута. Организаторы хотят вычислить рейтинг трудности каждой стартовой точке. Рейтинг трудности стартовой точки P – это минимальное число D такое, что корова сможет успешно достичь как минимум T ячеек решётки (1 <= T <= MN), если она стартует в P и может двигаться в соседнюю ячейку (на север, юг, запад или восток), только если абсолютная величина разности высот в этих ячейках не превосходит D.

Вычислите рейтинг трудности для каждой стартовой точки и выведите их сумму.

INPUT FORMAT:

* Строка 1: Целые числа M, N, T.

* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.

* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин равных 0 или 1, где 1 означает, что это ячейка – стартовая точка

OUTPUT FORMAT:

* Строка 1: Сумма рейтингов трудности всех стартовых точек (заметим, что это число может не поместиться в 32-битное целое, даже если каждый рейтинг в отдельности поместится).

INPUT DETAILS:

Местность описывается решеткой из 3 х 5 высот.

Верхняя левая и правая нижняя ячейки являются стартовыми точками.

Из каждой стартовой точки мы должны быть способны добраться до 10 ячеек.

OUTPUT DETAILS:

Рейтинг трудности верхнего левого угла равен 4.

Рейтинг трудности правого нижнего угла равен 20.

Ввод	Вывод
3 5 10 20 21 18 99 5 19 22 20 16 17 18 17 40 60 80 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1	24

Бинарный поиск по ответу графы Поиск компонент связности

—Войти и решать

Малыш и Карлсон#27293

Малыш может съесть банку варенья за А₁ минут, корзину печенья за B₁ минут, выпить бутылку молока за C₁ минут. А Карлсон может сделать это за A₂, B₂, C₂ минут соответственно. Напишите программу, вычисляющую, за какое минимальное время они смогут покончить с завтраком, состоящим из банки варенья, корзины печенья и бутылки молока?

В первой строке входного файла содержится три целых числа, разделенных пробелами – значения параметров A₁, B₁, C₁. Во второй строке входного файла содержится три целых числа, разделенных пробелами – значения параметров A₂, B₂, C₂. Все числа в диапазоне от 1 до 10⁶.

В выходной файл вывести одно число – минимальное время завтрака с точностью 10⁻⁵.

Ввод	Вывод
13 10 14 6 6 7	12.00000

(с) Южно-Уральский открытый командный чемпионат, 2006

Бинарный поиск по ответу Задачи на моделирование

✓ 5✗ 1231 200средняяВойти и решать

Деление пополам#27290

Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a.

Для решения используйте метод деления отрезка пополам.

Входные данные

Число a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после запятой. Число n – натуральное, не превосходящее 10. Каждое число вводится в отдельной строке.

Выходные данные

Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.

Примеры

№	Входные данные	Выходные данные
1	2 2	1.41421356237

Бинарный поиск значения функции

✓ 376✗ 1 482500лёгкаяВойти и решать

Двоичный поиск для монотонной функции (С++)#27283

Дано натуральное число x. Вычислите кубический корень из числа.

Формат входных данных

Число x – натуральное, не превосходящее \(10^6\).

Формат выходных данных

Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.

Примеры

№	Входные данные	Выходные данные
1	2	1.259921

Бинарный поиск значения функции

✓ 83✗ 203800средняяВойти и решать

Paired Up#27220

Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить M своих коров (M <= 10⁹, M - чётное) на M/2 пар. Каждую из этих пар он помещает в отдельное стойло, и все пары коров доятся одновременно.

Каждая из коров даёт различное количество молока. Если коровы в паре дают по A и B литров молока, то для дойки этой пары требуется A+B единиц времени.

Помогите ФД определить минимально возможное количество времени на весь процесс дойки, в предположении, что коровы разбиты на пары наилучшим образом.

Входные данные

Первая строка ввода содержит N (1 <= N <= 100000). Каждая из следующих N строк содержит два целых числа x и y, указывающих, что у ФД есть x коров с производством молока по y (1 <= y <= 10⁹) литров. Сумма всех x-ов есть M- общее количество коров.

Выходные данные

Выведите минимальное количество времени, которое займёт дойка всех коров, в предположении, что они разбиты на пары оптимальным образом.

Примеры

№	Входные данные	Выходные данные
1	3 1 8 2 5 1 2	10

"Два указателя"Жадный алгоритм

✓ 98✗ 387800средняяВойти и решать