|
Кластеры
(Время: 1 сек. Память: 32 Мб Сложность: 28%)
Однажды Евгений так сильно увлёкся компьютерными играми, что потерял связь с реальностью. Его научный руководитель решил помочь завязать с пагубной привычкой тем, что готов заплатить монеты, чтобы любимая экшн-РПГ игра Евгения была пройдена, тем самым даровав освобождение от её оков. Но возникла одна сложность с прокачкой персонажа, так как она реализована престранным образом:
- Во-первых, на каждое приобретение навыка тратится одна монета;
- Во-вторых, навыки располагаются в таком порядке, что образуется замкнутый круг;
- В-третьих, первым приобретается навык с номером 0, после чего разрешается приобретать только те навыки, которые связаны слева или справа с ранее приобретёнными;
- В-четвёртых, навыки делятся на ключевые и обычные.
Известно, что у персонажа Евгения всего имеется n навыков, k из которых являются ключевыми. Вот только научному руководителю неизвестно, как навыки расположены в круге. Единственное, что известно, так это то, что на данный момент у Евгения нет ни одного навыка, ровно как нет ни одной монеты. А вот если бы Евгений смог прокачать все k ключевых навыков, то игра тут же была пройдена.
Помогите научному руководителю Евгения определить количество монет, которое гарантированно хватит, чтобы прокачать все ключевые навыки персонажа при любом расположении навыков.
Входные данные
В единственной строке входного файла INPUT.TXT содержатся два целых числа n и k (1 ≤ n ≤ 1018; 1 ≤ k ≤ n) – общее количество навыков и количество ключевых навыков.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – ответ на поставленную задачу.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 6 3 | 5 |
2 | 4 3 | 4 |
3 | 8 1 | 5 |
Пояснение
Первый пример представлен на рисунке справа. Квадратами отмечены ключевые навыки. Белым текстом обозначены купленные навыки.
Из 6 навыков невыбранным остался только навык под номером 4. Можно доказать, что при других способах расположить навыки не возникнет ситуации, когда потребуется приобрести более чем 5 навыков.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |