Простейшие программы с функциями

Задание 1 #9969

Определите наименьшее значение переменной \(k,\) при котором программа, приведенная ниже, выведет ответ 17.

\[\begin{array}{|l|l|l|} \hline \text Python & \text{C++} \\ \hline def \; f(x): \; \; & \#include \; <iostream> \; \; \\ \quad \; \; return \; x*x*x \; \; & using \; namespace \; std; \; \\ def \; g(x): \; \; & int \; f(int \; x) \; \{ \; \; \\ \quad \; \; return \; x*x \; \; &\quad return \; x*x*x; \; \; \\ i=1 \; \; & \} \; \; \\ k=int(input()) \; \; & int \; g(int \; x) \; \{ \; \; \\ while \; f(i) < g(i) * k: \; \; &\quad return \; x*x; \; \; \\ \quad i+=1 \; \; &\} \; \; \\ print (i) \; \; &int \; main()\{ \; \; \\ \; \; &\quad int \; k, \; i=1; \; \; \\ \; \; &\quad cin >> k; \; \; \;\\ \; \; &\quad while(f(i) < g(i) * k) \; \; \\ \; \; &\quad \quad i++; \; \; \;\\ \; \; &\quad cout << i; \; \; \;\\ \; \; &\quad return \; 0; \; \; \\ \; \; &\} \; \; \\ \hline \end{array}\]

Показать решение

То, что программа выведет ответ 17, означает, что последнее значение переменной \(i,\) для которой условие цикла выполняется, равно 16 (когда для переменной \(i\)выполняется условие цикла, ее значение увеличивается на один, т.е. для выведенного после выхода из цикла значения \(i\) условие цикла выполнено не будет — последнее допустимое значение \(i\) после выполнения условия цикла было увеличено на один).

Это означает, что 16 раз было выполнено \(f(i) < g(i) \cdot k.\) Подставим в данное неравенство сами функции \(f(i)\) и \(g(i):\) \(i^3 < i^2 \cdot k.\) Преобразуем: \(i^2 \cdot (i- k) < 0.\) Знаем, что \(i^2 \geq 0,\) значит, при всех значениях \(i,\) кроме 0, неравенство равносильно \(i - k < 0,\) то есть \(k > i. \)

Для \(i\)= 16 полученное неравенство выполнено. Значит, \(k > 16.\)

Для \(i\)= 17 полученное неравенство уже выполнено быть не должно: иначе программа бы вывела ответ 18. Значит, \(k\) \(\geq\) 17.

Ищем наименьшее значение \(k.\) Значит, наш ответ — 17.

Ответ: 17

Задание 2 #9971

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

\[\begin{array}{|l|l|l|} \hline \text Python & \text{C++} \\ \hline def \; f(x): \; \; & \#include \; <iostream> \; \; \\ \quad \; \; return \; x*x \; \; & using \; namespace \; std; \; \\ def \; g(x): \; \; & int \; f(int \; x) \; \{ \; \; \\ \quad \; \; return \; 4000*x+7 \; \; &\quad return \; x*x; \; \; \\ i=1 \; \; & \} \; \; \\ k=int(input()) \; \; & int \; g(int \; x) \; \{ \; \; \\ while \; f(i) <= g(i): \; \; &\quad return \; 4000*x+7; \; \; \\ \quad i*= 2 \; \; &\} \; \; \\ print (i) \; \; &int \; main()\{ \; \; \\ \; \; &\quad int \; k, \; i=1; \; \; \\ \; \; &\quad cin >> k; \; \; \;\\ \; \; &\quad while(f(i) <= g(i)) \; \; \\ \; \; &\quad \quad i*= 2; \; \; \;\\ \; \; &\quad cout << i; \; \; \;\\ \; \; &\quad return \; 0; \; \; \\ \; \; &\} \; \; \\ \hline \end{array}\]

Показать решение

Рассмотрим основную функцию в программе: если выполнено условие \(f(i)\) \(\leq\) \(g(i),\) \(i\)увеличивается вдвое. Как только условие цикла перестает выполняться, то есть \(f(i) > g(i),\) мы выходим из цикла и выводим i. То есть ответом будет минимальное (т.к. иначе из цикла мы бы вышли на предыдущем или одном из предыдущих значениях) значение \(i,\) при котором \(f(i) > g(i),\) то есть \(i^2\) > 4000\(i\)+ 7.

Грустная часть решения состоит в том, что при попытке решить уравнение \(i^2\) - 4000\(i\)- 7 = 0 мы с досадой замечаем, что корни получаются нецелыми, и, скорее всего, тратим много времени на то, чтобы еще раз перепроверить вычисления. Поэтому самые настойчивые пытаются оценить полученные корни (полезно напомнить, что пользоваться калькулятором на экзамене нельзя, но оценить на самом деле не так сложно: 2000\(\cdot\)2000 = 4000000 <\(\sqrt{4000007}\) < 2001\(\cdot\)2001 = 4004001, то есть \(i>\) 2000 + 2000 = 4000, значит, минимальное \(i\)= 4001 — а олимпиадники в душе — найти более изящное решение. И правда, заметим, что при \(i\)= 4000 условие цикла еще выполняется: 4000\(\cdot\)4000 \(\leq\) 4000\(\cdot\)4000 + 7 — а вот уже при \(i\)= 4001 получаем, что 4001\(\cdot\)4001 > 4000\(\cdot\)4001 + 7, т.к. 4001\(\cdot\)4001 = (4000 + 1)\(\cdot\)4001 = 4000\(\cdot\)4001 + 4001, то есть предыдущее неравенство — это 4000\(\cdot\)4001 + 4001 > 4000\(\cdot\)4001 + 7, что, очевидно, правда. Так или иначе, теперь мы знаем, что при \(i\)< 4001 условие цикла еще выполняется, а при \(i\)\(\geq\) 4001 — уже нет.

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

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

Ответ: 4096

Задание 3 #9972

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

\[\begin{array}{|l|l|l|} \hline \text Python & \text{C++} \\ \hline def \; f(x): \; \; & \#include \; <iostream> \; \; \\ \quad \; \; return \; x*x*x \; \; & using \; namespace \; std; \; \\ def \; g(x): \; \; & int \; f(int \; x) \; \{ \; \; \\ \quad \; \; return \; 129*x*x+24 \; \; &\quad return \; x*x*x; \; \; \\ i=1 \; \; & \} \; \; \\ k=int(input()) \; \; & int \; g(int \; x) \; \{ \; \; \\ while \; f(i) <= g(i): \; \; &\quad return \; 129*x*x+24; \; \; \\ \quad i *= 2 \; \; &\} \; \; \\ print (i) \; \; &int \; main()\{ \; \; \\ \; \; &\quad int \; k, \; i=1; \; \; \\ \; \; &\quad cin >> k; \; \; \;\\ \; \; &\quad while(f(i) <= g(i)) \; \; \\ \; \; &\quad \quad i*= 2; \; \; \;\\ \; \; &\quad cout << i; \; \; \;\\ \; \; &\quad return \; 0; \; \; \\ \; \; &\} \; \; \\ \hline \end{array}\]

Показать решение

Рассмотрим основную функцию в программе: если выполнено условие \(f(i) > g(i),\) \(i\) увеличивается вдвое. Как только условие цикла перестает выполняться, то есть \(f(i)\) \(\leq\) \(g(i),\) мы выходим из цикла и выводим \(i.\) То есть ответом будет минимальное (т.к. иначе из цикла мы бы вышли на предыдущем или одном из предыдущих значениях) значение \(i,\) при котором \(f(i)\) \(\leq\) \(g(i),\) то есть \(i^3 \leq 129 i^2+24.\)

Немного попытавшись поподбирать целые корни \(i^3 - 129 \cdot i^2\) - 24 = 0, несложно догадаться, что так задачу не решить. Тогда можно воспользоваться тем, что мы рассматриваем только целые \(i\)и подобрать такое \(i,\) что \(f(i- 1) > g(i- 1),\) а \(f(i)\) \(\leq g(i),\) — такое \(i\) и будет решением, т.к. оно будет первым, при котором мы выйдем из цикла.

Но это не самый легкий и умный путь. Если \(k = 129,\) \(f(129) = 129\cdot 129 \cdot 129,\) а \(g(129) = 129 \cdot 129 \cdot 129 + 24\) — и сравнить эти значения не очень трудно. \(f(129) \leq g(129),\) значит, при \(i\)= 129 условие цикла еще верно. Теперь посмотрим на \(i\)= 130: \(f(130) = 130\cdot130 \cdot 130 = (129+1) \cdot 130 \cdot 130 = 129 \cdot 130 \cdot 130 + 130 \cdot 130,\) а \(g(130) = 129 \cdot 130 \cdot 130+24\) — очевидно, \(f(i) > g(i)\) — условие цикла не выполняется. Значит, условие цикла выполняется только при \(i\)< 130.

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

Итак, в любой момент выполнения цикла \(i\)— это какая-то степень двойки. Найдем последнюю степень двойки, меньшую 130. Это \(2^7\) = 128. На всякий случай покажем, что f(128) \(\leq\) g(128): \(128\cdot 128 \cdot 128 \leq 129 \cdot 128 \cdot 128 + 24,\) то есть \(128 \cdot 128 \cdot 128 \leq (128 + 1) \cdot 128 \cdot 128 + 24 = 128 \cdot 128 \cdot 128 + 128 \cdot 128 + 24.\) Значит, т.к. \(i\)= 128 — степень двойки, в цикле мы достигнем такого значения и в теле цикла умножим \(i\)на 2, получив 256. 256 > 130 и условие цикла уже не будет выполнено: \(256 \cdot 256 \cdot 256 = (129 + 127) \cdot 256 \cdot 256 = 129 \cdot 256 \cdot 256 + 127 \cdot 256 \cdot 256 > 129 \cdot 256 \cdot 256 + 24.\) Значит, при таком \(i\)мы выйдем из цикла — это и будет наш ответ.

Ответ: 256

Задание 4 #9973

Определите количество различных значений \(k,\) при которых программа, приведённая ниже, выводит тот же ответ, что и при входном значении \(k = 27.\) Значение \(k = 27\) также включается в подсчёт различных значений \(k.\)

\[\begin{array}{|l|l|l|} \hline Python & C++ \\ \hline def \; f(n): \; \; & \#include \; <iostream> \; \; \\ \quad \; \; return \; n*n*n \; \; & using \; namespace \; std; \; \\ i= 1 \; \; & int \; f(int \; n) \; \{ \; \; \\ k=int(input()) \; \; &\quad return \; n*n*n; \; \; \\ while \; f(i) < k: \; \; & \} \; \; \\ \quad \quad i += 1\; \; & int \; main()\{ \; \{ \; \; \\ if \; f(i) - k <= k - f(i- 1): \; \; &\quad int \; k, \; i=1; \; \; \\ \quad print(i) \; \; &\quad cin >> k; \; \; \\ else: \; \; & \quad while \; (f(i) < k) \; \; \\ \quad print(i- 1) &\quad \quad i+= 1 \; \; \\ \; \; &\quad if (f(i) - k <= k - f(i- 1)) \; \; \;\\ \; \; &\quad \quad cout << i; \; \; \\ \; \; &\quad else \; \; \;\\ \; \; &\quad \quad cout << i- 1; \; \; \;\\ \; \; &\quad return \; 0; \; \; \\ \; \; &\} \; \; \\ \hline \end{array}\]

Показать решение

Сначала вычислим, что выведет программа при \(k = 27.\) Программа выведет 3: \(f(1) = 1\) \(\leq\) 27, \(f(2) = 8\) \(\leq\) 27, \(f(3) = 27\) \(\leq\) 27.

Посмотрим, как работает программа: она выводит 3, если или if \(f(i) - k\) \(\leq\) \(k\) - \(f(i- 1)\) и \(i\)= 3, или \(if\) \(f(i) - k > k\) - f\((i\)- 1) — и \(i\)- 1 = 3, то есть \(i\)= 4.

Если \(i\)= 3, условие цикла при \(i\)= 3 неверно (иначе мы войдем в цикл и \(i\) станет равно 4): \(f(3) = 27\) \(\geq\) k, то есть \(k \leq\) 27, а при \(i\)= 2 — верно: \(f(2) = 8 < k,\) то есть \(k > 8.\) \(f(i) - k \leq k - f(i- 1)\) имеет вид \(27 - k \leq k - 8,\) то есть \(k \geq 17.5.\) Т.к. значения возможны только целые, получаем, что \(k \in [18; 27]. \)

Если \(i\)= 4, аналогично f(4) \(\geq\) k, \(f(3) < k,\) то есть \(k \leq 64\) и \(k > 27.\) Из \(f(i) - k > k - f(i- 1)\) получаем \(k < 45.5,\) то есть \(k \in (27; 45].\)

В ответ идет объединение случаев, когда \(i\)= 3 и когда \(i\)= 4, то есть \(k \in [18; 27] \cup (27; 45],\) то есть \(k \in [18; 45].\) Всего целых \(k\) здесь \(45 - 18 + 1 = 28. \)

Ответ: 28

Задание 5 #9974

Определите количество различных значений \(k,\) при которых программа, приведённая ниже, выводит тот же ответ, что и при входном значении \(k = 17.\) Значение \(k = 17\) также включается в подсчёт различных значений \(k.\)

\[\begin{array}{|l|l|l|} \hline Python & C++ \\ \hline def \; f(n): \; \; & \#include \; <iostream> \; \; \\ \quad \; \; return \; n*n*n \; \; & using \; namespace \; std; \; \\ i= 12 \; \; & int \; f(int \; n) \; \{ \; \; \\ k=int(input()) \; \; &\quad return \; n*n*n; \; \; \\ while \; i> 0 \; and \; f(i) > k: \; \; & \} \; \; \\ \quad \quad i-= 1\; \; & int \; main()\{ \; \{ \; \; \\ print(i) \; \; &\quad int \; k, \; i=12; \; \; \\ \; \; &\quad cin >> k; \; \; \\ \; \; & \quad while \; (i > 0 \; \&\& \; f(i) > k) \; \; \\ &\quad \quad i -= 1 \; \; \\ \; \; &\quad cout << i; \; \; \;\\ \; \; &\quad return \; 0; \; \; \\ \; \; &\} \; \; \\ \hline \end{array}\]

Показать решение

Программа работает так: \(i\)= 12, в цикле, если \(i>\) 0 и \(f(i) > k\) (т.е. \(i^3\) > k), мы уменьшаем значение \(i\)на единицу.

При \(k = 17\) получим \(i\)= 2. Посмотрим, при каких еще значениях k получим \(i\)= 2.

Чтобы получить \(i\)= 2, при \(i\)= 3 мы должны зайти в цикл, где уменьшим значение \(i\)на единицу, а при \(i\)= 2 условие захода в цикл уже не должно выполняться. Значит, \(f(3) > k,\) а \(f(2) \leq k.\) Получаем \(k < 27, k \leq 8.\)

Таким образом, нам подходят все целые значения \(k \in\) [8; 27) — их 27 - 8 = 19.

Ответ: 19

Задание 6 #12829

Определите количество чисел \(k,\) для которых программа, приведенная ниже, выведет такой же результат, что и для \(k = 14.\) Значение \(k = 14\) включается в подсчет.

\[\begin{array}{|l|l|l|} \hline \text Python & \text{C++} \\ \hline def \; f(x): \; \; & \#include \; <iostream> \; \; \\ \quad \; \; return \; x*x \; \; & using \; namespace \; std; \; \\ i=0 \; \; & int \; f(int \; x) \; \{ \; \; \\ k=int(input()) \; \; &\quad return \; x*x; \; \; \\ while(f(i)<k): \; \; & \} \; \; \\ \quad \; \; i+=1 \; \; & int \; main() \; \{ \; \; \\ print(i) \; \; &\quad int \; k; \; \; \\ \; \; &\quad int \; i = 0; \; \; \\ \; \; &\quad cin>>k; \; \; \\ \; \; &\quad while(f(i)<k) \; \;\\ \; \; &\quad \quad i++; \; \;\\ \; \; &\quad cout<<i; \; \; \\ \; \; &\quad return \; 0; \; \; \\ \; \; &\} \; \; \\ \hline \end{array}\]

Показать решение

Посмотрим, что делает программа. Функция \(f(x)\) считает квадрат переданного ей целого числа. У нас есть переменная \(i,\) изначально равная 0. В цикле мы передаем \(i\) в функцию, т.е. считаем квадрат числа, хранящегося в переменной. Если этот квадрат меньше какого-то введенного числа \(k,\) условие цикла выполнено — и переменную \(i\) мы увеличиваем на единицу, то есть переходим к следующему целому числу. Так мы делаем до тех пор, пока квадрат числа \(i\) не сравняется с числом \(k\) или не превысит его. Что в итоге будет храниться в переменной \(i?\) Последнее число, квадрат которого не превысит или не сравняется с числом \(k,\) причем увеличенное на один: когда мы находим такое последнее число, мы заходим в цикл, т.к. условие выполнено, и добавляем к \(i\) единицу.

Что выведет программа при \(k = 14?\) Теперь мы знаем, как работает программа: ищем последнее число, квадрат которого меньше k = 14, увеличенное на один. Это число 4 — \(3 \cdot 3 = 9\), а уже \(4 \cdot 4 = 16\) — не подходит. Т.к. число увеличено на 1, получаем \(i= 4.\) Теперь вручную прогоним программу и посмотрим, действительно ли это так:

Возьмем \(i= 0: \; 0 \cdot 0 = 0\) — подходит, теперь \(i = 1\).

\(i = 1: \; 1 \cdot 1\) — подходит, теперь \(i = 2\).

\(i = 2: \; 2 \cdot 2\) — подходит, теперь \(i = 3\).

\(i = 3: \; 3 \cdot 3 = 9\) — подходит, теперь \(i = 4\).

\(i = 4: \; 4 \cdot 4 = 16\) — не подходит, выходим из цикла.

Наша задача — найти все числа такие, что 3 — последнее число, квадрат которого меньше \(k.\)

\(k = 9\) не подходит: тогда числа сравняются, а нам нужно строгое неравенство. Значит, и меньшие числа нам не подходят: для них последнее число, квадрат которого меньше \(k,\) будет меньше 3.

\(k = 10\) подходит: \(3 \cdot 3 = 9 < 10\) и \(4 \cdot 4 = 16 > 10.\)

\(k = 11\) подходит: \(3 \cdot 3 = 9 < 11\) и > \(4 \cdot 4 = 16 > 11.\)

\(k = 12\) подходит: \(3 \cdot 3 = 9 < 12\) и > \(4 \cdot 4 = 16 > 12.\)

\(k = 13\) подходит: \(3 \cdot 3 = 9 < 13\) и > \(4 \cdot 4 = 16 > 13.\)

\(k = 14\) подходит: \(3 \cdot 3 = 9 < 14\) и > \(4 \cdot 4 = 16 > 14.\)

\(k = 15\) подходит: \(3 \cdot 3 = 9 < 15\) и > \(4 \cdot 4 = 16 > 15.\)

\(k = 16\) подходит: \(3 \cdot 3 = 9 < 15,\) а для \(i = 4\!: 16 < 16\) не выполнено, значит, \(i = 3\) — последний подходящий квадрат.

\(k = 17\) не подходит: 3 не будет последним квадратом, меньшим \(k,\) им будет 4. Значит, и дальше значения проверять не имеет смысла, они будут возрастать и для всех последний квадрат будет не меньше 4.

Таким образом, нам подошли 7 значений \(k:\) 10, 11, 12, 13, 14, 15, 16. Это и есть наш ответ: 7.

Ответ: 7