Страница: << 138 139 140 141 142 143 144 >> Отображать по:
#112095
Игорь и игрушки
  
ограничение по времени на тест
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
#112096
Пицца для вечеринки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Еще только начался март, а студент первого курса НУОП (Неизвестного университета олимпиадного программирования) Вениамин уже закрыл сессию — чем не повод устроить вечеринку?

Вениамин назначил день и час, пригласил всех своих друзей и заказал огромное количество пиццы. Он выбирал какую-нибудь новую настольную игру, которую никто из его друзей еще не видел, когда произошло неприятное событие — пиццу доставили гораздо раньше, чем планировалось. Так как к приходу друзей пицца уже гарантированно остынет, необходимо заранее продумать организацию процесса ее разогрева. Теория расписаний изучается в НУОП только на третьем курсе, так что Вениамин обращается к вам за помощью, разумеется, предварительно строго сформулировав задачу:

* Всего у Вениамина имеется N пицц.

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

Каждая пицца характеризуется ровно двумя параметрами \(a_i\) и \(b_i\):

– \(a_i\) обозначает время в секундах, необходимое для разогрева \(i\)-й пиццы в микро- волновой печи;

– \(b_i\) обозначает время в секундах, в течение которого пицца остается горячей

* Для разогревания пицц можно использовать только микроволновку, которая у Вениамина ровно одна. Чтобы пицца стала горячей, она должна находится в микроволновке непрерывный отрезок времени длительностью ровно \(a_i\) секунд.

* В каждый момент времени в микроволновке может находиться не более одной пиццы

* Можно считать, что все действия по управлению микроволновкой Веня совершает мгновенно (включить или выключить микроволновку, достать или убрать пиццу).

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

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

В первой строке входных данных записано целое число \(N\) — количество пицц (1 ≤ \(N\) ≤ 300 000). Следующие \(N\) строк содержат описания пицц, каждое из которых состоит из двух целых чисел \(a_i\) и \(b_i\) (1 ≤ \(a_i\); \(b_i\) ≤ \(10^{9}\)).

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

Выведите единственное число — максимальное количество пицц, которые могут одновременно оказаться горячими

Комментарий

Разберем подробнее первый тест из условия:

* В нулевой момент времени Вениамин убирает в микроволновку первую пиццу.

* В момент времени 1 Вениамин достает из микроволновки первую пиццу и кладет туда вторую.

* В момент времени 2 Веня достает из микроволновки вторую пиццу, в этот момент первая пицца еще горячая, следовательно, ответ на задачу — 2. Обратите внимание, что две пиццы будут горячими только в этот момент времени, и добиться того, чтобы они были горячими в течение ненулевого по длине промежутка времени, в данном примере невозможно.

Система оценивания

Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3–15. В тестах этой группы \(N\) ≤ 10. Эта группа оценивается в 20 баллов.

2. Тесты 16–30. В тестах этой группы \(N\) ≤ 20. Эта группа оценивается в 20 баллов.

3. Тесты 31–45. В тестах этой группы \(N\) ≤ 5 000. Эта группа оценивается в 20 баллов.

4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.

Примеры
Входные данные
2
1 1
1 1
Выходные данные
2
Входные данные
4
2 12
10 8
7 5
5 1
Выходные данные
3
#112098
Гонорар
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Инопланетяне с планеты Пандора уже много лет исследуют землян. Для этого на Землю внедрено множество агентов-пандорианцев. Так как среднестатический пандорианец примерно в 20 раз меньше среднестатичестического землянина, для перемещения по планете они используют специальных роботов, внешне неотличимых от жителей Земли. Внутри этих роботов с комфортом располагается команда агентов-исследователей.

Сегодня команда, управляющая роботом «Геннадий», получает свой гонорар. Команда состоит из двух пандорианцев, Джейка и Джейка, которые в данный момент исследуют жителей России. Гонорар исследователи получают один на двоих наличными в обыкновенном российском банке.

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

Напишите программу, которая поможет Джейку и Джейку ответить на этот вопрос.

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

На вход подается число K — сумма, которую получат Джейк и Джейк ( 1 ≤ K ≤ 100 000 ).

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

Выведите «YES», если вне зависимости от того, какими именно монетами и купюрами будет выдана нужная сумма, их можно будет поделить поровну, и «NO» — в противном случае. Действие происходит в России, поэтому для выдачи нужной суммы могут быть использованы купюры и монеты следующих номиналов: 1 , 2 , 5 , 10 , 50 , 100 , 500 , 1000 и 5000 рублей.

Примечание

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

  • Тесты 1–3. Тесты из условия, оцениваемые в ноль баллов.

  • Тесты 4–9. В тестах этой группы K < 10 . Эта группа оценивается в 20 баллов,

  • Тесты 10–18. В тестах этой группы 10 ≤ K < 100 . Эта группа оценивается в 20 баллов.

  • Тесты 19–29. В тестах этой группы 100 ≤ K < 1000 . Эта группа оценивается в 20 баллов.

  • Тесты 30–42. В тестах этой группы 1000 ≤ K < 10 000 . Эта группа оценивается в 20 баллов.

  • Тесты 43–51. В тестах этой группы 10 000 ≤ K ≤ 100 000 . Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.

Тестирование на тестах каждой группы производится вне зависимости от прохождения всех тестов из предыдущих групп.

Примеры
Входные данные
7
Выходные данные
NO
Входные данные
24
Выходные данные
YES
Входные данные
10
Выходные данные
NO
#112099
Воды слонам!
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Кроме Земли, пандорианцы уже много тысячелетий исследуют и другие планеты. Большой интерес для них в прошлом представляла планета Арракис. К сожалению, с началом исследований на Земле финансирование исследований на Арракисе было существенно урезано, и местным агентам-исследователям пришлось искать дополнительные источники дохода.

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

Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить \(\frac{10}{4}=2.5\) литра воды, а продать они эту воду смогут за \(2.5 \times 6=15\) золотых слитков. Таким образом, прибыль пандорианцев составила бы \(15-10=5\) золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!

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

В первой строке задано целое число 2 ≤ N ≤ 100 000 — количество дней в году на планете Арракис.

Во второй строке заданы N целых положительных чисел a i ( 1 ≤ i ≤ N , 1 ≤ a i ≤ 5000 ), задающих стоимость воды на Арракисе в день i .

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

Выведите два целых числа: первое число — номер дня, в который стоит купить воду, второе число — номер дня, в который следует воду продать. Дни нумеруются с единицы. Если оптимальных пар дней для покупки/продажи несколько, то выведите любую из них.

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

Примеры
Входные данные
6
10 3 5 3 11 9
Выходные данные
2 5
Входные данные
4
5 5 5 5
Выходные данные
0 0
#112100
Будьте осторожны при купании!_0
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes

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

В поисках материала для исследования пандорианцы на своей летающей научной базе прибыли на обыкновенный курортный пляж, до отказа забитый греющимися на солнце туристами. Туристы занимают все доступное место на пляже, образуя, таким образом, прямоугольник размером N × M человек. По пляжу они не перемещаются. То есть, каждый турист однозначно задается своими координатами в этом прямоугольнике: номером ряда, в котором он лежит, и номером в этом ряду.

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

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

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

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

В первой строке заданы два числа: N и M — размеры прямоугольника, который туристы образуют своими телами, где N — это количество рядов, а M — количество человек в одном ряду пляжа. Гарантируется, что туристов на пляже четное число.

Затем программа-решение начинает взаимодействие с программой-интерактором в соответствии со следующим протоколом:

  • Программа-решение выводит в стандартный поток вывода одну строчку, описывающую, каких туристов оператор поднимает с пляжа в этот раз. Строчка должна содержать четыре целых числа x 1 , y 1 , x 2 , y 2 , где x 1 — номер ряда, в котором лежит первый турист, y 1 — его номер в этом ряду, а x 2 и y 2 — координаты второго туриста, заданные аналогично. Ряды нумеруются сверху вниз, начиная с 1 , туристы в них — слева направо, начиная с 1 . Вывод должен завершаться переводом строки и сбросом буфера потока вывода. Для последнего используйте
    • flush(output) в паскале или Delphi;
    • fflush(stdout) или cout.flush() в С/C++;
    • sys.stdout.flush() в Python;
    • Console.out.flush() в Visual Basic.
  • После этого программа должна считать из стандартного потока ввода ответ программы-интерактора. Ответ состоит из двух натуральных чисел, не превышающих 200 000 — цвета глаз первого и второго туриста соответственно. Отправка туристов обратно на пляж или на исследование в соответствии с этими данными происходит автоматически. Если их забирают ученые, больше эти земляне на пляж не возвращаются. Их места на пляже остаются пустыми до конца исследования.
  • Программа-решение должна завершить работу, когда на пляже не останется ни одного туриста. Гарантируется, что организовать выбор туристов так, чтобы это условие оказалось выполненным, всегда возможно. Количество запросов не должно превышать 262 144.

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

Примечание

Тесты к этой задаче состоят из пяти групп.

  • Тест 1. Тест из условия, оценивается в ноль баллов.

  • Тесты 2–7. В тестах этой группы глаза у всех туристов одного цвета, 1 ≤ N , M ≤ 50 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • Тесты 8–13. В тестах этой группы 1 ≤ N , M ≤ 50 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • Тесты 14-17. В тестах этой группы 1 ≤ N , M ≤ 200 . Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо.

  • Тесты 18-21. В тестах этой группы 1 ≤ N , M ≤ 500 . Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо.

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

Правильный пример на картинке.

Страница: << 138 139 140 141 142 143 144 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест