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

Компания «Аэротрам» готовит к производству новый самолет «T-239-n». Перед инженерами встала задача спланировать организацию салона, чтобы как можно больше мест было у прохода. Будем использовать следующую упрощенную математическую модель салона самолета. В горизонтальном сечении салон представляет собой прямоугольник длиной l и шириной w сантиметров. Кресло представляет собой прямоугольник размером x на y сантиметров и должно быть расположено в салоне так, чтобы его сторона длиной x была параллельна стороне салона длиной l. Проход представляет собой полосу шириной a, параллельную стороне салона длиной l. Проход идет вдоль всего салона.

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

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

Введем координатную систему таким образом, чтобы ось OY была направлена с юга на север, а ось OX с запада на восток. Берега реки представляют собой ломаные, бесконечные в обе стороны. Левый берег начинается лучом, направленным на юг из точки (x1,1,y1,1), продолжается отрезками (x1,1,y1,1) − (x1,2,y1,2), (x1,2,y1,2)− (x1,3,y1,3), ..., (x1,m−1,y1,m−1) − (x1,m,y1,m) и заканчивается лучом, направленным на север из точки (x1,m,y,m).

Аналогично, правый берег реки начинается лучом, направленным на юг из точки (x2,1,y2,1), продолжается отрезками (x2,1,y2,1) − (x2,2,y2,2), (x2,2,y2,2) − (x2,3,y2,3), ..., (x2,n−1,y2,n−1) − (x2,n,y2,n) и заканчивается лучом, направленным на север из точки (x2,n,y2).

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

В теории кодирования часто используют беспрефиксные коды наборы слов, ни одно из которых не является префиксом (Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова, a, ab и aba являются префиксами слова aba) другого. Например, набор слов aba, aa и bac является беспрефиксным кодом, а набор abac, aba, ba нет, поскольку слово aba является префиксом слова abac.

Профессор Дешифро работает в лаборатории исследования бесполезной информации и изучает свое новое изобретение почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор abac, abс, ba является почти беспрефиксным кодом уровня 2, а набор abac , abab, ba нет, поскольку наибольший общий префикс слов abac и abab имеет длину 3.

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

Недавно на кружке по программированию Петя узнал об обходе в глубину. Обход в глубину используется во многих алгоритмах на графах. Петя сразу же реализовал обход в глубину на своих любимых языках программирования Паскале и Си.

Петина программа хранит граф с использованием матрицы смежности в массиве a (вершины графа пронумерованы от 1 до n). В массиве visited помечается, в каких вершинах обход в глубину уже побывал.

Петя запустил процедуру graph_dfs для некоторого неориентированного графа G с n вершинами и сохранил ее вывод. А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество ребер могло быть в графе G. Помогите ему выяснить это!

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

Купцы хотят продать шаху n драгоценных камней, которые они привезли с собой. Для этого они выкладывают их перед шахом в ряд, после чего шах оценивает эти камни и принимает решение о том, купит он их или нет. Видов драгоценных камней на Востоке известно не очень много всего 26, поэтому мы будем обозначать виды камней с помощью строчных букв латинского алфавита. Шах обычно оценивает камни следующим образом. Он заранее определил несколько упорядоченных пар типов камней: (\(a_1\), \(b_1\)), (\(a_2\), \(b_2\)), ..., (\(a_k\), \(b_k\)). Эти пары он называет красивыми, их множество мы обозначим как P. Теперь представим ряд камней, которые продают купцы, в виде строки S длины n из строчных букв латинского алфавита. Шах считает число таких пар (i,j), что 1 ≤ i < j ≤ n, а камни \(S_i\) и \(S_j\) образуют красивую пару, то есть существует такое число 1 ≤ q ≤ k, что \(S_i = a_q\) и \(S_j = b_q\).

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