Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача A. Перестановки

Задачу добавил: alef

Успешно сдано решений: 2

В некотором царстве-государстве правил царь Гордей. Славился он своим умением улаживать разные споры и ссоры. А применять это умение приходилось ему часто — уж такие соседи-цари попались. Что ни месяц — очередные посланники к Гордею спешат: то царь Пантелеймон сердит на князя Евсея, что пчелы с приграничной пасеки князя на луга его царства залетают, то царице Марфе покоя не дают на лягушачьи концерты, что из вотчины царя Пантелеймона раздаются. А иной раз и из дальних стран гости за тем же пожалуют.

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

А однажды прибыл к Гордею посланник императора Чунь Линя. Говорил витиевато, да подробно — то про короля Лоренсо расскажет, то про правителя Кинич-Эб-Шока. И, как бы между прочим, заметил, какое зеркало роскошное, и место такому во дворце императорском, и поинтересовался, не подарит ли царь императору это зеркало в знак дружбы. Выслушал его Гордей и стал ответное слово говорить. Долго говорил, как уважает он императора, дорожит его предолжением дружбы, и, конечно же, примет его. Только вот с зеркалом проблема — оно подарено, а местные обычаи таковы, что нельзя передаривать дареное. Кивал посланник с почтением, что, разумеется, обычаи уважать надо. И лишь в глазах его мелькнуло что-то. Пообещал Гордей, что подумает, а сам вызвал министра дел иностранных да велел ему разузнать про зеркало — нет ли в нем какой тайны и что у него за история.

Отправил министр в страну заморскую депешу с просьбой о зеркале рассказать. Да только не знали ничего о зеркале в стране заморской, однако сообщили министру, что привезли это зеркало из другой страны, может там про него что знают. Разузнал все же министр, где и какой мастер это зеркало изготовил. Дело деликатное, нужно к мастеру надежного человека посылать. И дело срочное, так что придется ковер-самолет у соседа короля Григория одолжить. Доложил министр обо всем царю, и отправился царь к соседу своему с просьбой.

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

Расписание полетов ковра-самолета на ближайшее время выглядит как последовательность символов. Если ковер-самолет в некоторый час свободен, на соответствующем месте в последовательности стоит символ *. Если ковер-самолет занят по важному делу, которое никак нельзя перенести, в последовательности стоит символ X (латиница). Если же ковер-самолет занят, но полет можно перенести, в последовательности стоит либо символ А, либо символ В. Так, например, фрагмент последовательности AAA**XXXXXAABBB означает, что сначала ковер-самолет арендован на 3 часа на некоторое мероприятие, после этого он 2 часа свободен, потом арендован на 5 часов на важное мероприятие (или мероприятия), затем на 2 часа на третье мероприятие и, наконец, на 4 часа еще на одно мероприятие. При этом все мероприятия, кроме второго, могут быть передвинуты в рамках расписания.

Король Григорий и царь Гордей решили, что не станут даже пытаться перенести полеты, отмеченные как X. А полеты, помеченные как A и B, попробуют перенести на свободное время, не меняя их относительного порядка. При этом, поскольку неизвестно, сколько времени потребуется надежному человеку на выяснение всех обстоятельств, нужно выделить для этого полета максимально возможный отрезок времени.

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


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

Первая строка содержит расписание полетов на ближайшее время — последовательность символов *, X, A, B.

В последовательности содержится не менее одного и не более 10^5 символов.


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

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



Пример входного файла

**XAABBBAA*A*XXX*B***XX**X*


Пример выходного файла

10 3


Сдать задачу

Задать вопрос жюри по этой задаче