Современные исследования показали, что стая голодных мышей в поисках сыра действует следующим образом: если поблизости есть несколько кусков сыра, то каждая мышь выбирает себе ближайший, после чего все мыши одновременно начинают двигаться в направлении выбранного куска сыра. Как только мышь, или несколько мышей, достигают точки назначения и там есть сыр, они его съедают, а все мыши, которые прибежали позже, остаются голодными. Скорость передвижения всех мышей одинакова. Если существует несколько способов выбрать ближайшие куски сыра, то мыши выберут такой способ, в соответствии с которым минимальное количество мышей стаи останутся голодными. Чтобы проверить эту теорию, ученые решили провести эксперимент. Они расположили N мышей и M кусков сыра в прямоугольной системе координат таким образом, что все мыши находятся на некоторой прямой y = Y ₀ , а все куски сыра — на другой прямой y = Y ₁ . Но чтобы проверить результаты эксперимента, ученым нужна программа, которая воспроизводит поведение стаи голодных мышей. Напишите программу, вычисляющую количество мышей, которые останутся без сыра.

На плоскости задано N точек.

Напишите программу, которая найдет сумму квадратов расстояний между всеми парами точек.

На секретной военной базе работает N (1 ≤ N ≤ 10000) охранников. Сутки поделены на 10000 равных промежутков времени, и известно когда каждый из охранников приходит на дежурство и уходит с него. Например, если охранник приходит в 5, а уходит в 8, то значит, что он был в 6, 7 и 8-ой промежуток (а в 5-й нет!!!). В связи с уменьшением финансирования часть охранников решено было сократить.

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

Жюри N-ской олимпиады по информатике решило зашифровать свои материалы подстановочным шифром. Для шифрования таким шифром задаётся взаимно-однозначное соответствие между буквами алфавита в открытом (т. е. до шифрования) тексте и буквами алфавита в закрытом (т. е. после шифрования) тексте, это соответствие и является ключом шифра. В процессе шифрования каждая буква в открытом тексте заменяется на соответствующую ей букву в закрытом тексте, порядок букв в слове при этом не меняется.

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

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

В одной из звездных систем Галактической Республики произошло дерзкое ограбление банка "13-е Общество межгалактического кредита", из которого было похищено несколько миллиардов буказоидов. Оказалось, что Армия Республики в данном секторе имеет ограниченные силы и не в состоянии блокировать все возможные пути бегства грабителей, поэтому встала задача о минимизации числа кордонов.

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