eolymp
bolt
Try our new interface for solving problems
Məsələlər

Тестирование шаффл-машин

Тестирование шаффл-машин

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

У Сергея Михайловича очень интересная работа. Он занимается тестированием шаффл-машин - механизмов, используемых для тасования стопок карточек.

Машины, которые тестирует Сергей Михайлович, осуществляют перестановку стопок из n карточек, где n - чётное натуральное число. Механизм, по которому они работают, состоит в применении к исходной стопке определённой последовательности преобразований, каждое из которых имеет один из двух типов - U или D.

U-преобразование производится следующим образом. Сначала исходная стопка из n карточек делится на две части, первая из которых состоит из n / 2 верхних карточек, а вторая - из n / 2 нижних. Затем в результирующую стопку поочерёдно помещается по одной карточке из каждой из двух частей, начиная с первой. D-преобразование отличается от U-преобразования только тем, что на втором шаге результирующая стопка начинает формироваться, начиная не с первой части, а со второй.

Если мы пронумеруем карточки сверху вниз числами 1, 2, ..., n, то в результате U-преобразования карточки будут следовать сверху вниз в порядке 1, n / 2 + 1, 2, n / 2 + 2, ..., n / 2, n, а в результате D-преобразования порядок карточек будет таким: n / 2 + 1, 1, n / 2 + 2, 2, ..., n, n / 2.

Сергей Михайлович проводит тестирование следующим образом. Он берёт n карточек, пронумерованных от 1 до n, и формирует из них стопку так, чтобы номера карточек в стопке возрастали при их просмотре сверху вниз. Затем он помещает стопку в машину и производит её перетасовку. После этого Сергей Михайлович достает из результирующей стопки k-ю сверху карточку и в зависимости от её номера делает вывод об исправности или неисправности тестируемой машины.

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

Giriş verilənləri

Первая строка ввода содержит целые числа n и k (1kn2 * 10^9, число n - чётное). Во второй строке записано от 1 до 1000 символов 'U' и 'D' без пробелов. Эти символы описывают последовательность преобразований, применяемых машиной для перестановки карточек. Символ 'U' соответствует U-преобразованию, а символ 'D' - D-преобразованию.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
20 7
DUUUDUDUDU
Çıxış verilənləri #1
1
Müəllif Сергей Копелиович
Mənbə Зимняя школа, Харьков 2011, День 5