У одного из меломанов, участвующих в подготовке этой олимпиады, любимой группой так и остаётся ABBA (да простят его некоторые участники, предпочитающие что-нибудь «потяжелее»). Соответственно, когда речь заходит о примерах различных алгоритмов на строках, он в первую очередь составляет строки из двух букв a и b.

Собственно из анализа таких примеров и родилась следующая задача. Пусть мы хотим прочитать в строке буквосочетание ab. При этом a и b не обязательно должны стоять подряд, достаточно, чтобы a встречалось в строке раньше, чем b. Как составить строку минимально возможной длины, чтобы это буквосочетание можно было прочитать ровно K способами? Например, в строке abba это буквосочетание можно прочитать дважды, но эта строка не будет самой короткой для K = 2, а в строке abab его можно прочитать три раза, и более короткую строку для K = 3 составить нельзя.

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

Учительница по программированию задала Вовочке задачу — отсортировать массив из N чисел от 1 до N по возрастанию :). Вовочка поступает так: он просматривает массив слева направо, и, если замечает два элемента, стоящих рядом, таких, что правый меньше левого, он меняет их местами. Так он поступает, пока массив не будет отсортирован. Но Вовочка — очень ленивый ученик. В какой-то момент ему надоело сортировать числа, и он решил посчитать, сколько ещё описанных выше обменов нужно сделать. Помогите ему.

От некоторых школ в командной олимпиаде по информатике участвует очень много команд. Учитель одной из таких школ раздал для регистрации своим командам номера: 1, 2, 3 и т. д. Для того чтобы проверить, все ли команды зарегистрировались, учитель выписал из таблицы регистрации только номера команд своей школы, но в том порядке, в котором команды регистрировались.

После нелёгких подсчётов оказалось, что зарегистрировались все. Но в процессе решения этой задачи учитель сформулировал следующую: сколькими способами можно выбрать стоящие подряд в этом списке K номеров команд, чтобы они образовывали некоторую перестановку чисел от 1 до K? Например, если от школы участвуют всего три команды, то при порядке регистрации 3 1 2 таких способов будет три (для K = 1, 2, 3), а при регистрации в порядке 2 3 1 — всего два (для K = 1 и K = 3).

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

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

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

Государственная антимонопольная служба возбудила расследование против крупной авиакомпании «Aero-float». Ей предъявлено обвинение в излишней неэкономности. Джонни было поручено проинспектировать «Aero-float» в целях обнаружения финансовых махинаций, но авиакомпания отказалась раскрывать полный список выполняемых ею прямых рейсов. После продолжительных переговоров руководство компании согласилось сообщить Джонни информацию о минимально возможной продолжительности перелёта между каждой парой городов, если использовать только прямые рейсы «Aero-float» и не учитывать время, затрачиваемое на пересадки.

Используя эту информацию, помогите Джонни установить: может ли компания «Aero-float» быть экономной или нет? Более формально, установите, существует ли набор рейсов, при котором длины кратчайших маршрутов именно такие, как было сообщено Джонни, и при котором компания является экономной?

Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.

Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.

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

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