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

Способ убедиться в правильности утверждения Витя избрал довольно оригинальный. Он взял аквариум с основанием длиной N и шириной 1, очень высокими стенками, и поставил N –1 перегородку параллельно узкой боковой стенке аквариума, тем самым, разделив аквариум на N одинаковых отсеков. Каждая перегородка имеет ширину 1 и очень большую высоту. Толщиной перегородки можно пренебречь. В каждой из перегородок есть точечное отверстие на высоте H_i, диаметром которого также можно пренебречь. После всех этих приготовлений Витя медленно наливает в первый отсек (между стенкой и 1ой перегородкой) C литров воды. В часть аквариума размером 1x1x1 вмещается ровно один литр воды. Так как стенки и перегородки в аквариуме были очень высокими, то через край вода не переливалась. После установления стационарного состояния он замерил уровень жидкости в каждом из N сосудов.

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

Рассмотрим подробно случай N = 3. Пусть сначала H₁ < H₂. Как только жидкость в первом отсеке достигнет уровня первого отверстия, вода станет поступать во второй отсек до тех пор, пока уровни в обоих отсеках не сравняются (или уровень воды в первом отсеке окажется равным H₁, тогда во втором отсеке он будет на уровне С – H₁). Далее уровень жидкости в первых двух частях будет увеличиваться равномерно (или не будет меняться). Как только вода достигнет второго отверстия, вся она будет поступать в третий отсек, опять же до тех пор, пока уровни жидкости во всех трех частях не сравняются или вода в первых двух отсеках достигнет уровня H₂. После этого, если воды оказалось достаточно, весь аквариум будет заполняться равномерно.

Пусть теперь H₁ > H₂. Как только жидкость в первом отсеке достигнет уровня первого отверстия, вся вода станет поступать во второй отсек. Если после этого уровень во втором отсеке сравняется с уровнем второго отверстия, то вода станет выливаться в третий до тех пор, пока высоты жидкостей во втором и третьем отсеках не станут равными. Далее уровень воды в них будет равномерно увеличиваться, пока не достигнет первого отверстия. После этого весь аквариум будет заполняться равномерно.

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

Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.

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

abc
acb

симпатичными являются все части, состоящие из одного квадратика (их 6), а также части

bc и a

cb и a

Напишите программу, которая по информации о шедевре Васи определит его стоимость.

Мосгортранс в честь дня своего рождения решил провести соревнования, и, по аналогии с «Бегущим городом» назвать их «Ездящий город».

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

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

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

Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.

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