Шарик несколько раз запускают с разных стартовых позиций. Для каждого запуска требуется найти x-координаты точки соприкосновения шарика с землёй.
В первой строке содержится число N (0 <= N <= 3 * \(10^5\)) — количество перегородок.
Каждая из последующих \(N\) строк содержит описание очередной перегородки — четыре числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(x_1\) < \(x_2\), \(y_1\) ̸= \(y_2\), \(y_1\); \(y_2\) > 0): (\(x_1\); \(y_1\)) — координаты левого конца перегородки, (\(x_2\); \(y_2\)) — координаты правого конца.
В следующей строке содержится число M (1 <= M <= 3 * \(10^5\)) — количество запусков шарика.
Далее следуют \(M\) строк, в каждой из которых записано одно целое число — \(x\)-координата позиции, с которой производится запуск. Гарантируется, что \(y\)-координата стартовой позиции превосходит \(y\)-координаты концов всех перегородок.
Все координаты во входном файле — целые числа, не превосходящие \(10^6\) по модулю. Гарантируется, что среди перегородок нет вертикальных и горизонтальных, перегородки не имеют общих точек, длина каждой перегородки строго больше нуля.
Для каждого запуска выведите на отдельной строке единственное число — x-координату точки соприкосновения шарика с землёй.
Изображение в условии соответствует третьему примеру входных данных.
2 0 7 1 3 3 3 4 7 2 2 4
2 3
2 -3 5 1 3 -1 1 1 2 3 -3 -4 1
-1 -4 -1
7 -2 10 2 11 -4 9 -1 6 3 9 8 8 -7 3 -6 6 -1 5 3 4 -3 4 0 3 1 2 7 3 1 0
1
Анализируя результаты командной олимпиады прошлого года, жюри решило помимо лиг А и В организовать ещё и лигу С. На стадии распределения задач по лигам каждая отобранная задача была помечена соответствующим набором букв: А , В , С , АВ , ВС или АВС .
Для подготовки олимпиады требуется составить единый список задач. Жюри хочет, чтобы задачи для одной лиги шли в списке подряд. Помогите жюри упорядочить задачи требуемым образом или определите, что это невозможно.
В первой строке ввода находится число N ( 3 ≤ N ≤ 32 ) "— количество задач, отобранных для олимпиады.
В каждой из следующих N строк содержится описание задачи, начинающееся с одной из пометок А , В , С , АВ , ВС или АВС , записанной заглавными латинскими буквами, за которой через пробел следует название задачи. Название задачи "— произвольная строка, состоящая из строчных и прописных латинских букв и пробелов, которая заключена в кавычки (символ с кодом 34). В частности, название задачи может быть пустым или состоять только из пробелов. Описания задач не могут полностью совпадать, но задачи могут иметь одинаковые названия. Длина каждой строки во входном файле не превосходит 255 символов.
Выведите описания задач в требуемом порядке в том же формате, что и во входных данных. Все задачи, в пометку которых входит буква А , должны идти подряд, то же касается задач, пометка которых содержит букву В , и задач, пометка которых содержит букву С . В случае, если задачи можно расположить несколькими способами, удовлетворяющими вышеописанному условию, выведите любой из них. В частности, задачи с одинаковыми пометками могут следовать в любом порядке.
В случае, если добиться требуемого невозможно, выведите в единственной строке слово Impossible .
5 C "Tetris" A "World of warcraft" B "Doom" C "Lines" AB "Counter strike"
A "World of warcraft" AB "Counter strike" B "Doom" C "Tetris" C "Lines"
4 A "a" B "b" C "c" ABC "abc"
Impossible
Мэр уездного города
заботится о жителях и прислушивается к их мнению, поэтому он ежегодно даёт поручение социологической комиссии провести опрос общественного мнения. Участникам опроса предлагается
M
вопросов,
i
-й из которых содержит целое положительное количество вариантов ответа
a
i
. Жители города крайне серьёзно относятся к данному опросу, поэтому заполняют анкету добросовестно: каждый участник опроса выбирает ровно один вариант ответа в каждом вопросе.
При обработке результатов по каждому вопросу для каждого из доступных ответов считается процент людей, отдавших ему предпочтение. К большой радости сотрудников комиссии, обрабатывающих результаты опроса, в этом году все полученные числа выражаются целым количеством процентов.
В целях соблюдения конфиденциальности и анонимности все данные с бумажных анкет были занесены в электронную базу, а листы уничтожены. Но, по закону подлости, в ночь перед презентацией результатов исследования испортился жёсткий диск компьютера, на котором они хранились в единственном экземпляре. Более того, вместе с результатами был утрачен даже список вопросов и вариантов ответов на них! Единственной сохранившейся информацией являются пометки на полях тетради, сделанные во время подсчётов результатов секретаршей Жанной. После обработки каждого варианта она записывала процент людей, выбравших его, в совершенно произвольное место своей тетради ровно один раз.
Долгий и кропотливый процесс восстановления результатов предполагается начать с определения количества вопросов в исходном тестировании. Эта задача поручена вам.
В первой строке находится одно целое число K ( 1 ≤ K ≤ 100 ) "— количество чисел, записанных Жанной на полях тетради, совпадающее с суммарным количеством вариантов ответа на все вопросы.
Во второй строке записаны K неотрицательных целых чисел от 0 до 100, разделённых пробелами, каждое из которых обозначает процент жителей, проголосовавших за какой-то вариант ответа на какой-то вопрос.
Выведите единственное число M "— количество вопросов в социологическом опросе. Гарантируется, что существует ответ, удовлетворяющий записям из тетради Жанны. Если определить количество вопросов однозначно не удаётся, выведите любое подходящее значение.
В приведённом примере существует единственный способ получить подходящее разбиение: первое и третье число представляют ответы на один вопрос, а второе и четвёртое "— на другой.
4 25 50 75 50
2
Тем не менее Фёдору повезло: после прохождения многочисленных инстанций он всё-таки нашел место для нового дома. Более того, щедрое правительство даже подарило ему невероятно красивую крышу для постройки.
Важным обстоятельством является то, что Федя — совершенно плоский, как и весь мир, который его окружает. В этом плоском мире введена стандартная декартова система координат: ось \(O_x\) совпадает с землёй, а ось \(O_y\) направлена от земли вверх. Крыша представляет собой два отрезка, исходящих из одной точки (вершины крыши) вниз в разные стороны.
Разумеется, крыша находится над землёй, то есть отрезки находятся в верхней полуплоскости. Оба отрезка имеют ненулевую длину. Дом Феди должен представлять собой прямоугольник со сторонами, параллельными осям координат, одна сторона которого находится на земле, а другая сторона упирается в оба отрезка крыши. Дом не должен выходить за пределы крыши по горизонтали. Помогите Феде построить для себя дом наибольшей площади.
В первой строке содержатся два целых числа \(x_c\) и \(y_c\) — координаты вершины крыши (|\(x_c\)| <= \(10^4\), 1 <= \(y_c\) <= \(10^4\)).
Во второй строке содержатся два целых числа \(x_1\) и \(y_1\) — координаты одного из концов крыши (|\(x_1\)| <= \(10^4\), \(x_1\) ̸= \(x_c\), 0 <= \(y_1\) < \(y_c\)). В следующей строке в таком же формате заданы координаты \(x_2\) и \(y_2\) другого конца крыши.
Гарантируется, что отрезки, образующие крышу, направлены в разные стороны относительно верхней точки крыши, т. е. либо \(x_1\) < \(x_c\) < \(x_2\), либо \(x_2\) < \(x_c\) < \(x_1\)
Выведите единственное число — искомую максимальную площадь дома. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10-6
А именно, пусть ваш ответ равен \(A\), а ответ жюри — \(B\). Проверяющая программа будет считать ваш ответ правильным, если |\(A\)-\(B\)| / max(\(1\); \(B\)) <= 10-6.
10 10 5 5 15 5
50.0000000000
0 3727 -200 35 314 10
481473.2018423739
Туристическая отрасль в этом сезоне столкнулась с серьёзными сложностями. Добросовестные туроператоры ищут новые рекламные ходы для продажи своих туров. Как известно, наиболее благоприятная для отдыха погода меняется плавно, причём не только от одного дня к другому, но и в течение суток.
Для большинства туристических направлений есть многолетние посекундные результаты измерений различных климатических параметров, например, температуры или влажности. У каждого человека своё понимание того, насколько различными могут быть подобные значения во время отпуска, но всех интересуют непрерывные туры как можно большей продолжительности.
Пусть мы зафиксировали туристическое направление и некоторый климатический параметр. Будем называть изменчивостью тура разницу между максимальным и минимальным значением выбранного параметра за всё время поездки. Для каждого туриста известно максимальное приемлемое значение изменчивости k i .
Даны результаты измерений некоторого климатического параметра на одном из курортов и значения k i для нескольких туристов. Требуется для каждого из них определить максимальный диапазон, подходящий для отпуска.
В первой строке входного файла находится целое число N ( 1 ≤ N ≤ 600 000 ) "— количество сделанных измерений. Во второй строке "— N целых чисел, по модулю не превосходящих 10 9 — данные посекундных измерений.
В третьей строке входного файла находится число M ( 1 ≤ M ≤ 100 ) "— количество туристов, для которых необходимо найти оптимальный диапазон. В четвёртой строке "— M целых чисел k 1 , k 2 , ..., k M ( 0 ≤ k i ≤ 10 9 ) "— максимальная возможная разница между выбранным климатическим параметром в непрерывном диапазоне дней для каждого из туристов.
В выходной файл для каждого из M запросов в отдельной строке выведите два числа: номер первого измерения диапазона и номер последнего измерения, входящего в диапазон. Нумерация измерений ведётся с единицы. Если для некоторого туриста существует несколько подходящих диапазонов максимальной длины, выведите границы любого из них.
7 10 1 10 12 11 1 11 2 2 1
3 5 4 5