Рассмотрим строку \(s\), состоящую из строчных букв латинского алфавита. Примером такой строки является, например, строка «abba».

Подстрокой строки \(s\) называется строка, составленная из одного или нескольких подряд идущих символов строки \(s\). Обозначим как \(W(s)\) множество, состоящее из всех возможных подстрок строки \(s\). При этом каждая подстрока входит в это множество не более одного раза, даже если она встречается в строке \(s\) несколько раз.

Например, \(W\)(«abba») = {«a», «b», «ab», «ba», «bb», «abb», «bba», «abba»}.

Подпоследовательностью строки \(s\) называется строка, которую можно получить из \(s\) удалением произвольного числа символов. Обозначим как \(Y\)(\(s\)) множество, состоящее из всех возможных подпоследовательностей строки \(s\). Аналогично \(W\)(\(s\)), каждая подпоследовательность строки \(s\) включается в \(Y\)(\(s\)) ровно один раз, даже если она может быть получена несколькими способами удаления символов из строки \(s\). Поскольку любая подстрока строки \(s\) является также ее подпоследовательностью, то множество \(Y\)(\(s\)) включает в себя \(W\)(\(s\)), но может содержать также и другие строки.

Например, \(Y\)(«abba») = \(W\)(«abba») ∪ {«aa», «aba»}. Знак ∪ обозначает объединение множеств.

Будем называть строку \(s\) странной, если для нее \(W\)(\(s\)) = \(Y\)(\(s\)). Так, строка «abba» не является странной, а, например, строка «abb» является, так как для нее \(W\)(«abb») = \(Y\)(«abb») = {«a», «b», «ab», «bb», «abb»}.

Будем называть странностью строки число ее различных странных подстрок. При вычислении странности подстрока считается один раз, даже если она встречается в строке \(s\) в качестве подстроки несколько раз. Так, для строки «abba» ее странность равна 7, любая ее подстрока, кроме всей строки, является странной.

Требуется написать программу, которая по заданной строке \(s\) определяет ее странность.

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй — \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).

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

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

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

Прямоугольная детская площадка полностью замощена \(N\) плитками. Все плитки прямоугольные, возможно разного размера. Плитки не перекрываются.

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

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

Дано прямоугольное поле, каждая клетка которого покрашена в какой-то цвет. За один ход необходимо перекрасить все клетки одного цвета в другой цвет. Стоимость перекраски одной клетки зависит от номера хода и задается функцией: \(F(i) = ((A \cdot F(i-1)+B) \bmod~C) + 1\), \(F_1\) – известная стоимость первого хода.

Необходимо за минимальное количество ходов перекрасить все поле в один цвет так, чтобы общая стоимость перекраски была бы максимальной.

В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c _i , время его завоза в магазин a _i и время его вывоза из магазина b _i .

У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m _j , время s _j , которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k _j , которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k _j , при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.

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