Question

Определены две функции:

```python
def f(n):
    return n * n

def g(n):
    return n * 2000 + 3
```

Программа ищет наименьшее значение переменной `i`, начиная с 1 и удваивая его на каждом шаге, при котором условие `f(i) <= g(i)` становится ложным. Какое число выведет программа?

```python
i = 1
while f(i) <= g(i):
    i *= 2
print(i)
```

Accepted Answer

2048

Answer

Идея решения: найти наименьшую степень двойки, при которой $n^2 > 2000n + 3$.

Программа начинает с $i = 1$ и удваивает его, пока выполняется условие $f(i) \leq g(i)$, то есть $i^2 \leq 2000i + 3$. Цикл завершается, когда это неравенство нарушается.

Переформулируем условие выхода из цикла:
$$i^2 > 2000i + 3$$

Для больших $i$ квадратичная функция $i^2$ растёт быстрее линейной $2000i + 3$, поэтому существует пороговое значение, после которого неравенство всегда верно.

Проверим степени двойки:
- $i = 1024$: $f(1024) = 1048576$, $g(1024) = 2048003$. Условие $1048576 \leq 2048003$ верно, цикл продолжается.
- $i = 2048$: $f(2048) = 4194304$, $g(2048) = 4099203$. Условие $4194304 \leq 4099203$ ложно, цикл завершается.

Программа выведет значение $i$, при котором цикл остановился.

Задание №21Алгоритмы и исполнителиЕГЭ по информатике