Алгоритмы

Сегодня в Москве отмечается Новый год. Для танца составили схему, на которой показано кто и где находится. Есть несколько групп людей, одетых в разных персонажей. 

Е-елка
О-охрана
1-зона 1
2-зона 2
3-зона 3
4-зона 4
Х-олени
К-зайцы
С-снеговики
М-медведи
Л-лисицы
В-волки
П-подарки
Д-деды Морозы.

Вот план для размеров поля 9 на 9. Размер поля всегда нечетный и больше 8.

О М М М 2 С С С О
Л О М М 2 С С О К
Л Л О М 2 С О К К 
Л Л Л О О О К К К
3 3 3 О Е О 1 1 1
В В В О О О Х Х Х
В В О П 4 Д О Х Х
В О П П 4 Д Д О Х
О П П П 4 Д Д Д О

Человек, находящийся в зоне 1, одет в зайца, если стоимость его костюма кратна 3, в противном случае, он одет в оленя.
Человек, находящийся в зоне 2, одет в снеговика, если стоимость его костюма кратна 5, в противном случае, он одет в медведя.
Человек, находящийся в зоне 3, одет в лисицу, если стоимость его костюма кратна 5, в противном случае, он одет в волка.
Человек, находящийся в зоне 4, одет в подарок, если количество единиц его стоимости , записанной в двоичной системе счисления, больше количества нулей, в противном случае, он одет в Деда Мороза.
Про каждый костюм известно, за сколько его можно сшить.
Посчитайте и выведите стоимость костюма елки, затем охраны.
Затем надо вывести в порядке убывания стоимость и название костюма персонажа.

• Входные данные:
  Вводится n-размер квадратной матрицы, затем сама матрица.
• Выходные данные:
  Вывести сначала стоимость костюма елки, затем сумму всех костюмов охраны, затем в порядке убывания стоимость костюмов остальных персонажей и название костюма.
• Входные данные:
  9
  0 1 1 0 2 5 5 4 1
  2 3 2 4 5 6 1 2 0
  1 2 3 4 2 3 1 2 3
  1 2 2 4 3 5 7 1 2
  0 2 3 1 2 3 4 5 6
  0 1 2 3 5 3 3 4 5
  5 6 2 7 4 2 2 4 2
  8 4 3 4 3 1 3 4 5
  6 7 8 2 5 2 1 3 3
• 2
  58
  39 podarok
  32 olen
  27 snegovik
  27 volk
  21 zayka
  16 medved
  16 ded moroz
  10 lisiza

(с) Чуканова Юля, 10и

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

Принцип работы транспортного средства Деда Мороза(в дальнейшем ПепеЛАЦ(Пепе Летающий агрегат Цвайхандер)) такой:
на расстоянии одного километра друг от друга в точках (0, 0) и (1, 0) были построены две станции управления пепелацами A и B. С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки A или B. Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.

Например, если повернуть пепелац, находящийся в точке (3, 1) на 90 градусов против часовой стрелки относительно станции A, то он переместится в точку (−1, 3), если его затем повернуть на 90 градусов по часовой стрелке относительно станции B, то он переместится в точку (4, 2), если затем повернуть его вокруг станции B по часовой стрелке еще раз, он переместиться в точку (3, −3).
Деду Морозу необходимо добраться из точки (x1, y1) в точку (x2, y2). Помогите зайцам Деда Мороза составить маршрут, чтобы ему меньше пришлось ходить по заснеженному лесу.
Поскольку перемещения мгновенные и абсолютно бесплатные(магия же), то минимизировать количество перемещений не надо.

Формат входного файла
Входной файл содержит четыре целых числа — x1, y1, x2 и y2, они не превышают 104 по
абсолютной величине.

Формат выходного файла
Выведите в выходной файл последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x1, y1) как можно ближе к точке (x2, y2).
Поворот по часовой стрелке относительно станции A обозначается как «+A», поворот против часовой стрелки относительно станции A обозначается как «-A», соответствующие повороты относительно станции B обозначаются как «+B» и «-B». Выводите по одному перемещению на строке. Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более 106 действий.

Примеры

Ввод	Вывод
3 1 3 -3	-A    +B +B
0 0 3 0	-B +B

 (с) Павел Колодкин, 12И

Герцог Циклонский, обладая безграничным могуществом, что отражено в его девизе "Все могу!", ежегодно проводит конкурс среди приглашенных на исполнение самого заветного желания.
Отбор проводится следующим образом: все претенденты рассаживаются на пронумерованных стульях (нумерация стульев начинается с 1) вокруг Большого Круглого стола, после чего посредством Константы счета начинается отсчет по часовой стрелке.
Претендент, на которого падает Константы счета, обязан освободить место, отсчет продолжается до тех пор, пока не останется два человека. 
Требуется при известном числе гостей N и Константы счета С определить номера стульев, которые нужно занять, чтобы попасть в число этих двух "счастливчиков".

Входные данные
В первой строке вводится число N (\(1<=N<=100\))  - количество приглашенных претендентов. Во второй строке вводится Константы счета (\(С<=100\)).

Выходные данные
Необходимо вывести через пробел два числа - номера стульев "счастливчиков".
 

Примеры

№	Входные данные	Выходные данные
1	5 3	2 4

Известны значения роста всех учащихся класса. Определите рост учащегося, который при построении учащихся по росту, в порядке возрастания, занимал бы 10-е место при счете от самого высокого ученика.

Нельзя использовать встроенную сортировку.
 
Выходные данные
Необходимо вывести на экран значение роста учащегося, который бы занимал 10-е место по росту в порядке убывания, при счете от самого высого ученика.
 

Пример

№	Входные данные	Выходные данные
1	12 148 144 154 145 155 130 157 136 152 130 177 166	136

 

Примеры

№	Входные данные	Выходные данные
1	5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1	12
2	2 3 4 5 1 1 1	4

 

Примеры

№	Входные данные	Выходные данные
1	ABBCDA A*CDA	YES
2	AADAAVA A*DA*AA*	NO

7	8	9
4	5	6
1	2	3
	0

 

Примеры

№	Входные данные	Выходные данные
1	2	16

 

Примеры

№	Входные данные	Выходные данные
1	6 3 29 5 5 28 6	3

 

Примеры

№	Входные данные	Выходные данные
1	3 4 1 1 1 1 5 2 2 100 9 4 2 1	8

 

 

Примеры

№	Входные данные	Выходные данные
1	abab abababcab	2

Пояснение: подстрока abab встречается во второй строке дважды, начиная с 1-го и 3-го символа.

 

Примеры

№	Входные данные	Выходные данные
1	hgdfjgkdghkdjgkgkd1543gjdlgkdjlg	URA
2	1=5 4=3	NO

 

Примеры

№	Входные данные	Выходные данные
1	6 3 3 -5 7 4 9 6 1 4 1 2 2 3 1 5 3 5 2 5	2 1 1 2 2 2

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

Инна любит гулять по крышам. Она стоит на крыше здания с номером 1 и хочет попасть на крышу здания с номером n.

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

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

Формат входных данных
В первой строке задано натуральное число n — число зданий в Иннополисе (n<= 10⁵). В следующих n строках заданы крыши зданий. Каждая из этих строк содержит четыре целых числа x_i1, y_i1, x_i2 и y_i2 — координаты противоположных вершин прямоугольника, описывающего крышу здания (x_i1 < x_i2; y_i1 < y_i2) Гарантируется, что никакие два прямоугольника не имеют общих точек. Все координаты — неотрицательные целые числа и <= 10⁹

Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которые Инна должна совер- шить, чтобы добраться с крыши здания 1 до крыши здания n. Если же Инна не может добраться до крыши n-го здания, выведите -1.

Ввод	Вывод
4 0 0 3 2 1 6 4 8 1 3 4 5 7 7 10 9	3
3 0 0 3 2 1 3 4 5 7 7 10 9	-1