Наташа и Денис купили упаковку чипсов. вопрос внутри
Наташа и Денис
купили упаковку чипсов. Чтобы разделить их между собой, они придумали игру.
Игроки по очереди берут из упаковки некоторое положительное число чипсов, не
превышающее наперед заданного ограничения. Каждый из игроков добавляет чипсы,
которые взял он, в свою кучу (Наташа - в бинарную, Денис - в фибоначчиеву) .
Игрок, после чьего хода упаковка стала пустой, съедает чипсы из своей кучи, а
его соперник забрасывает свои чипсы заново в упаковку, после чего игра
продолжается с первым ходом соперника. Игра идет до тех пор, пока все чипсы не
съедены. Денис хочет съесть как можно больше чипсов, чтобы Наташа осталась
стройной. Помогите ему в осуществлении этого замысла? Примите к сведению, что
Денис ходит первым, и что оба соперника безгранично умны и не делают никаких
ошибок.
Задание. Напишите
программу, которая читает параметры игры из входного файла, вычисляет
количество чипсов, которое удастся съесть Денису и пишет результат в выходной
файл.
Входные данные. Единственная
строка входного файла содержит числа N и M, разделенные одним пробелом. N -
количество чипсов в упаковке; M - верхний лимит на количество чипсов, которое
можно взять за один ход.
Выходные данные. Выведите одно
число – количество чипсов, которое может съесть Денис.
Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 1 секунда
Пример.
input.txt
output.txt
5 2
3
Ограничения. 1<=M<=N<=100;
все числа целые