Задача к ЕГЭ по информатике на тему «простейшие программы с функциями» №2

Определите, что выведет программа.

|---------------------|-------------------------| |Python |C++ | |deff-(x-) :-----------|#include--<-iostream-->—| | | | | returnx ∗ x |usingnamespacestd; | |defg(x ) : |intf (intx ){ | | return4000 ∗ x + 7 | returnx ∗ x; | |i = 1 |} | |k = int(input ()) |intg(intx){ | | | | |whilef(i) <= g(i) : | return4000 ∗ x + 7; | | i∗ = 2 |} | |print(i) |intmain (){ | | | intk, i = 1; | | | cin > > k; | | | | | | while (f(i) <= g (i)) | | | i∗ = 2; | | | cout < < i; | | | return0; | | | | -----------------------}-------------------------

Рассмотрим основную функцию в программе: если выполнено условие $f(i)$ $≤$ $g(i),$ $i$ увеличивается вдвое. Как только условие цикла перестает выполняться, то есть $f(i) > g(i), » class=»math» width=»auto»> мы выходим из цикла и выводим i. То есть ответом будет минимальное (т.к. иначе из цикла мы бы вышли на предыдущем или одном из предыдущих значениях) значение <img decoding=$ при котором $f (i) > g(i), » class=»math» width=»auto»> то есть <img decoding=$ > 4000 $i$ + 7.

Грустная часть решения состоит в том, что при попытке решить уравнение $i2$ — 4000 $i$ — 7 = 0 мы с досадой замечаем, что корни получаются нецелыми, и, скорее всего, тратим много времени на то, чтобы еще раз перепроверить вычисления. Поэтому самые настойчивые пытаются оценить полученные корни (полезно напомнить, что пользоваться калькулятором на экзамене нельзя, но оценить на самом деле не так сложно: 2000 $⋅$ 2000 = 4000000 < $√ -------- 4000007$ < 2001 $⋅$ 2001 = 4004001, то есть $i > » class=»math» width=»auto»> 2000 + 2000 = 4000, значит, минимальное <img decoding=$ = 4001 — а олимпиадники в душе — найти более изящное решение. И правда, заметим, что при $i$ = 4000 условие цикла еще выполняется: 4000 $⋅$ 4000 $≤$ 4000 $⋅$ 4000 + 7 — а вот уже при $i$ = 4001 получаем, что 4001 $⋅$ 4001 > 4000 $⋅$ 4001 + 7, т.к. 4001 $⋅$ 4001 = (4000 + 1) $⋅$ 4001 = 4000 $⋅$ 4001 + 4001, то есть предыдущее неравенство — это 4000 $⋅$ 4001 + 4001 > 4000 $⋅$ 4001 + 7, что, очевидно, правда. Так или иначе, теперь мы знаем, что при $i$ < 4001 условие цикла еще выполняется, а при $i$ $≥$ 4001 — уже нет.

Теперь посмотрим, что если условие цикла выполняется, то $i$ умножается на 2. То есть ответом будет какая-то степень двойки, так как мы начали с $i$ = 1 и в цикле все время умножали $i$ на 2.

Итак, в любой момент выполнения цикла $i$ — это какая-то степень двойки. Найдем последнюю степень двойки, меньшую 4001. Это $211$ = 2048. На всякий случай покажем, что f(2048) $≤$ g(2048): 2048 $⋅$ 2048 $≤$ 4000 $⋅$ 2048 + 7, то есть 2048 $⋅$ 2048 $≤$ (2048 + 1952) $⋅$ 2048 + 7 = 2048 $⋅$ 2048 + 1952 $⋅$ 2048 + 7. Значит, т.к. $i$ = 2048 — степень двойки, в цикле мы достигнем такого значения и в теле цикла умножим $i$ на 2, получив 4096. 4096 > 4001 и условие цикла уже не будет выполнено: (4000 + 96) $⋅$ 4096 = 4000 $⋅$ 4096 + 96 $⋅$ 4096 > 4000 $⋅$ 4096 + 7. Значит, при таком $i$ мы выйдем из цикла — это и будет наш ответ.

Ответ: 4096