Задача 2. спокойствие бобров

Задача 1. Очень хитрая задача

Ограничение по времени на тест 1 секунда
Ограничение по памяти на тест 64 мегабайта
Входные данные tricky.in
Выходные данные tricky.out

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

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

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

В единственной строке заданы два целых числа и

( ) – два очень хитрых числа, полученных очень хитрым бобром.

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

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

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

Входные данные Выходные данные Пояснение
7 3
7 10
15 -3

Частичная оценка

Дополнительные ограничения Максимальное количество баллов
–––

Задача 2. Спокойствие бобров

Ограничение по времени на тест 1 секунда
Ограничение по памяти на тест 128 мегабайт
Входные данные calmness.in
Выходные данные calmness.out

В тот день ничего не предвещало беды. Все бобры находились на дереве, занимались своими обыденными делами. Как вдруг, неожиданно, по дереву стал подниматься какой-то странный механизм. На одной из его панелей было написано «Боброжуй-0xFF». Бобры, увидев эту надпись, сразу поняли, что к чему. К несчастью, они так перепугались, что не смогли двигаться, а «Боброжуй-0xFF» тем временем начал пожирать этих бедняг. Не всех ждала столь ужасная участь, так как механизм, по каким-то непонятным причинам, пропускал некоторых бобров.

Прошло некоторое время, «Боброжуй-0xFF» уже завершил свою операцию и скрылся в неизвестном направлении. Бобры все еще были напуганы, но уже могли передвигаться. Однако им нужно было успокоиться перед тем, как продолжить заниматься своими делами. Бобры заметили, что общение помогает им в этом. Однако на все это нужно время, поэтому они обратились к вам за помощью.

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

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

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

В первой строке задано одно целое число ( ) – количество напуганный бобров.

Во второй строке задано целых чисел ( ) – время, необходимое -у бобру.

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

В первой строке выведите два целых числа и

( , ) – номер главного бобра и размер списка.

В следующих строках выведите два целых числа и

( , , ) – номер бобра, к которому нужно подойти и время, которое нужно затратить на общение с ним.

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

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

Входные данные Выходные данные Пояснение
1 7 3 4 2 2 5 1 1 3 3 4 2 5 2 4 2 Для того, чтобы успокоить всех бобров, понадобиться как минимум 10 единиц времени. Также существует оптимальная стратегия с меньшим списком.
6 1 1 1 2 2 1 3 5 Для того, чтобы успокоить всех бобров, понадобиться как минимум 6 единиц времени.

Частичная оценка

охота #29 на бобра с таксами


Похожие статьи.

Понравилась статья? Поделиться с друзьями: