Странный счетчик | Решение проблемы с объяснением от Hackerrank

Постановка задачи

Имеется странный счетчик. В первую секунду он показывает число . Каждую секунду отображаемое число уменьшается на 1, пока не достигнет 1. В следующую секунду таймер сбрасывается на 2 x начальное число предыдущего цикла и продолжает отсчет. На диаграмме ниже показаны значения счетчика для каждого времени t в первых трех циклах:

Найдите и напечатайте значение, показываемое счетчиком в момент времени t.

Формат входных данных
Одно целое число, значение t.

Образец ввода
4

Образец вывода
6

Ссылка на вопрос: https://www.hackerrank.com/challenges/strange-code/problem

Решение (Python3)

def strangeCounter(t):
    # Write your code here
    n = math.log(((t + 3) / 3), 2)
    if math.floor(n) == math.ceil(n):
        return 1
    n = int(math.ceil(n))
    term = 3 * (math.pow(2, n) - 1)
    return int(term - t + 1)

Объяснение

Из приведенной постановки задачи ясно видно, что:

Время, необходимое для завершения 1-го цикла: 3s
Время, необходимое для завершения 2-го цикла: 6 с
Время, необходимое для завершения 3-го цикла: 12 с

И так далее.

Если мы немного понаблюдаем, то обнаружим, что время, затраченное циклами, образует ряд, и этот ряд находится в G.P. (геометрической прогрессии) с общим соотношением 2.

Ясно, что время, в которое заканчивается любой цикл, представляет собой кумулятивную сумму всех времен, затраченных на завершение цикла до этого цикла. Например.

Время окончания 1-го цикла: 3
Время окончания цикла: Время, затраченное на завершение 1-го цикла + Время, затраченное на завершение 2-го цикла = 3 + 6 = 9

И так далее.

Если эта серия в G.P., то кумулятивная сумма, т.е. время окончания любого цикла, может быть рассчитана по следующей формуле:

S = a(rⁿ-1)/(r-1),

где S – сумма серии, a – первый член серии, r – общий коэффициент и n – количество членов в серии.

Здесь, в задаче, нам дана сумма ряда (т.е. t в данном случае), мы знаем первый член и общее отношение (т.е. 3 и 2). Таким образом, нам нужно вычислить n. Используя приведенную выше формулу, мы можем вывести:

n=log₂((S+3)/3).

Если в качестве n мы получим целое число, то данное t будет временем окончания цикла. Если же мы получаем плавающее число, то t – это время между временем окончания предыдущего и следующего цикла. В этом случае, используя значение потолка t и формулу Суммы Г.П., мы можем вычислить время окончания текущего цикла, скажем сроки. А разница между сроками и t и есть наш ответ.