Разогревочный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"A" Космический корабль
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Космический рейнджер оказался на инопланетном космическом корабле в окружении врагов. Чтобы освободиться, ему необходимо уничтожить всех врагов в определенном порядке.

Вокруг рейнджера n врагов, i-й из них обладает силой fi. Чтобы выбраться, рейнджеру необходимо уничтожить всех врагов, причем в таком порядке, чтобы сила последнего уничтоженного врага была равна сумме всех остальных врагов.

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

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

В первой строке ввода находится натуральное число n — количество врагов (2 ≤ n ≤ 105).

Во второй строке находятся n целых чисел fi, задающих силу каждого врага ( - 109 ≤ fi ≤ 109).

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

Выведите числа fi в порядке, в котором необходимо уничтожать соответствующих им врагов. Если существует несколько подходящих вариантов, выведите любой. Гарантируется, что хотя бы один подходящий порядок уничтожения существует.

Примеры
Входные данные
3
2 5 3
Выходные данные
2 3 5
Входные данные
5
-1 1 0 1 -1
Выходные данные
-1 1 1 -1 0
"B" Рейнджеры в автобусе
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Космические рейнджеры едут на тайную встречу в автобусе.

Главный злодей внимательно следит за автобусом, в котором, по его мнению, едет кто-то из рейнджеров. В салоне автобуса n рядов сидений, в каждом из которых по два места — слева и справа от прохода. Ряды пронумерованы от 1 до n, начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли k человек, и злодей знает, кто на какое место сел и в каком порядке. Исходно все места были свободны.

Злодею известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:

  • Красный рейнджер любит сидеть впереди. Поэтому среди свободных мест он всегда выбирает место в ряду с наименьшим номером. Если же в этом ряду свободно два места, он садится слева от прохода.
  • Синий рейнджер тоже любит сидеть впереди. Но, в отличие от красного, когда в ряду с наименьшим номером свободно два места, Синий садится справа.
  • Чёрный рейнджер любит сидеть сзади. Среди свободных мест он всегда выбирает место в ряду с наибольшим номером, а если там свободно два места, то садится слева от прохода.
  • Жёлтый рейнджер тоже, любит сидеть сзади. Но, в отличие от чёрного, когда в ряду с наибольшим номером свободно два места, жёлтый садится справа.
  • Розовый рейнджер не имеет никаких предпочтений и может сесть на любое свободное место.

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

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

В первой строке заданы числа n и k — количество рядов в автобусе и количество пассажиров (1 ≤ n ≤ 109, 1 ≤ k ≤ min(2·105, 2n)).

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

В i-й из этих строк заданы числа xi и yi — место, на которое сел i-й пассажир (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2), xi — это номер ряда, yi = 1, если это место слева от прохода, и yi = 2, если справа.

Все места, на которые сели пассажиры, различны.

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

В первой строке выведите число s1 — количество пассажиров, которые могли бы быть красным рейнджером, а затем, через пробел, s1 чисел — номера этих пассажиров в порядке возрастания (пассажиры нумеруются с 1 по k в том порядке, в котором они заданы во входном файле).

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

Примеры
Входные данные
3 4
1 1
1 2
3 2
2 1
Выходные данные
3 1 2 4
1 2
0
1 3
4 1 2 3 4
"C" Волшебное оружие
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Для сборки волшебного оружия необходимо соединить три фрагмента: зеленый, красный и синий.

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

При сборке оружия необходимо соблюдать три правила:

  • Первая цифра номера модели красного фрагмента должна быть равна последней цифре модели зеленого.
  • Последняя цифра номера модели красного фрагмента должна быть равна первой цифре модели синего.
  • Все три использованных фрагмента должны иметь разные номера моделей.

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

Для каждого рейнджера вам известны номера моделей его фрагментов. У одного рейнджера могут быть несколько фрагментов одной модели.

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

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

В первой строке ввода заданы числа g, r и b — количество фрагментов у зеленого, красного и синего рейнджера соответственно (1 ≤ g, r, b ≤ 105).

В следующей строке находится g чисел xi — номера моделей, которые есть у зеленого рейнджера (0 ≤ xi ≤ 109).

В следующей строке находится r чисел yi — номера моделей, которые есть у красного рейнджера (0 ≤ yi ≤ 109).

В следующей строке находится b чисел zi — номера моделей, которые есть у синего рейнджера (0 ≤ zi ≤ 109).

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

Выведите одно число — количество способов собрать оружие.

Примеры
Входные данные
3 3 2
101 11 52
11 23 23
31 13
Выходные данные
3
"D" Рыцари и лжецы
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Космический рейнджер построил свою армию в две шеренги по k солдат. Соседями в данном построении он считает солдат слева и справа в той же шеренге, а также солдата, который стоит на той же позиции, но в другой шеренге.

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

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

  • «Правда ли, что ровно x из твоих соседей рыцари?»
  • «Правда ли, что ровно y из твоих соседей лжецы?»
и задал каждому солдату. Всем солдатам были заданы вопросы с одними и теми же значениями x и/или y.

Внезапно все солдаты ответили «да» на все заданные им вопросы.

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

Разберем второй пример из условия: в каждой шеренге по 5 солдат, и были заданы вопросы «Правда ли, что ровно один из твоих соседей рыцарь?» и «Правда ли, что ровно двое из твоих соседей лжецы?»

Армия может полностью состоять из лжецов (они точно солгали, отвечая на первый вопрос, хотя крайние в шеренгах ответили правду на второй вопрос). В этом случае достигается минимальное число рыцарей — 0. Другой вариант — в каждой шеренге на втором и четвертом местах стоят рыцари, а на остальных — лжецы. В этом случае все рыцари говорят правду, как и должны, а каждый лжец говорит неправду, отвечая на второй вопрос (у каждого лжеца ровно один сосед лжец). В этом случае достигается максимальное число рыцарей — 4.

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

В единственной строке ввода содержатся три целых числа k, x, y — количество солдат в одной шеренге и числа из вопросов (1 ≤ k ≤ 105,  - 1 ≤ x, y ≤ 3).

Если x =  - 1, это означает, что рейнджер не задавал первый вопрос.

Если y =  - 1, это означает, что рейнджер не задавал второй вопрос.

Гарантируется, что рейндждер задавал хотя бы один вопрос.

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

Если для данных k, x и y не существует ни одного способа построения, выведите  - 1.

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

Примеры
Входные данные
2 0 -1
Выходные данные
2
2
Входные данные
5 1 2
Выходные данные
0
4
Входные данные
1 2 2
Выходные данные
0
0
Входные данные
10 0 3
Выходные данные
5
8
"E" Параллелепипед
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Черный Рейнджер хочет составить прямоугольный параллелепипед. Для этого он планирует использовать 6 из n прямоугольных листов металла, i-й лист имеет размер ai на bi метров.

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

Черный Рейнджер хочет построить параллелепипед максимального объема. Помогите ему.

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

В первой строке дано одно число n — количество листов металла у Черного Рейнджера (6 ≤ n ≤ 200 000).

В следующих n строках даны пары чисел ai, bi — размеры i-го листа металла (1 ≤ ai, bi ≤ 106).

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

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

Если из данных листов невозможно собрать прямоугольный параллелепипед, выведите  - 1.

Примеры
Входные данные
6
3 6
6 9
9 3
6 3
3 9
9 6
Выходные данные
162
Входные данные
6
1 1
1 1
1 1
1 1
1 1
1 1
Выходные данные
1
Входные данные
6
1 2
2 3
3 4
4 5
5 6
6 1
Выходные данные
-1

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

It.Mail.ru

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.