--->
8 задач
<---
Источники
#111273
Темы:
[Тернарный поиск]
[Бинарный поиск]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2012,
Лига А,
Задача H
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
6 megabytes
Спортивный программист для достижения вершин своего мастерства должен быть натренирован в совершенно разных аспектах, в том числе и физически. Кто-то для этого садится на велосипед, кто-то ныряет в бассейн, а молодой программист Влад бегает по стадиону. Но из-за неаккуратного обращения с личными вещами его секундомер может измерять время только в минутах, без указания секунд и тем более их долей.
Чтобы следить за прогрессом своего ученика, тренеру Влада приходится довольствоваться показаниями этого прибора. Каждый раз, когда Влад пробегает мимо тренера, сделав очередной круг по стадиону, тот записывает в блокнот показания секундомера в минутах. Фактически показания секундомера соответствуют целому числу минут, прошедших к определенному моменту времени. Причём, если секундомер показывает, например, 1, то это может обозначать и время ровно 2 минуты, так как 1.(9) = 2.
На контрольной тренировке Влад бегал с постоянной скоростью, однако по записям тренера не так легко сказать, с какой именно. Кроме того, секундомер был, возможно, запущен до того как Влад начал бегать. Напишите программу, которая поможет тренеру определить за какое минимальное, а также максимальное возможное время Влад мог пробегать каждый круг.
Входные данные
В первой строке входного файла находится единственное натуральное число N — количество записей в блокноте тренера (2 ≤ N ≤ 105). В следующей строке находятся сами эти записи — разделённые пробелами целые числа a1, a2, ..., aN (0 ≤ a1 ≤ a2 ≤ ... ≤ aN ≤ 106). Здесь a1 соответствует времени, когда Влад пробежал мимо тренера в первый раз.
Выходные данные
Выведите два неотрицательных вещественных числа, разделённых пробелом, — минимальное и максимальное возможное количество минут, за которое спортсмен пробегал один круг. Ваш ответ должен отличаться от правильного менее чем на 10 - 3.
Если ответа не существует, то есть Влад не мог бежать с постоянной скоростью так, чтобы записи тренера получились именно такими, в единственной строке выведите «No solution».
Примеры тестов
Входные данные
5
2 3 5 6 8
Выходные данные
1.33333 1.66667
Входные данные
5
1 6 9 14 17
Выходные данные
4 4
Входные данные
3
1 5 6
Выходные данные
No solution
Входные данные
5
1 1 2 3 3
Выходные данные
0.5 0.75
Примечание
Во втором тесте время 4 соответствует показаниям секундомера 1.(9), 6.0, 9.(9), 14.0, 17.(9).
В четвёртом примере минимальное время соответствует показаниям секундомера 1.5, 1.(9), 2.5, 3.0, 3.5, а максимальное — показаниям 1.0, 1.75, 2.5, 3.25, 3.(9).
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Методом градиентного спуска найдите глобальный минимум функции a ( y - x 4 ) 2 + b (1 - x ) 2 + cy , где a , b и c – натуральные числа, не превосходящие 20. Стартовое приближение во всех случаях можно полагать равным (1, 1) .
Входные данные
Даны три натуральных числа – a , b и c .
Выходные данные
Выведите два вещественных числа – координаты точки минимума. Ответ нужно дать с точностью до четвертого знака после запятой.
Примеры
Входные данные
1 1 2
Выходные данные
0.5000 -0.9374
#112095
Темы:
[Бинарный поиск в массиве]
[Бинарный поиск по ответу]
[Тернарный поиск]
[Многоугольники. Выпуклые оболочки]
[Обход в ширину]
[Дерево отрезков, RSQ, RMQ]
Источники:
[
Личные олимпиады,
Открытая олимпиада школьников,
2013-2014,
Заключительный этап,
Задача G
]
ограничение по времени на тест
2.5 second;
ограничение по памяти на тест
512 megabytes
На улице уже неделю лил беспросветный дождь, а Игорь все сидел дома и играл в свои любимые игрушки. Но играть так долго в одно и то же ему быстро надоело, и он пошел к родителям выпрашивать новые. Родители быстро сдались, поэтому на следующий день вся семья собралась, и они поехали в магазин игрушек.
При входе в магазин у Игоря сразу разбежались глаза. Ему хотелось и гоночную машинку, и кораблик с белыми парусами, и саблю, которая так и манила его своим блестящим лезвием. Всего в магазине продается \(N\) новых игрушек, причем так получилось, что все они плоские и имеют форму выпуклых многоугольников (действительно, на что еще можно было надеяться в магазине «Сто тысяч и один выпуклый многоугольник для детей младшего школьного возраста»?). Но строгий отец сказал, что купит Игорю только две игрушки. Игорь сразу же начал перебирать в голове варианты, но их оказалось слишком много, а если быть более конкретным, то его интересовало ровно \(Q\) вариантов выбора пары игрушек.
Любознательный Игорь сразу же задумался о тонкостях упаковки игрушек. А именно, для каждой интересующей его пары игрушек \(i\), \(j\) он хочет проделать следующие операции.
Изначально каждая игрушка лежит в своей плоской прямоугольной коробке, которая плотно прилегает к игрушке. Далее Игорь ставит эти две коробки на стол рядом друг с другом (\(i\)-ю игрушку можно поставить как левее \(j\)-й, так и правее), убирает коробки, потом придвигает игрушки друг к другу, насколько это возможно, и кладет то, что получилось, обратно в коробку (обратите внимание на рисунок). Так как Игорь очень экономный, ему нужно знать размеры получившейся коробки. Повлиять на высоту итоговой коробки, двигая игрушки параллельно плоскости стола, нельзя, так что вам нужно помочь Игорю лишь с определением минимально возможной ширины получившейся коробки.
Обратите внимание, что игрушки можно лишь двигать параллельно плоскости стола, поворачивать их каким-либо образом запрещено. Таким образом, задачу можно считать двумерной: ось \(O_x\) совпадает с плоскостью стола, а ось \(O_y\), по которой измеряется высота игрушек и коробок, перпендикулярна плоскости стола. Стороны коробок параллельны соответствующим осям координат. Диковинных игрушек в магазине предостаточно, так что они могут «стоять» на столе, в том числе и балансируя на одной вершине самым непостижимым образом.
Для лучшего понимания условия ознакомьтесь с примером и иллюстрациями к нему.
Формат входного файла
В первой строке содержится натуральное число \(N\) (1 ≤ \(N\) ≤ 100 000) - количество игрушек. Далее следуют описания \(N\) выпуклых многоугольников в следующем формате: сначала идет натуральное число \(k_m\) (3 ≤ \(k_m\) ≤ 300 000) - количество вершин в \(m\)-м многоугольнике, затем идут \(k_m\) строк, в которых записаны пары целых чисел xm,s, ym,s, по модулю не превосходящих \(10^9\) - координаты вершин \(m\)-го многоугольника в порядке обхода против часовой стрелки, заданные в системе координат соответствующей ему коробки, которая стоит на столе (это означает, что ym,s >= 0, а также для всех игрушек существует вершина \(v_m\), у которой ym,\(v_m\) = 0). Сумма всех \(k_m\) (обозначим ее за \(S\)) не превосходит 300 000.
В следующей строке записано натуральное число \(Q\) (1 ≤ \(Q\) ≤ 500 000) - число вариантов. Следующие \(Q\) строк содержат пары натуральных чисел \(i_t\), \(j_t\) (1 ≤ \(i_t\) < \(j_t\) ≤ \(N\)) - номера сдвигаемых игрушек в очередном варианте.
Формат выходного файла
Выведите \(Q\) строк: для каждого варианта выбора пары одно вещественное число - необходимую ширину коробки. Ответ будет считаться правильным, если все числа посчитаны с абсолютной или относительной погрешностью не более \(10^{-9}\).
Комментарий
Верхний рисунок иллюстрирует исходное размещение игрушек в коробках, а нижние — варианты итогового расположения игрушек (оптимальный вариант слева).
Система оценивания
Тесты к этой задаче состоят из четырех групп.
0. Тест 1. Тест из условия, оценивается в ноль баллов.
1. Тесты 2–20. В тестах этой группы \(k_m\) ≤ 100, \(Q\) ≤ 1 000, \(S\) ≤ 10 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы.
2. Тесты 21–40. В тестах этой группы \(k_m\) ≤ 300, \(Q\) ≤ 50 000, \(S\) ≤ 100 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае про- хождения всех тестов из первой группы.
3. Тесты 41–65. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 50 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.
Примеры
Входные данные
2 5 0 0 4 2 6 6 3 8 -2 4 5 0 0 2 0 8 4 5 11 3 12 1 1 2
Выходные данные
14.5000000000
Входные данные
2 3 0 0 0 3 -1 1 3 0 0 1 0 -20 20 1 1 2
Выходные данные
21.0000000000
Выбрано
:
|