Страница: << 32 33 34 35 36 37 38 >> Отображать по:

#112688

Новоселье

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига А, Задача D ]

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

Тем не менее Фёдору повезло: после прохождения многочисленных инстанций он всё-таки нашел место для нового дома. Более того, щедрое правительство даже подарило ему невероятно красивую крышу для постройки.

Важным обстоятельством является то, что Федя — совершенно плоский, как и весь мир, который его окружает. В этом плоском мире введена стандартная декартова система координат: ось \(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

#112689

Интеллектуальный отпуск

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига А, Задача E ]

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

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

Пусть мы зафиксировали туристическое направление и некоторый климатический параметр. Будем называть изменчивостью тура разницу между максимальным и минимальным значением выбранного параметра за всё время поездки. Для каждого туриста известно максимальное приемлемое значение изменчивости k _i .

Даны результаты измерений некоторого климатического параметра на одном из курортов и значения k _i для нескольких туристов. Требуется для каждого из них определить максимальный диапазон, подходящий для отпуска.

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

В первой строке входного файла находится целое число N ( 1 ≤ N ≤ 600 000 ) "— количество сделанных измерений. Во второй строке "— N целых чисел, по модулю не превосходящих 10 ⁹ — данные посекундных измерений.

В третьей строке входного файла находится число M ( 1 ≤ M ≤ 100 ) "— количество туристов, для которых необходимо найти оптимальный диапазон. В четвёртой строке "— M целых чисел k ₁ , k ₂ , ..., k _M ( 0 ≤ k _i ≤ 10 ⁹ ) "— максимальная возможная разница между выбранным климатическим параметром в непрерывном диапазоне дней для каждого из туристов.

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

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

Примеры

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

7
10 1 10 12 11 1 11
2
2 1

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

3 5
4 5

#112690

Средиземье в опасности

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига А, Задача F ]

Тёмные силы под руководством Саурона заполонили Средиземье, и только Арагорн, сын Араторна, наследник Исилдура и истинный правитель Гондора, может найти силы противостоять Тёмному владыке Мордора. Впрочем, ему мы поможем в другой раз, сейчас же давайте оценим, как далеко может зайти Тёмный Властелин.

Карта Средиземья представляет собой клетчатый прямоугольник из N строк по M клеток, каждая из которых может либо полностью принадлежать Саурону, либо полностью не принадлежать. Если в любом квадрате размером 2 × 2 три клетки уже захвачены тёмными силами, то они могут завоевать четвёртую клетку этого квадрата.

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

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

В первой строке содержатся два целых числа N и M ( 1 ≤ N , M ≤ 1 000 ) "— количество строк и столбцов на карте Средиземья.

Следующие N строк по M символов описывают клетки карты. Символ ‘ . ’ соответствует клетке карты, свободной от власти Саурона, а ‘ # ’ "— клетке, захваченной Сауроном. Строки нумеруются от 1 до N , столбцы "— от 1 до M .

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

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

Примеры

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

2 2
##
#.

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

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

3 4
#...
#...
###.

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

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

3 5
...##
#....
#.#..

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

#112691

Турбулентность

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига А, Задача G ]

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

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

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

Формат входного файла

В первой строке содержатся два целых числа: \(N\) — длина переданного сообщником слова (\(1 \leq N \leq 10^6\)) и \(K\) (\(1 \leq K \leq 26\)).

Во второй строке содержится переданное сообщником слово.

Формат выходного файла

Выведите строку, которую Миша хочет попробовать в качестве кода от сейфа

Примеры

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

3 2
aab

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

ba

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

6 3
aaabbc

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

ac

#112692

Язык PJ

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига А, Задача H ]

Мальчик Вартáн настолько любит языки программирования, что выучил уже целых девять и обзавёлся самоучителем по ещё одному языку! Впрочем, просто учить языки ему уже немного надоело, и он решил придумать свой. Название для языка было придумано всего за пару минут — PJ (аббревиатура от любимых команд Вартана), казалось бы, полдела сделано.

После пяти лет упорной работы Вартан реализовал две команды, работающие с целыми неотрицательными числами:

print value "— число value выводится на экран, после чего исполнитель переходит к следующей строке.
jump num count "— если выполнено условие count > 0 , то управление передаётся в строку с номером num , а count уменьшается на 1 . В текущей реализации PJ не предусмотрено использование в качестве num числа большего, чем номер строки, в которой записана данная команда. Если же count = 0 , то исполнитель просто переходит к следующей строке. Обратите внимание, что в следующий раз, когда интерпретатору встретится данная строка, он будет работать уже с новым значением count , то есть можно считать, что каждой команде jump соответствует своя глобальная переменная.

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

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

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

На ввод подаётся корректная программа на языке PJ, состоящая как минимум из одной, но не более чем из 10 ⁵ команд. Количество строк в файле совпадает с количеством команд, каждая команда занимает отдельную строку. Команда, записанная в строке с номером i (при нумерации от единицы), удовлетворяет одному из двух форматов:

print value , где 0 ≤ value ≤ 10 ⁴ .
jump num count , где 1 ≤ num ≤ i , 0 ≤ count ≤ 10 ⁴ .

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

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

Примеры

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

print 1
print 2
jump 2 2

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

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

print 3
jump 1 1
print 1
print 1
jump 1 2

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

Страница: << 32 33 34 35 36 37 38 >> Отображать по:

Выбрано

Отменить

Добавить в контест