Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Кластеры

(Время: 1 сек. Память: 32 Мб Сложность: 28%)

Однажды Евгений так сильно увлёкся компьютерными играми, что потерял связь с реальностью. Его научный руководитель решил помочь завязать с пагубной привычкой тем, что готов заплатить монеты, чтобы любимая экшн-РПГ игра Евгения была пройдена, тем самым даровав освобождение от её оков. Но возникла одна сложность с прокачкой персонажа, так как она реализована престранным образом:

  • Во-первых, на каждое приобретение навыка тратится одна монета;
  • Во-вторых, навыки располагаются в таком порядке, что образуется замкнутый круг;
  • В-третьих, первым приобретается навык с номером 0, после чего разрешается приобретать только те навыки, которые связаны слева или справа с ранее приобретёнными;
  • В-четвёртых, навыки делятся на ключевые и обычные.

Известно, что у персонажа Евгения всего имеется n навыков, k из которых являются ключевыми. Вот только научному руководителю неизвестно, как навыки расположены в круге. Единственное, что известно, так это то, что на данный момент у Евгения нет ни одного навыка, ровно как нет ни одной монеты. А вот если бы Евгений смог прокачать все k ключевых навыков, то игра тут же была пройдена.

Помогите научному руководителю Евгения определить количество монет, которое гарантированно хватит, чтобы прокачать все ключевые навыки персонажа при любом расположении навыков.

Входные данные

В единственной строке входного файла INPUT.TXT содержатся два целых числа n и k (1 ≤ n ≤ 1018; 1 ≤ k ≤ n) – общее количество навыков и количество ключевых навыков.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – ответ на поставленную задачу.

Примеры

INPUT.TXTOUTPUT.TXT
16 35
24 34
38 15

Пояснение

Первый пример представлен на рисунке справа. Квадратами отмечены ключевые навыки. Белым текстом обозначены купленные навыки.

Из 6 навыков невыбранным остался только навык под номером 4. Можно доказать, что при других способах расположить навыки не возникнет ситуации, когда потребуется приобрести более чем 5 навыков.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 A. Забытая цифра
 B. Число + олсич
 C. Соревнование кузнечиков
 D. Два квадрата
 E. Горы мусора
 F. Урок физкультуры
 G. Игра в монетку
 H. Снеговик
 I. Сплетня
 J. Кластеры

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru