print1918. Очередь в кассу

printОчередь в кассу

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Вы стоите в очереди на кассу магазина. Так как сейчас обеденное время, пока работает только первая касса. Всего в очереди `N` человек, включая Вас, и Вы — последний.
Каждый человек расплачивается на кассе за 1 минуту и уходит из магазина. Также, каждые `M` минут с обеда возвращается очередной кассир и открывает следующую кассу. Когда открывается `i`-я касса часть людей из конца очереди в `(i-1)`-ю кассу в том же порядке переходит в очередь в `i`-ю кассу. Причем, если количество людей в `(i-1)`-й кассе было `K`, то количество людей, которое перейдет в `i`-ю кассу равно целой части от `K\ /\ 2`. Например, если в момент открытия 4-й кассы в 3-й было 5 человек, то в 4-ю перейдет 2 человека, если было 6 человек — перейдет 3 человека. Переход из одной очереди в другую происходит мгновенно.
Определите, через сколько минут Вы сможете уйти из магазина.
Входной файл содержит два целых числа `N` и `M`, разделенных пробелом (`1\ ≤\ N\ ≤\ 10^9`, `1\ ≤\ M\ ≤\ 10^9`).
Выведите одно целое число — через сколько минут Вы уйдете из магазина.

Пример ввода 1

5 10

Пример вывода 1

5

Пример ввода 2

5 2

Пример вывода 2

3

Пример ввода 3

15 3

Пример вывода 3

7
3-й тест:
  • 1 касса – 15 человек

Через 3 минуты:
  • 1 касса – 6 человек
  • 2 касса – 6 человек

Через 6 минут:
  • 1 касса – 3 человека
  • 2 касса – 2 человека
  • 3 касса – 1 человек (Вы)
Источник: 3-й этап Республиканской олимпиады по информатике 2013, Казахстан
loading