Поблизости от столицы Флатландии одна компания решила построить коттеджный поселок. Строительная компания, которая занимается возведением коттеджей, решила раскрасить некоторые коттеджи в розовый цвет, а остальные - в голубой. Но они не могут решить какой коттедж раскрасить в какой цвет.

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

Помогите им определить, сколько существует различных симпатичных раскрасок.

В воинской части города Шатров продолжаются занятия по строевой подготовке. На этот раз Андрей Юрьевич выполняет очередное задание своего начальника Павла Андреевича. Для выполнения этого задания, Андрею Юрьевичу необходимо среди всех n солдат, стоящих в одной шеренге, выбрать отряд из k высоких солдат для выполнения строительных работ. В качестве первого шага, Андрей Юрьевич приказал каждому солдату посчитать свой показатель роста. Для этого каждый солдат, стоящий в шеренге, должен посмотреть сначала в одну сторону и посчитать количество солдат в этой части шеренги, которые строго ниже его, потом посмотреть в другую сторону, посчитать такое же количество, и тогда сумма этих двух чисел и будет его показателем роста. На втором шаге, основываясь на этом показателе, Андрей Юрьевич должен выбрать отряд. Поскольку за долгие дни и ночи занятий строевой подготовкой солдаты успели хорошо познакомиться и даже подружиться со своими соседями в шеренге, Андрей Юрьевич решил выбрать в шеренге такой непрерывный подотрезок из ровно k солдат, у которого сумма показателей роста всех солдат максимальна. Обладая информацией о росте каждого солдата в шеренге, помогите Андрей Юрьевичу найти оптимальный подотрезок.

Поразрядная сортировка является одним из видов сортировки, которые работают за линейное от размера сортируемого массива время. Такая скорость достигается за счет того, что эта сортировка использует внутреннюю структуру сортируемых объектов. Изначально этот алгоритм использовался для сортировки перфокарт. Первая его компьютерная реализация была создана в университете MIT Гарольдом Сьюардом (Harold Н. Seward). Опишем алгоритм подробнее. Пусть задан массив строк s ₁ , ..., s _i причем все строки имеют одинаковую длину m . Работа алгоритма состоит из m фаз. На i -ой фазе строки сортируются па i -ой с конца букве. Происходит это следующим образом. Будем, для простоты, в этой задаче рассматривать строки из цифр от 0 до 9. Для каждой цифры создается «корзина» («bucket»), после чего строки s _i распределяются по «корзинам» в соответствии с i -ой с конца цифрой. Строки, у которых i -ая с конца цифра равна j попадают в j -ую корзину (например, строка 123 на первой фазе попадет в третью корзину, на второй — во вторую, на третьей — в первую). После этого элементы извлекаются из корзин в порядке увеличения номера корзины. Таким образом, после первой фазы строки отсортированы по последней цифре, после двух фаз - по двум последним, ..., после m фаз - по всем. При важно, чтобы элементы в корзинах сохраняли тот же порядок, что и в исходном массиве (до начала этой фазы). Например, если массив до первой фазы имеет вид: 111,112,211, 311, то элементы по корзинам распределятся следующим образом: в первой корзине будет. 111,211,311, а второй: 112. Ваша задача состоит в написании программы, детально показывающей работу этого алгоритма на заданном массиве.

Рассмотрим компьютерную сеть с настроенной TCP/IP маршрутизацией. Будем рассматривать некоторую ее модификацию. А именно в этой сети находить N подсетей. Каждая подсеть характеризуется своей маской. Маска подсети представляет собой 4 однобайтных числа, разделенных точкой. Причем для масок выполнено следующее свойство: если представить маску в двоичном виде, то сначала она будет содержать k единиц, а потом q нулей, причем k + q = 32 . Например 255.255.255.0 — маска подсети, а 192.168.0.1 — нет.

Поясним, как получается двоичное представление IP-адреса. Для этого числа, составляющие IP-адрес, представляются в двоичной системе счисления (при этом каждое из них дополняется ведущими нулями до длины 8 цифр), после чего удаляются точки. Получившееся 32-битное число и есть двоичное представление IP-адреса. Например, для адреса 192.168.0.1 этот процесс выглядит так: 192.168.0.1 -> 11000000.10101000.00000000.00000001 -> 11000000101010000000000000000001. Таким образом, двоичным представлением IP-адреса 192.168.0.1 является 11000000101010000000000000000001.

Будем говорить, что два компьютера с IP ₁ и IP ₂ лежат в подсети, если IP ₁ & Mask = IP ₂ & Mask , где Mask — маска этой подсети, а & — операция побитового логического "и". IP компьютера представляет так же 4 однобайтных числа, разделенных точкой.

Вам даны M пар IP-адресов компьютеров. Для каждой из них Вам надо определить, в скольких подсетях из заданных они лежат.

Комната имеет прямоугольную форму размером M × N (1 ≤ M ≤ 9, 1 ≤ N ≤ 9) . Необходимо уложить его паркетом. Есть деревяшки двух форм:

• прямоугольники (2 × 1)
• уголки (квадрат 2 × 2 без одного куска 1 × 1 )

Вы должны найти X — количество способов покрыть пол паркетом (не должно остаться пустых мест; части не должны накладываться друг на друга и выходить за границу комнаты).