Загрузка [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
 

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

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

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

Вы стоите в очереди на кассу магазина. Так как сейчас обеденное время, пока работает только первая касса. Всего в очереди N человек, включая Вас, и Вы — последний.
Каждый человек расплачивается на кассе за 1 минуту и уходит из магазина. Также, каждые M минут с обеда возвращается очередной кассир и открывает следующую кассу. Когда открывается i-я касса часть людей из конца очереди в (i-1)-ю кассу в том же порядке переходит в очередь в i-ю кассу. Причем, если количество людей в (i-1)-й кассе было K, то количество людей, которое перейдет в i-ю кассу равно целой части от K . Например, если в момент открытия 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