Найдите время, необходимое для достижения точки N из точки 0 по заданным правилам.

Даны два положительных целых числа X и Y и N точек, расположенных на прямой, задача состоит в том, чтобы найти время, необходимое для достижения точки N из точки 0 в соответствии со следующими правилами:

• Каждая точка имеет один барьер, который закрывается через каждые Y минут и остается закрытым в течение следующих Y минут.
• При достижении точки, если шлагбаум закрыт, то человеку нужно дождаться, пока он откроется.
• Время, необходимое для перемещения из одной точки в другую, равно X минут.
• Изначально все барьеры открыты.

Примеры:

Input: N = 5, X = 4, Y = 3
Output : 28
Explanation:
It takes 4 units of time to reach point number 1 from point number 0 and an additional wait for 2 minutes(till 4th unit of time the barrier was closed on 3 unit time and has to wait for 6th unit time to reopen). Therefore the total time for current hop is 6 unit.

Similarly, a total of 24 units of time to reach point 4 and wait there, and finally 4 units of time to reach point 28. 

Input: N = 7, X = 6, Y = 2
Output: 54

Подход: Данная задача может быть решена на основе следующего наблюдения:

• Если будет найдено время достижения первой точки, т.е. N=1 , или когда будет первый барьер, то найти ответ станет легко.
• Следите за текущим временем при достижении каждой точки. Если по прибытии в город шлагбаум открыт, то двигайтесь к следующей точке, иначе подождите, пока шлагбаум не откроется.
• Чтобы проверить, открыт ли шлагбаум, проверьте, принадлежит ли текущее время периоду времени, когда шлагбаум открыт или закрыт.
• Разделите текущее время на Y , и если при делении времени ток станет четным, барьер открыт, иначе они закрыты. Если текущее время нечетное, подождите, пока текущее время не станет следующим большим кратным Y , а затем двигайтесь вперед.
• Обратите внимание, что если X<Y, то каждый раз, когда он достигает точки, подождите, пока барьер откроется, а затем запустите, и процесс повторится, поэтому ответ будет (N – 1)*Y + X . Точно так же для Y>=X, когда встречается первый барьер, вычислите время, необходимое для достижения этой точки, и используйте его для расчета нашего общего времени для достижения N .

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, currtime как 0 , которая хранит общее требуемое время.
• Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
  1. Инициализируйте проверку переменной как currtime/Y .
  2. Если check%2 равен 0 , то добавьте значение x к переменной currtime .
  3. В противном случае увеличьте значение currtime на (currtime+Y)/Y , умножьте currtime на Y и добавьте значение currtime * repeat + (N – (repeat * i)) * X к переменной currtime и break.
• После выполнения вышеуказанных шагов выведите значение currtime в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)