Фирма «Kel-Morian Productions» разрабатывают искусственный интеллект для новой автоматизированной модели промышленного робота SCV-2. На данном этапе создается робот для строительства и ремонта стен, составленных из стандартных строительных блоков.

Для начала было принято решение сделать упрощенную модель робота, который будет работать со стенами, состоящими из блоков одинакового размера. Стена представляет собой последовательность столбиков, составленных из блоков, пример такой стены приведен на рисунке 1.

Рисунок 1

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

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

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

Рисунок 2

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

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

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

Флот инопланетян прилетел с северо-востока, и застыл в таком положении, что все оси кораблей направлены строго на юго-запад.

Единственный способ нанести урон инопланетной армии – это пустить из некоторой точки поверхности Земли лазерный луч вертикально вверх. Пущенный так луч прожигает насквозь все вражеские корабли, через которые он проходит (даже те, которые он задевает по границе). Но этот выстрел повредит инопланетянам только в случае, если все n кораблей будут при этом поражены.

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

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

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

«Ну не гномы, а наказание какое-то!», – подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь – другой уже проснулся! И так всю ночь.

У Белоснежки \(n\) гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать \(i\)-го гнома нужно \(a_i\) минут, и после этого он будет спать ровно \(b_i\) минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.

Например, пусть есть всего два гнома, \(a_1\) = 1, \(b_1\) = 10, \(a_2\) = 10, \(b_2\) = 20. Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.

Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены \(n\) кружочков, помеченных числами от 1 до \(n\). Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка a в кружочек \(b\) разрешено проводить, если выполнены два условия:

1. еще нет стрелочки из \(a\) в \(b\);

2. нельзя дойти по стрелочкам из \(b\) в \(a\).

Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).

Проигрывает тот, кто не может сделать ход.

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