Задача A. Школа танцев ≡

Условие

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

Формат входного файла

В первой строке входного файла задано число n. Во второй строке задается описание построенного ряда из мальчиков и девочек — строка из n символов a и b (символ a соответствует девочке, а символ b — мальчику).

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 10⁶

Примеры тестов

3
bab

2

8
abbababa

13

Задача B. Стеклянный забор ≡

Условие

В известном городе Санкт-Тверь решили построить новый микрорайон, представляющий в плане прямоугольную область. Границы микрорайона и его улицы по проекту ориентированы строго по сторонам света, причем улицы разбивают микрорайон на кварталы размером 1 км  ×  1 км.

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

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

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

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

Формат входного файла

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

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

Формат выходного файла

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

Ограничения

4 ≤ n ≤ 10⁵, n четное

Примеры тестов

8
0 0
9 0
9 9
6 9
6 3
3 3
3 6
0 6

6
0 0
9 0
9 9
6 9
6 6
0 6

Задача C. Несчастливые номера ≡

Условие

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

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

Счастливым он считал тот номер, сумма некоторых цифр которого равнялась сумме оставшихся цифр. В его представлении билет с номером 561743 счастливый, так как 5+1+4+3=6+7.

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

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

Формат входного файла

Входной файл содержит пару значений n и k.

Формат выходного файла

Выведите искомое количество несчастливых билетов или 0, если такое число вам получить не удалось.

Ограничения

3 ≤ n ≤ 100

1 ≤ k ≤ 9

Примеры тестов

1 7
4 3
50 8
11 9

7
164
0
50184219171