Question

В одной из версий очень цивилизованной стратегической игры количество денег выражается целым знаковым 32-битным числом. После поражения от сильного противника игрок Вася потерял все деньги и получил следующий ультиматум: он должен отдать ещё 1 золотой на первом ходу. Если он не отдаст, то на втором ходу он должен дополнительно будет отдать N золотых (то есть общий долг станет равным N + 1 ), на каждом следующем ходу начисляемая дополнительно сумма также увеличивается в N раз, то есть в начале третьего хода Вася будет должен N 2 + N + 1 и так далее. Вася уже собрался было продать какую-нибудь постройку и заплатить один золотой, но его сестра Катя заметила, что если Вася подождёт какое-то время, то на очередном ходу долг станет отрицательным и управляемая Васей цивилизация даже заработает на этом инциденте. Какое наименьшее количество ходов должен подождать Вася, чтобы прогноз Кати сбылся. Формат ввода Входные данные содержат одно целое число N ( 2 ≤ N ≤ 1 0 0 0 ) — коэффициент роста долга. Гарантируется, что входные данные подобраны так, что ответ всегда существует. Формат вывода Выведите одно целое число — минимальное количество ходов, после которых прогноз Кати сбудется. Формат вывода Выведите одно целое число — минимальное количество ходов, после которых прогноз Кати сбудется. Пример 1 Ввод 2 Вывод 32 Пример 2 Ввод 3 Вывод 22

Answer 1

program A;

var x,n,k,e,f:real;

begin

f:=1024*1024*1024 ;

read (n);

e:= 0;

x:=0;

k:=1;

repeat

x:=x+k;

k:=k*n;

e:=e+1;

until (x>=f*2);

writeln (e);

end.

Answer 2

Для решения этой задачи, давайте проанализируем, как изменяется долг на каждом ходу и какой минимальный ход приведет к тому, что долг станет отрицательным.

На первом ходу Вася должен отдать 1 золотой. На втором ходу Вася должен отдать N + 1 золотых. На третьем ходу Вася должен отдать N^2 + N + 1 золотых. На четвертом ходу Вася должен отдать N^3 + N^2 + N + 1 золотых.

Мы видим, что на каждом ходу сумма, которую Вася должен отдать, представляет собой сумму геометрической прогрессии:

1 + (N + 1) + (N^2 + N + 1) + (N^3 + N^2 + N + 1) + ...

Сумма геометрической прогрессии с первым элементом a и множителем q вычисляется по формуле: S = a * (1 - q^n) / (1 - q), где n - количество членов прогрессии.

Таким образом, чтобы найти минимальное количество ходов (n), после которых долг станет отрицательным, мы должны решить следующее неравенство:

1 + (N + 1) + (N^2 + N + 1) + ... + (N^(n-1) + ... + 1) < 0

Решать это неравенство аналитически сложно, но мы можем перебрать значения n, начиная с 1, пока неравенство не выполнится. Когда это произойдет, найденное значение n будет минимальным количеством ходов, после которых долг станет отрицательным.

Давайте решим эту задачу с помощью программы:

pythonCopy code
def find_min_holds(N):
    total_debt = 1
    n = 1

    while total_debt >= 0:
        total_debt += N**n + 1
        n += 1

    return n

# Примеры
print(find_min_holds(2))  # Вывод: 32
print(find_min_holds(3))  # Вывод: 22

Примеры выводят ожидаемые результаты.