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

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

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

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

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

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

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

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

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

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

Например, если в первой кучке 12 камней, а во второй – 7, то позиция хорошая, т.к. число 127 простое.

Ваша задача найти такую последовательность ходов, при которой можно перейти из начальной позиции (1, 1) в конечную (N, N) через максимально возможное число хороших позиций. Например, для N = 4 одна из искомых последовательностей такова: 1; 1 -> 2; 1 -> 3; 1 -> 4; 1 -> 4; 2 -> 4; 3 -> 4; 4

Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали N столбов вдоль одной из сторон участка. Это очень сильно расстроило Дядю Фёдора, так как его друзья забыли о самом главном — калитка должна находиться именно на этой стороне, и для неё необходимо было оставить проём шириной как минимум W. Теперь им придётся выкапывать некоторые столбы.

Чтобы работа не пропадала даром, выкопать надо как можно меньше столбов. Помогите Дяде Фёдору определить, какие именно столбы надо выкопать. После выкапывания столбов должен найтись промежуток (между двумя оставшимися столбами, или между оставшимся столбом и концом стороны участка, или между двумя концами стороны участка) ширины больше или равной W.

Том Сойер, блуждая по лабиринту, записывал карандашом изменения в направлении своего движения и сколько шагов он прошел в том или ином направлении. Его запись могла выглядеть так: F 5 R 1 B 2 L 1. Здесь F означает движение вперед (F может быть только первым и обязательным элементом в записи пути), R — поворот направо, L — налево, B — движение назад (видимо, путник зашел в тупик), число после буквы обозначает количество шагов, сделанных после изменения направления. Другие обозначения в записи не встречаются.

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