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

Load Balancing#29545

Коровы Фермера Джона стоят в различных точках (x₁,y₁)…(x_n,y_n) его поля (1≤N≤100,000, все x_i и y_i - положительные нечётные целые числа, не превышающие 1,000,000. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x=a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y=b, где b - чётное целое. Эти две изгороди пересекаются в точке (a,b), и вместе делят поле на четыре региона.

ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть M - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы M было как можно меньше. Помогите ФД определить это минимально возможное значение для M.

ФОРМАТ ВВОДА:

Первая строка ввода содержит одно целое число, N. Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y.

ФОРМАТ ВЫВОДА:

Выведите минимально возможное значение M, которое может достичь ФД оптимальным расположением изгородей.

Ввод	Вывод
7 7 3 5 5 7 13 3 1 11 7 5 3 9 1	2

✓ 3✗ 251 100средняяВойти и решать

Вложенный вложенный тернарный поиск: Космические спасатели#29495

В галактике находится n планет, на каждой из которых обитают множество различных живых существ. И каждое из них может оказаться в беде! Космические спасатели прекрасно знают об этом и всегда готовы помочь каждому, кому эта помощь действительно понадобится. Стоит только позвать.

Сейчас космические спасатели планируют построить самую большую в истории галактики спасательную базу, однако месторасположение будущей базы пока еще не определено. Поскольку помощь иногда требуется абсолютно неотложно, спасатели стремятся найти такую точку в галактике, из которой можно было бы добраться до самой удаленной планеты за наименьшее возможное время. Другими словами, необходимо найти такую точку в пространстве, чтобы расстояние от нее до самой удаленной от нее планеты было наименьшим из всех возможных точек в пространстве. К сожалению, они не в силах решить такую задачу.

Поскольку планеты достаточно удалены друг от друга, их можно считать точками в евклидовом трехмерном пространстве. Расстояние между точками (x_i, y_i, z_i) и (x_j, y_j, z_j) вычисляется по формуле:

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

Галактика в опасности! Спасите космических спасателей и укажите им искомую точку.

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

В первой строке входного файла содержится целое число n — количество планет (1 ≤ N ≤ 100). Каждая из последующих n строк содержит информация о планетах. i-я из этих строк содержит три целых числа xi, yi, zi — координаты i-й планеты ( - 10⁴ ≤ xi, yi, zi ≤ 10⁴, 1 ≤ i ≤ n). Никакие две планеты не совпадают.

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

В первой строке выходного файла следует вывести три вещественных числа через пробел x₀, y₀, z₀ — координаты будущей базы. Если существует несколько решений, то разрешается вывести любое. Ответ будет засчитан, если расстояние от данной точки до самой удаленной планеты будет отличаться от результата жюри не более чем на 10^-6 по абсолютному или относительному значению.

Ввод	Вывод
5 5 0 0 -5 0 0 0 3 4 4 -3 0 2 2 -2	0.000 0.000 0.000

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

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

Вложенный тернарный поиск: футбольные ворота#29484

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

Соня, конечно, хочет забить как можно больше голов. Поэтому она решила сделать ворота максимальной площади. Стандартные футбольные ворота имеют прямоугольную форму, но Соня — человек креативный, и она считает, что ворота могут иметь форму произвольного четырёхугольника.

Можно считать, что берёза является отрезком прямой и растёт строго перпендикулярно земле.

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

В единственной строке записаны целые числа a, b — длины палок (\(1 <= a, b <= 10 000\)). Известно, что суммарная длина палок строго меньше высоты берёзы.

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

Выведите максимальную площадь ворот, которые можно соорудить из палок и берёзы. Ответ следует вывести с точностью не менее шести знаков после десятичной точки.

Примеры

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

Источник: Уральская региональная командная олимпиада по программированию 2011

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

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

Велогонка#29480

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на x₁, x₂, ..., x_n метров (n – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью v₁, v₂, ..., vn метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

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

Требуется написать программу, которая по заданному количеству велосипедистов n, заданным начальным положениям велосипедистов x₁, x₂, ..., x_n и их скоростям v₁, v₂, ..., vn, вычислит момент времени t, в который расстояние l между лидирующим и замыкающим велосипедистом будет минимальным.

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

Первая строка входного файла содержит целое число n – количество велосипедистов.

В последующих n строках указаны по два целых числа: x_i – расстояние от старта до i-го велосипедиста в начальный момент времени (0 ≤ x_i ≤ 10⁷ ) и v_i – его скорость (0 ≤ v_i ≤ 10⁷ ).

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

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

Числа t и l должны иметь абсолютную или относительную погрешность не более 10^–6, что означает следующее. Пусть выведенное число равно x, а в правильном ответе оно равно y. Ответ будет считаться правильным, если значение выражения |x – y| / max(1, |y| ) не превышает 10^–6.

Подзадачи и система оценки

Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Ввод	Вывод
3 0 40 30 10 40 30	1 30
5 90 100 100 70 100 70 110 60 120 35	0.5 5.000000000000

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

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

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

Красота превыше всего#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средняяВойти и решать

Двоичный поиск для монотонной функции (С++)#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средняяВойти и решать

Транспортировка#27126

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. Нато, чтобы довезти кружки от завода-изготовителя до ЛКШ,остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.

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

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

Алгоритм Дейкстры Бинарный поиск по ответу

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

Путь в никуда#24761

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^oвправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

Утром Колобок решил проанализировать свой сон. Он догадался, что в каждой клетке он был максимум один раз, но никак не может вспомнить, сколько клеток он посетил. Колобок просит вас написать программу, которая посчитает количество посещённых им клеток.

Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

Формат выходного файла
В выходной файл выведите одно число — количество клеток, посещенных Колобком во сне.

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.

Бинарный поиск Деревья Префиксные суммы(минимумы, ...)Разреженные таблицы (sparse table)Структуры данных

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

Cipher#24728

Корвину удалось перехватить n сообщений о перемещении войск Эрика. Правда, они оказались зашифрованными, но это не беда! Вы ведь поможете ему расшифровать эти сообщения? Это должно быть не сложно, ибо Корвин знает хотя бы одну подстроку в каждом исходном сообщении.

Известно, что для шифровки Эрик использует шифр Цезаря, то есть шифр, в котором буква с номером i заменяется на букву с номером i + k, где k - некоторое число.

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

Каждое сообщение имеет длину x, а каждая известная подстрока его расшифровки - y.

Ваша цель - восстановить все изначальные сообщения.

СДАВШИЙ С ПОМОЩЬЮ STD::STRING ОТПРАВИТСЯ ВО ДВОРЫ ХАОСА!!!

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

В первой строке считываются числа n (\(1 <= n <= 100\)) и q (\(1 <= k <= 100\))

В следующих 3 * n строках содержатся числа x_i, y_i (\(1 <= b_i <= a_i <= 100\)) и 2 массива с числами, являющиеся сообщением и его подстрокой его расшифровки.

Выходные данные
В строке номер i выведите расшифрованный вариант сообщения с номером i.
В конце этой строки пробела быть НЕ ДОЛЖНО

Примеры

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

Z-функция. Префикс-функция Поиск подстроки в строке реализация

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