Алгоритмы

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.

Входные данные
В первой строке находится число N. В следующих N строках содержатся по N цифр без пробелов. 2 <= N <= 250.

Выходные данные
Выводятся N строк по N символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.

Дана строка, состоящая из M попарно различных символов. Вывести все перестановки символов данной строки.

Входные данные
В первой строке находится исходная строка. 2 <= M <= 8, символы - буквы латинского алфавита и цифры.

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

Для натуральных чисел a и n вычислить aⁿ.

Входные данные
В первой строке находятся разделённые пробелом a и n. 1 <= a <= 9, 1 <= n <= 7000.

Выходные данные
Выводится одно число - результат без стоящих впереди нулей, стоящих впереди и позади пробелов.

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

Входные данные
В четырёх строках находятся пары чисел - координаты точек. Числа в первых трёх строках - это координаты вершин треугольника, в четвёртой строке - координаты тестируемой точки. Координаты вершин - целые числа, для любой точки выполняются следующие условия: -10 000 <= x, y <= 10 000.

Выходные данные
Вывести слово "In", если точка находится внутри треугольника, или "Out" - если снаружи.

Даны N целых чисел X₁, X₂, ..., X_N. Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S.

Входные данные
В первой строке находятся числа N и S. В следующей строке - N чисел через пробел. 2 <= N <= 24, 0 <= X_i <= 50 000 000, -1 000 000 000 <= S <= 1 000 000 000.

Выходные данные
Если получить требуемый результат невозможно, вывести "No solution", если можно, то вывести равенство. Если решение не единственное, вывести любое.

Дан неориентированный граф без кратных ребер и петель. В нем уже содержится некоторое (возможно, нулевое) количество ребер. Можно за определенную плату добавлять в него новые ребра (плата своя для каждого ребра). Требуется за наименьшую плату сделать граф связным.

Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество вершин в исходном графе. Далее в N строках записано по N неотрицательных целых чисел в каждой ( j -е число в i -й строке соответствует стоимости добавления ребра, соединяющего вершины i и j, 0 соответствует уже существующему ребру, положительное число – несуществующему), числа не превышают 100. Матрица симметрична.

Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.

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

Входные данные
В первой строке входных данных содержится одно целое число N
 (1 ≤ N ≤ 50) – количество точек. Далее в N строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число M – количество уже существующих отрезков. В следующих M строках записаны по 2 числа – номера начала и конца соответствующего отрезка.

Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения с точностью 5 знаков после запятой.

Дан неориентированный граф без кратных ребер и петель. В нем уже содержится некоторое (возможно, нулевое) количество ребер. Можно за определенную плату добавлять в него новые ребра (плата своя для каждого ребра). Требуется за наименьшую плату сделать граф связным.

Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество вершин в исходном графе. Далее в N строках записано по N положительных целых чисел в каждой ( j -е число в i -й строке соответствует стоимости добавления ребра, соединяющего вершины i и j ), числа не превышают 100. В следующих N строках записаны по N чисел, каждое из которых является единицей или нулем (1, если вершины соединены, и 0, если не соединены). Обе матрицы симметричны.

Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.

Будем называть цепочкой слов длины n последовательность слов w₁, w₂, …, w_n, такую, что для всех i от 1 до n – 1 слово w_i является собственным префиксом слова w_i+1.

Слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u. Например, «program» является собственным префиксом слова «programmer».

Задано множество слов S = {s₁, s₂, …, s_m} и последовательность чисел x[1], x[2], …, x[k]. Требуется найти такие числа l и r (l ≤ r), что s_x[l], s_x[l + 1], …, s_x[r – 1], s_x[r] является цепочкой слов, и количество слов в цепочке (число r – l + 1) максимально.

Входные данные
Первая строка входного файла содержит целое число m (1 ≤ m ≤ 250 000). Каждая из следующих m строк содержит по одному слову из множества S.

Все слова не пусты, имеют длину, не превосходящую 250 000 символов, и состоят только из строчных букв латинского алфавита. Суммарная длина всех слов не превосходит 250 000.

Следующая строка содержит число k (1 ≤ k ≤ 250 000). Последняя строка входного файла содержит k чисел — последовательность чисел x[1], x[2], …, x[k] (для всех i выполнено 1 ≤ x[i] ≤ m).

Выходные данные
Выведите в первой строке выходного файла два числа: l и r. Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.

Строительная компания хочет построить дом, в котором будет n квадратных комнат. Каждая комната характеризуется своим размером — длиной стены. Обозначим размеры комнат в новом доме как a₁, a₂, …, a_n.

При этом для того, чтобы квартиры в доме активнее распродавались, компания объявила его «Домом оригинальности и гармонии». Оригинальность означает, что размер любой комнаты не должен делиться на размер никакой другой комнаты. Свойство гармонии требует, чтобы площадь любой комнаты делилась на размер каждой из комнат. Иначе говоря, для любых различных i и j должны выполняться условия: ai не делится на a_j, а a_i² делится на a_j.

Требуется по заданному числу n выбрать такие размеры комнат, чтобы выполнялись свойства оригинальности и гармонии. При этом с целью экономии строительных материалов размер каждой комнаты не должен превышать 2⁶³ – 1.

Входные данные
Строка содержит число n (1 ≤ n ≤ 1000).

Выходные данные
Выведите размеры комнат — n положительных целых чисел, не превосходящих 2⁶³ – 1. Разделяйте числа пробелами.

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

Восстановите нарисованный Васей многоугольник.

Входные данные
В первой строке входных данных содержатся два натуральных числа: Y - количество строк и X - количество столбцов листа (3 <= Y <= 1000, 3 <= X <= 1000). В каждой из следующих Y строк задается по X целых неотрицательных чисел, не превосходящих 4. Ни одна из сторон многоугольника не проходит по границе листа бумаги.

Выходные данные
Выведите искомый многоугольник в следующем формате.

Выходные данные должны содержать Y строк по 2X-1 символов в каждой (по одному символу на клетку и линию между клетками).

В первой строке выведите вертикальные отрезки в верхнем ряду клеток, обозначая их символом | (вертикальная черта - символ с кодом 124) и горизонтальные отрезки, отделяющие первый ряд клеток от следующего, обозначая их символом _ (подчеркивание). Если соответствующий отрезок в данном многоугольнике отсутствует, выведите вместо него символ . (точка). Во второй строке выведите в том же формате вертикальные отрезки во втором ряду и горизонтальные отрезки, отделяющие второй ряд от третьего. И т.д. В каждой строке на нечетных местах могут стоять только символы точка или подчеркивание, на четных местах - символы точка или вертикальная черта.

Гарантируется, что хотя бы одно решение существует. Если решений несколько, выведите любое из них.

Недавно Петя научился считать. Он тут же заметил, что число 2 обладает замечательным свойством - 2 + 2 = 2 × 2. Его старший брат Ваня тут же объяснил ему, что дело не в двойке.

"Дело в том, что последовательность 2, 2 - волшебная," - сказал Пете Ваня. - "Волшебная последовательность - это такая последовательность натуральных чисел, что сумма ее членов равна их произведению. Например последовательность 1, 2, 3 - тоже волшебная."

Петя тут же сложил 1, 2 и 3, потом перемножил их и обрадовался.

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

Входные данные
В первой строке входных данных содержится целое число N (2 <= N <= 100).

Выходные данные
Выведите любую волшебную последовательность длины N. Разделяйте числа пробелами. Члены последовательности не должны превышать 10⁹. Если такой волшебной последовательности длины N не существует, выведите единственное число - "-1".

Компания Macrohard выпустила новую версию своего редактора Nottoobad, который понимает некоторые голосовые команды. К сожалению, этих команд всего две - "повторить последнее слово" и "стереть последний символ". Причем при исполнении команды "повторить последнее слово" редактор автоматически вставляет пробел, который разделяет слова.

Однако компания утверждает, что с помощью этого редактора можно набирать текст, нажимая клавиши на клавиатуре гораздо реже. Например, чтобы набрать фразу "this thin thing" достаточно нажать на клавиши на клавиатуре всего 6 раз:


Чтобы повысить популярность своего продукта, компания решила провести конкурс, победителем которого станет тот, кто сможет набрать заданный набор слов в редакторе за наименьшее количество нажатий на клавиши. Причем первое слово зафиксировано, а остальные могут быть набраны в произвольном порядке. То есть, если надо набрать слова "apple", "plum" и "apricote", то первым надо набрать "apple", а слова "plum" и "apricote" можно поменять местами.

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

Входные данные
В первой строке входных данных задано число N (1 <= N <= 100) – количество слов, которые предстоит набрать. Следующие N строк содержат слова – последовательности маленьких латинских букв, не длиннее 100 символов. Помните, что первое слово необходимо набрать первым!

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

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

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

Входные данные
В первой строке вводится число n - количество селений (1 <= n  <= 100000). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения. В третьей строке входных данных задается число m - количество бомбоубежищ (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища. Все расстояния положительны и не превышают 10⁹. Селение и убежище могут располагаться в одной точке.

Выходные данные
Выведите n чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.

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



Для задания конфигурации головоломки удобно рассмотреть ее развертку - "разрезать" поверхность цилиндра вдоль вертикальной линии, проходящей по границам квадратиков, и обозначить черные клетки символом "1", а белые - символом "0". Пусть, например, одна из возможных разверток головоломки, приведенной на рисунке, следующая (на рисунке видно только первые три столбца этой развертки):
        000110 001110 101000 001000 011111 011110
Задача решающего головоломку состоит в том, чтобы, поворачивая слои, добиться того, чтобы все вертикальные столбцы были различны. Например, головоломка приведенная выше, не решена, поскольку два из ее столбцов (четвертый и пятый на приведенной развертке) одинаковы. Если же повернуть нижний слой влево на один квадратик, развертка головоломки примет следующий вид:
        000110 001110 101000 001000 011111 111100
Теперь все столбцы различны и, следовательно, головоломка решена.

Для того, чтобы решать головоломку было интереснее, на ее раскраску наложено дополнительное условие: нельзя повернуть один из слоев головоломки меньше, чем на полный оборот таким образом, что внешний вид головоломки останется тем же. Так, например, для n  = 6 слой с раскраской "010101" не разрешается, поскольку при его повороте на 2 квадратика внешний вид головоломки не меняется.

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


Входные данные
В первой строке вводится число n  - количество слоев в головоломке и количество квадратиков в одном слое (1 <= n  <= 200). Следующие n
 строк содержат по n  символов, каждый из которых равен 0 или 1 - развертку головоломки.

Выходные данные
Если решить головоломку можно, в первой строке выведите слово "Yes". В этом случае следующие n  строк должны содержать произвольную развертку решенной головоломки.

Если решить головоломку нельзя, выведите в первой и единственной строке выходных данных слово "No".

 

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

В ряд выписаны n чисел. Требуется поставить между каждой парой соседних чисел один из знаков "+" или "×" таким образом, чтобы значение получившегося выражения было как можно больше. Использовать скобки не разрешается.

Например, для последовательности чисел 1, 2, 3, 1, 2, 3 оптимально расставить знаки следующим образом: 1 + 2 × 3 × 1 × 2 × 3. Значение выражения в этом случае равно 37.

Входные данные
В первой строке вводится число n (2 <= n <= 200000). Вторая строка содержит n целых чисел - числа, между которыми следует расставить знаки. Все числа находятся в диапазоне от 0 до 10⁹.

Выходные данные
Выведите оптимальное выражение. В качестве знака "×" выводите символ "*" (звездочку). Если оптимальных решений несколько, выведите любое из них.

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

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

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

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

Задание
Напишите программу, которая:
<> * читает из стандартного ввода количество поселков, количество дополнительных пилорам, которые будут установлены, количество срубленных в каждом поселке деревьев и описание рек,
*вычисляет минимальную стоимость сплава деревьев после установки дополнительных пилорам,
*выводит результат в стандартный вывод.

Входные данные
Первая строка входных данных содержит два целых числа: n — количество поселков, не считая Байттауна (2 ≤ n ≤ 100), и k
 — количество дополнительных пилорам, которые будут установлены (1 ≤ k ≤ 50 и k ≤ n). Поселки нумеруются числами 1 , 2 ,...., n , а Байттаун имеет номер 0.

Каждая из последующих n строк содержит три целых числа, разделенных одним пробелом. Строка i + 1 содержит:

w_i — количество деревьев, срубаемых в поселке i за год (0 ≤ w_i ≤ 10 000),
v_i — ближайший поселок (либо Байттаун) вниз по реке от поселка i (0 ≤ v_i ≤ n),
d_i — расстояние (в километрах) по реке от поселка i до поселка v_i (1 ≤ d_i ≤ 10 000).
Гарантируется, что суммарная стоимость сплава всех деревьев к пилораме в Байттауне не превосходит 2 000 000 000 центов в год.
В 50% тестов число n не превосходит 20.

Выходные данные
Первая и единственная строка выходных данных должна содержать одно целое число: минимальную стоимость сплава (в центах).

Пояснения


Рисунок сверху иллюстрирует входные данные примера. Номера поселков указаны внутри кругов. Числа под кругами обозначают количество деревьев, срубаемых вблизи данного поселка. Числа над стрелками указывают длины рек.

Пилорамы должны быть установлены в поселках 2 и 3.

Вы можете предполагать, что суммарное время работы библиотеки в процессе тестирования не будет превышать 4 сек.

Загрузить библиотеку для тестирования

Рассмотрим игру для двух игроков. Игрокам дан прямоугольник размером x × y (где x и y — положительные целые числа). Игроки ходят по очереди. Ход состоит в разделении прямоугольника на два прямоугольника одним горизонтальным или вертикальным разрезом. Полученные прямоугольники должны иметь положительные целочисленные размеры.


                  Возможные разрезы прямоугольника размером 4 × 3.

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

Ваша задача — написать программу, которая бы играла в игру с прямоугольниками и выигрывала. Для того чтобы играть, программа должна использовать специальную библиотеку. В библиотеке есть функции dimension_x() и dimension_y(), возвращающие размеры прямоугольника. Начальные размеры прямоугольника — целые числа от 1 до 100 000 000. Как минимум один из размеров больше 1. К тому же, в 50% тестов размеры прямоугольника не будут превышать 25.

В библиотеке есть также процедура cut(dir, position), которая должна вызываться вашей программой, чтобы сделать ход. Параметры dir и position описывают направление и позицию разреза соответственно. Параметр dir может принимать одно из двух значений: vertical и horizontal. Если dir = vertical, то проводится вертикальный разрез, а параметр position указывает x - координату разреза, как показано на рисунке выше. При этом вы должны гарантировать выполнение неравенства 1 ≤ position  ≤ dimension_x()− 1. Если dir = horizontal, то проводится горизонтальный разрез, а параметр position указывает y ? координату разреза. При этом, вы должны гарантировать выполнение неравенства 1 ≤ position  ≤ dimension_y()− 1.

После запуска вашей программы она будет играть за одного из игроков. Ваша программа ходит первой, она должна разрезать исходный прямоугольник. Когда ваша программа вызывает процедуру cut, ваш ход записывается и управление передается программе соперника. После хода соперника управление возвращается вашей программе. Значения, которые возвращаются функциями dimension_x() и dimension_y(), будут отражать результат вашего хода и хода соперника. Как только ваша программа выигрывает, проигрывает или делает неправильный ход, ее исполнение будет прервано. Прерывание вашей программы — это автоматический процесс, так что ваша программа должна продолжать делать столько ходов, сколько возможно до автоматического прерывания ее исполнения. Вы можете предполагать, что для предложенных входных данных всегда существует выигрышная стратегия для вашей программы.

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

Экспериментирование

Для того, чтобы дать вам возможность поэкспериментировать с библиотекой, в ваше распоряжение предоставлены примеры библиотек: их исходные тексты находятся в файлах preclib.pas, creclib.c и creclib.h . Эти библиотеки вы можете взять по адресу: http :// contest / . Они реализуют очень простую стратегию. Когда вы запустите вашу программу, она будет играть против этих простых соперников. Вы можете изменять их, чтобы протестировать вашу программу с лучшими соперниками. Следует учесть, что во время тестирования после окончания тура, ваша программа будет играть против другого соперника.

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

Если вы модифицируете часть implementation библиотеки preclib.pas, пожалуйста, перекомпилируйте её, используя команду ppc386 -O2 preclib.pas. Эта команда создаст файлы preclib.o и preclib.ppu. Эти файлы необходимы для компиляции вашей программы и должны быть в помещены в каталог, где находится ваша программа. Пожалуйста, не модифицируйте часть interface библиотеки preclib.pas.

Если вы модифицируете библиотеку creclib.c, пожалуйста, не забудьте поместить ее вместе с creclib.h в каталог, где находится ваша программа, — они необходимы для компиляции. Пожалуйста, не модифицируйте файл creclib.h.

В ваше распоряжение также предоставляются две простые программы, которые иллюстрируют использование библиотек crec.c и prec.pas. Пожалуйста, помните, что эти программы не являются правильными решениями. Вы можете откомпилировать их, используя такие команды:

gcc -O2 -static crec.c creclib.c -lm
g++ -O2 -static crec.c creclib.c -lm
ppc386 -O2 -XS prec.pas

Библиотеки

В ваше распоряжение предоставлены библиотеки, которые обеспечивают следующую функциональность:

Библиотека для FreePascal (preclib.ppu, preclib.o)
type direction = (vertical, horizontal);
function dimension_x(): longint;
function dimension_y(): longint;
procedure cut(dir: direction; position: longint);

 
Включите следующий оператор в ваш исходный файл rec.pas:
uses preclib;
Чтобы откомпилировать вашу программу, скопируйте файлы preclib.o и reclib.ppu в каталог, где находится ваш исходный файл, и выполните следующую команду:
ppc386 -O2 -XS rec.pas
Файл prec.pas является примером использования библиотеки preclib.

Библиотека для GNU C/C++ (creclib.h, creclib.c)

typedef enum __direction {vertical, horizontal} direction;
int dimension_x();
int dimension_y();
void cut(direction dir, int position);



Включите следующий оператор в ваш исходный файл (rec.c или rec.cpp):
#include ”creclib.h”
Чтобы откомпилировать вашу программу, скопируйте файлы creclib.c и creclib.h в каталог, где находится ваш исходный файл, и выполните следующую команду:
gcc -O2 -static rec.c creclib.c –lm
или:
g++ -O2 -static rec.cpp creclib.c –lm
Файл crec.c является примером использования библиотеки в C.
Пример взаимодействия

Ниже приведен пример взаимодействия вашей программы с библиотекой. Он показывает, как может проходить игра. Игра начинается с прямоугольника размером 4 × 3. Существует выигрышная стратегия для этого случая.
 

Ваша программа вызывает	Что происходит
dimension_x()	возвращает 4
dimension_y()	возвращает 3
cut(vertical, 1)	ваш разрез записывается, и прямоугольник размером 3 × 3 передается вашему сопернику, который разрезает его и получается прямоугольник размером 3 × 2; после этого управление передается вашей программе
dimension_x()	возвращает 3
dimension_y()	возвращает 2
cut(horizontal, 1)	ваш разрез записывается, и прямоугольник размером 3 × 1 передается вашему сопернику, который разрезает его и получается прямоугольник размером 2 × 1; после этого управление передается вашей программе
dimension_x()	возвращает 2
dimension_y()	возвращает 1
cut(vertical, 1)	в результате вашего разреза получается прямоугольник размером 1 × 1, так что вы выиграли; после этого работа вашей программы автоматически прекращается.

Сегодня день рождения Никиты. На празднование дня рождения приглашены n детей (включая самого Никиту). Все дети пронумерованы числами от 1 до n. Работники МакДональдса приготовили большой круглый стол и поставили вокруг него n стульев.

Как только дети приходят на день рождения, они рассаживаются за столом. Ребенок с номером 1 занимает одно из мест. Ребенок с номером 2 занимает место слева от ребенка с номером 1. Ребенок с номером 3 занимает следующее за ним место слева и так далее. Наконец, ребенок с номером n
 займет оставшееся свободное место между детьми с номерами n – 1 и 1.

Работники МакДональдса хорошо знают, что некоторые из приглашенных детей ведут себя весьма шумно за столом, если сидят друг с другом. Поэтому работники ресторана собираются пересадить детей в некотором порядке. Этот порядок описывается перестановкой p₁, p₁,..., p_n (p₁, p₂,..., p_n — различные целые числа от 1 до n). То есть, ребенок p₁ должен сидеть между p_n и p₂, ребенок p_i (i = 2, 3, ... , n − 1) должен сидеть между p_i-1 и p_i+1; ребенок p_n должен сидеть между p_n-1 и p1.

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

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

Имейте в виду, что ребенок p_i может сидеть как слева, так и справа от ребенка pn.

Задание
Ваша задача — написать программу, которая:
· читает из стандартного ввода количество детей и перестановку, определяющую желаемый порядок рассадки детей,
· вычисляет минимально возможную величину беспорядка,
· выводит результат в стандартный вывод.

Входные данные
В первой строке стандартного ввода содержится единственное целое число n (1 ≤ n ≤ 1 000 000). Во второй строке содержатся n целых чисел p₁, p₂,..., p_n, разделенных одним пробелом. Числа p₁, p₂,..., p_n образуют перестановку множества {1, 2, ... , n}, описывающую желаемый порядок рассадки детей. Кроме того, в 50% тестов число n не будет превышать 1 000.

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

Пояснения

На рисунке слева изображена исходная рассадка детей. На рисунке в середине показан результат пересаживания, при котором дети с номерами 1 и 2 перемещаются на одно место, дети с номерами 3 и 5 перемещаются на два места и дети с номерами 4 и 6 не меняют своего положения. Требуемые условия рассадки выполнены, поскольку 3-й сидит между 6-м и 4-м, 4-й сидит между 3-м и 5-м, 5-й сидит между 4-м и 1-м, 1-й сидит между 5-м и 2-м, 2-й сидит между 1-м и 6-м и 6-й сидит между 2-м и 3-м. Также существует другой вариант конечной рассадки детей, изображенный на рисунке справа. В обоих вариантах величина беспорядка равна 2.

Рассмотрим неубывающую последовательность s₁, ..., s_n + 1 ( s_i <= s_i + 1 для 1 <= i <= n ). Последовательность m₁, ..., m_n, в которой каждый член определен как m_i = ½ * ( s_i + s_i + 1 ) для 1 <= i <= n, назовем “средней последовательностью” для последовательности s₁, ... s_n + 1. Например, средняя последовательность для последовательности 1, 2, 2, 4 есть 1.5, 2, 3. Заметим, что элементы средней последовательности могут быть дробными числами. Тем не менее, в данной задаче используются только те средние последовательности, в которых все числа целые. Для заданной неубывающей последовательности из n целых чисел m1, ..., mn необходимо вычислить количество всех неубывающих последовательностей из n + 1 целых чисел s₁, ..., s_n + 1, для которых заданная последовательность m₁, ..., m_n является средней последовательностью.

Задание
Напишите программу, которая:

• читает из стандартного ввода неубывающую последовательность целых чисел;
• вычисляет количество всех неубывающих последовательностей целых чисел, для которых заданная последовательность является средней последовательностью;
• выводит ответ в стандартный вывод.

Входные данные
Первая строка стандартного ввода содержит одно целое число n (2 <= n <= 5000000). Оставшиеся n строк содержат значения последовательности m₁, ..., m_n. Строка i + 1 содержит одно целое число mi (0 <= mi <= 1000000000).

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