У одного из меломанов, участвующих в подготовке этой олимпиады, любимой группой так и остаётся 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» быть экономной или нет? Более формально, установите, существует ли набор рейсов, при котором длины кратчайших маршрутов именно такие, как было сообщено Джонни, и при котором компания является экономной?