XVIII Всеукраїнська комплексна олімпіада з математики, фізики
та інформатики

"Турнір чемпіонів"

2011 р.

Задача Три грибника (MUSHROOM)

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

Сколько грибов было у каждого перед привалом, если известно, что все вместе они собрали N грибов?

Технические условия

Программа MUSHROOM читает с клавиатуры одно натуральное число N (N≤30000) и выводит на экран первоначальное количество грибов у Пети, Васи и Коли соответственно. Предполагается, что ответ для данного N существует.

Пример:

Задача Секретное сообщение (SECRET)

До Штирлица не дошло письмо из Центра. Перечитал еще раз… Все равно не дошло…

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

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

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

Технические условия: Программа SECRET читает с клавиатуры в первой строке  число N (1≤N≤200000). Вторая и третья строки содержат по N чисел, задающих найденные Васей последовательности. Последняя строка содержит одно число – ключ P. Все эти числа являются целыми и лежат в пределах от 0 до 255 включительно.

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

Пример:

Задача Дорожная реформа (ORIENT)

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

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

Технические условия:

Программа ORIENT читает с клавиатуры два целых числа N – количество перекрестков в городе и M – количество дорог (1≤N≤20000, 1≤M≤200000). Далее  читает  M строк, в каждой из которых записаны два числа – номера перекрестков, связанных дорогой. Каждые два перекрестка соединяются не более чем одной дорогой.

Программа выводит на экран одно число K – максимальное количество дорог, на которых можно ввести одностороннее движение.

Пример: