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

Автор:Завгороднев А.А. Бадерик М.М.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 40, 1 ≤ ai ≤ 100

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

Стандартный вход Стандартный выход
1
5
12
10
3
7
23
-1
2
6
14
12
16
21
15
25
1 2 4 5

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

Автор:Артем Завгороднев, Иван Кобец   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

1 ≤ a, b, c, ai, bi, ci ≤ 109

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

Стандартный вход Стандартный выход
1
3 3 3
3
2 4 5
2 2 5
1 1 4
Physics
2
5 2 4
5
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
Geometry

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

Автор:Иван Кобец, Артем Завгороднев   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 2 ⋅ 105

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

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

Подзадача Количество тестов Баллы Дополнительные ограничения Информация о проверке
n
15 тестов5 баллов за тест1 ≤ n ≤ 200полная
25 тестов5 баллов за тест1 ≤ n ≤ 2000полная
310 тестов5 баллов за тест1 ≤ n ≤ 2 ⋅ 105полная

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

Стандартный вход Стандартный выход
1
7
1 1 1 0 0 1 0
6
2
5
1 1 1 1 1
5

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

Автор:Артем Завгороднев, Иван Кобец   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 2 ⋅ 105

1 ≤ ai ≤ 106

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

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

Подзадача Количество тестов Баллы Дополнительные ограничения Информация о проверке
N
110 тестов4 балла за тест1 ≤ N ≤ 20полная
210 тестов4 балла за тест1 ≤ N ≤ 5 ⋅ 104полная
35 тестов4 балла за тест1 ≤ N ≤ 2 ⋅ 105полная

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

Стандартный вход Стандартный выход
1
3
1 2 3
5
2
5
1 1 1 1 1
4

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

Автор:Бадерик М.М.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ A, B, Ai, Bi, Aj, Bj ≤ N ≤ 104

N ≤ M + K ≤ 105

0 ≤ ti, dti, tj ≤ 109

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

Стандартный вход Стандартный выход
1
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
2
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

0.226s 0.008s 21