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

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

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

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

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

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

Требуется написать программу, которая определяет, в каком интервале может находиться частота звучания треугольника.

Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из \(n\) деталей, пронумерованных от 1 до \(n\), при этом деталь с номером \(i\) изготавливается за \(p_i\) секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

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

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

Небольшая компания «Домострой» также решила выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов. Блок представляет собой параллелепипед размером \(1\times1\times L\), на одной из сторон которого есть место для рекламы — пространство размера \(1\times L\), в которое можно вписать ровно \(L\) букв латинского алфавита.

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

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

После того, как некоторое число \(K\) блоков, каждый из которых имеет длину \(L\), поставили друг на друга, получилась прямоугольная таблица размером \(K\times L\), в каждой клетке которой находится буква латинского алфавита. Каждый рекламный блок соответствует строке этой таблицы. Теперь содержимое этой таблицы выписывается по столбцам, начиная с самого левого. При этом в каждом столбце буквы выписываются сверху вниз. В случае, изображённом на рисунке, в результате этого процесса получилась бы строка «TOEIIZENITKN». Необходимо, чтобы рекламная надпись, требуемая заказчику, входила в получившуюся строку как подстрока «TOEIIZENITKN».

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

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

• высота замка (всегда целое положительное число) должна быть строго больше высот замков его вассалов (для соблюдения субординации).
• замки первого из двух вассалов и всех вассалов этого вассала должны быть построены слева, второго вассала и его вассалов – справа (для пресечения междоусобиц). Это правило должно выполняться для всех
• высота замка должна быть минимально возможной (для экономии ресурсов)
• число всех подчиненных (непосредственно или через промежуточных) у правого и левого вассалов одинаково (для баланса сил).

Для удобства замки феодалов занумерованы натуральными числами по порядку слева направо, начиная с единицы, и разбиты на улицы. Улица (i, j) представляет собой последовательность подряд идущих замков, начиная с замка под номером i и заканчивая замком с номером j (i ≤ j)

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