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

Стоимость стакана чая и кофе в автомате предполагается установить равной пяти рублям. Автоматы будут принимать монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда пассажиру надо выдавать сдачу (т.е. когда пассажир бросил в автомат десятирублёвую монету или 10-, 50- или 100- рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же пассажир бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим пассажирам. Ясно, что, чтобы обеспечить возможность выдачи сдачи всем покупателям, может потребоваться изначально загрузить в автомат некоторое количество пятирублёвых монет. Сейчас на маршрутках фирмы проходят испытания с целью определить минимальное количество монет, которые надо загрузить в автомат перед выездом маршрутки в рейс. Вам дан протокол одного из таких испытаний: известен порядок, в котором пассажиры оплачивали свои покупки различными монетами и купюрами. Определите, какое минимальное количество пятирублёвых монет должно было изначально находиться в автомате, чтобы всем пассажирам хватило сдачи.

Большое количество соревнований по разным видам спорта проводится по так называемой "олимпийской системе". В простейшем варианте она состоит в следующем. В турнире участвуют N = 2^k игроков. Они получают номера от 1 до N, и в первом круге игрок 1 играет с игроком 2, игрок 3 с игроком 4 и т. д., игрок (N - 1) — с игроком N. Проигравшие в каждой паре выбывают из соревнований, а победители проходят во второй круг. Там победитель первой пары (т. е. игрок 1 или игрок 2) играет с победителем второй пары и т. д. Таким образом, в первом круге участвуют N = 2^k игроков, во втором круге — = 2^k - 1 и т. д., в финале участвуют два игрока.

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

В этой задаче вам нужно будет написать программу, находящую в некотором смысле оптимальный “рассев” игроков. Для этого рассмотрим следующую модель. Предположим, что участников можно упорядочить по силе так, что более сильный игрок всегда будет выигрывать у более слабого. В таком случае по изначальному “рассеву” игроков дальнейший ход соревнований будет однозначно определен. Тогда в качестве критерия оптимальности рассева” можно потребовать выполнение следующих условий: в финале играют двое сильнейших игроков, в полуфиналах играют четверо сильнейших игроков, и т. д.: в каждом круге играют только сильнейшие игроки (т. е. если в каком-то круге m мест, то в этом круге должны участвовать m сильнейших игроков). Вам дано N. Найдите любой оптимальный рассев N игроков.

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

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

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

Среди множества моделей, предложенных экономистами для описания различных видов рынков, вашему другу больше всего понравилась знаменитая «модель конного рынка» Е. фон Бём-Баверка. Эта модель состоит в следующем: в базарный день на рыночной площади собрались N продавцов и M покупателей. У каждого продавца есть одна единица товара (принято говорить о конях); каждый покупатель хочет купить одного коня. С точки зрения покупателей, все продавцы и все кони абсолютно одинаковы, т. е. покупателям всё равно, у кого покупать (значение имеет только цена). Аналогично, с точки зрения продавцов все покупатели одинаковы: продавцам всё равно, кому продавать (опять-таки, значение имеет только цена). Но субъективные оценки товара различаются:

1. Каждый продавец заранее определил для себя цену, дешевле которой он продавать ни в коем случае не будет: i-й продавец готов продавать коня по цене s_i и выше.
2. Аналогично, каждый покупатель заранее определил для себя цену, дороже которой он покупать ни в коем случае не будет: i-й покупатель готов покупать коня по цене b_i и ниже.

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

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

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

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

Подчиненные уже пронумеровали все отделы числами натуральными числами, начиная с 1, первый номер присвоен отделу по борьбе с компьютерными преступлениями.