АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1081. Волшебный артефакт 256

Ограничение времени: 0.5 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

Группа археологов подошла к артефакту древней цивилизации. Перед артефактом они увидели дорогу из квадратных плит. Шириной дорога была в одну плиту, длина дороги была столь большой, что другого конца её было не видно. Местное племя использовало артефакт для выборов вождя. Претенденты на высокий пост (N человек) выстраивались в очередь к артефакту, по одному человеку на плите на последовательных плитах дороги, начиная от ближайшей к артефакту. Верховный жрец вводил в артефакт число S, посланное богами, и нажимал кнопку начала выборов. После этого артефакт начинал процедуру выбора вождя. Сначала артефакт отсчитывал S-ю непустую плиту, и человек с этой плиты пропадал. Затем артефакт продолжал процедуру отсеивания тем же образом - отсчитывал S-го человека от последнего пропавшего, и уже этот человек пропадал. Если в какой-то момент счёт оказывался на последнем человеке очереди, то счёт продолжался с начала очереди - с ближайшего к артефакту не пропавшего человека. Артефакт заканчивал процедуру отбора, когда на дороге к нему оставался всего один человек. На этого человека снисходила мудрость, и он становился вождём.

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

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

Исходные данные

В единственной строке входного файла записаны через пробел целые числа P (0 <= P < 256) и S (0 < S <= 256). Здесь P - номер плиты, на которую должен встать археолог (плиты нумеруются последовательными числами с нуля), а S - число, которое согласно пророчеству будет введено в артефакт.

Результат

Выведите в выходной файл одно целое число N - минимальный размер очереди к артефакту, который позволит последнему оставшемуся оказаться на месте P. Если пророчество не может быть исполнено (ни при какой длине очереди артефакт с параметром S не выберет место P), выведите 0.

Пример

Исходные данныеРезультат
1 4
3
224 252
39901598

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XV Межвузовская олимпиада 2012 /
1080. A - Факториалы!!! 1081. 1082. C - Слон 1083. D - Изображения 1084. E - Восстановление текста
 
время генерации 0.093 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.