Задача A. Поиск трапеции ≡

Условие

Ваня купил себе VR-гарнитуру и решил поиграть. Для начала ему необходимо разметить VR-зону в комнате. Для этого Ваня хочет использовать изоленту. У него уже есть N отрезанных кусков длиной a_i. VR-зона должна иметь форму прямоугольной трапеции. Каждая сторона трапеции должна быть образована ровно одним куском изоленты.

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

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

Первая строка содержит единственное число N. Следующие N строк содержат целые числа — длины отрезков a_i

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

Выведите 4 индекса отрезков в порядке возрастания или  − 1, если невозможно получить прямоугольную трапецию. Индексация начинается с нуля.

Если существует несколько ответов, выведите трапецию с максимальной площадью, а среди таких — с минимальным первым индексом.

Ограничения

Примеры тестов

5
12
10
3
7
23

-1

6
14
12
16
21
15
25

1 2 4 5

Задача B. Экзамен ≡

Условие

Артему предстоит сложный экзамен по алгебре, геометрии и физике. Преподаватель на лекции сообщил, что студентам на выбор будет предложено n билетов и скинул всем их на электронную почту. Артем оценил каждый билет по трем параметрам: сложность его по алгебре, геометрии и физике. Сам Артем оценил свои силы следующим образом: если сложность билета по алгебре, геометрии и физике меньше чем a, b и c соответственно, он способен к нему подготовится и сдать.

Так как Артем был прилежным студентом, преподаватель готов принять у него экзамен, пропустив один из предметов по его выбору: алгебру, геометрию или физику. Студент не против воспользоваться такой возможностью, поэтому просит у вас узнать, какой предмет ему стоит пропустить, чтобы можно было решить как можно больше билетов.

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

В первой строке записано три целых числа a, b и c  — предельные пороги сложности по алгебре, геометрии и физике соответственно.

Во второй строке целое число n  — количество билетов на экзамене.

Во следующих n строках записано по три целых числа a_i, g_i, p_i  — сложность билета по алгебре, геометрии и физике соответственно.

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

Выведите Algebra, Geometry или Physics в соответствии с тем, какой экзамен выгоднее пропустить. Если существует несколько вариантов ответа, выведите любой.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ a, b, c, a_i, b_i, c_i ≤ 10⁹

Примеры тестов

3 3 3
3
2 4 5
2 2 5
1 1 4

Physics

5 2 4
5
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5

Geometry

Задача C. Радостные студенты ≡

Условие

На лекции по высшей математике в ДВФУ преподаватель собрал n студентов в ряд и задал простой вопрос: Кто сейчас грустит, поднимите руку. На это предложение несколько (возможно, ноль) студентов подняли руки.

После этого, он решил выбрать из этой последовательности студентов некоторый отрезок [left, right], на котором он добавит грустным студентам по 5 баллов к экзамену просто так. При этом, он понимает, что студенты, которые были радостные на этом отрезке, поменяют своё настроение. Если ни один студент не является грустным, преподаватель не будет выбирать никакой отрезок. Он хочет получить наибольшее количество радостных студентов на лекции, поэтому просит Вас написать программу, которая рассчитает максимальное их количество после применения ранее описанной операции.

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

В первой строке записано целое число n  — количество студентов.

Во второй строке записано n цифр 0 и 1, где 0  — грустный студент, а 1  — радостный

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

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

Ограничения

1 ≤ n ≤ 2 ⋅ 10⁵

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

Баллы начисляются за каждый тест независимо. Тесты поделены по подзадачам, описанным ниже.

Примеры тестов

7
1 1 1 0 0 1 0

6

5
1 1 1 1 1

5

Задача D. Подготовка к ЕГЭ ≡

Условие

Мальчик Миша готовится экзаменам. На это у него осталось N дней. В i-ый день у Миши вдохновение решить a_i задач. Но он не сверхчеловек, поэтому ему необходимо спать. В i-ый день у Миши есть выбор:

• Поспать, не решив ни одной задачки.
• Выпить чай с лимонником и не спать, решив все задачи.
• Не спать, решив все задачи.

Не спать он может только в том случае, если у него достаточно сил, то есть если в предыдущий день он поспал.

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

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

В первой строке записано целое число N.

Во второй строке находится N целых чисел a_i.

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

Выведите одно целое число: максимальное количество задач, которые может решить Миша.

Ограничения

1 ≤ N ≤ 2 ⋅ 10⁵

1 ≤ a_i ≤ 10⁶

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

Баллы начисляются за каждый тест независимо. Тесты поделены по подзадачам, описанным ниже.

Примеры тестов

3
1 2 3

5

5
1 1 1 1 1

4

Задача E. Путешествие ≡

Условие

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

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

В этой игре между двумя планетами иногда появляются "кротовые норы" (англ. wormholes), пройдя через которые, флот может переместиться вперед во времени и оказаться у следующей планеты. В то же время может также существовать "обычный" путь между планетами, который флот может преодолеть за некоторое время. Существование кротовых нор и обычного пути не связаны между собой. Кротовые норы появляются не сразу и, если флот окажется у планеты, нора около которой еще не образовалась, он не сможет ею воспользоваться. Воспользоваться норой в обратном направлении невозможно. Даки хочет определить, в какой самый ранний момент времени его флот, находящийся у планеты A, может оказаться у планеты B.

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

Первая строка содержит 3 целых числа: N, A, B – количество планет, планету с флотом и планету-цель, соответственно.

Далее следует строка с 2 целыми числами: M – количество кротовых нор и K – количество обычных путей.

Последующие M строк содержат 4 целых числа: A_i, B_i – две планеты, между которыми появляется нора, t_i – время её появления и dt_i – насколько изменится время при перемещении по ней из A_i в B_i.

Далее идут K строк в таком формате: A_j, B_j, t_j – две планеты и время пути между ними.

Считаем, что изначально время равно 0. Все планеты нумеруются от 1 до N включительно. Обычные пути существуют в любое время.

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

Выведите единственное число – самое раннее время в которое флот сможет оказаться у планеты B.

Гарантируется, что путь существует.

Ограничения

1 ≤ A, B, A_i, B_i, A_j, B_j ≤ N ≤ 10⁴

N ≤ M + K ≤ 10⁵

0 ≤ t_i, dt_i, t_j ≤ 10⁹

Примеры тестов

6 3 5
3 6
6 3 0 0
1 3 2 3
2 1 0 1
3 5 3
1 6 2
5 1 4
3 6 0
5 2 1
2 4 2

3

5 3 2
0 8
3 2 4
1 4 1
5 2 2
5 3 5
1 5 3
2 4 1
4 1 3
4 3 2

4