Задание 12. Здания 19 – 21
91. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a, b) (где a, b – целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Чертёжнику был дан для исполнения следующий алгоритм:
Сместиться на (1, -3)
Сместиться на (-1, -2)
Сместиться на (-25, -33)
После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «Повтори … раз»?
92. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
Дана программа для исполнителя Редактор:
ПОКА нашлось (333) ИЛИ нашлось (555)
ЕСЛИ нашлось (555)
ТО заменить (555, 3)
ИНАЧЕ заменить (333, 5)
Какая строка получится в результате применения приведённой выше программы к строке, состоящей из 184 идущих подряд цифр 5? В ответе запишите полученную строку.
93. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
Дана программа для исполнителя Редактор:
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (4555)
ЕСЛИ нашлось (25) ТО заменить (25, 3) КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (355) ТО заменить (355, 4) КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (4555) ТО заменить (4555, 2) КОНЕЦ ЕСЛИ
Какая строка получится в результате применения приведённой выше программы к строке, состоящей из цифры 3 и следующих за ней 57 цифр 5? В ответе запишите полученную строку.
94. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
Дана программа для исполнителя Редактор:
ПОКА нашлось (63) ИЛИ нашлось (664) ИЛИ нашлось (6665)
ЕСЛИ нашлось (63) ТО заменить (63, 4)
ЕСЛИ нашлось (664) ТО заменить (664, 5)
ЕСЛИ нашлось (6665) ТО заменить (6665, 3) КОНЕЦ ЕСЛИ
Какая строка получится в результате применения приведённой выше программы к строке, в которой первая и последняя цифры – 4, а между ними стоит 125 цифр 6? В ответе запишите полученную строку.
95. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
Дана программа для исполнителя Редактор:
ПОКА нашлось (555) ИЛИ нашлось (333)
ЕСЛИ нашлось (333)
ТО заменить (333, 5)
ИНАЧЕ заменить (555, 3)
Дана строка, состоящая из 500 цифр 5. Сколько пятёрок было удалено за время обработки строки по этой программе?
96. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
Если при выполнении команды заменить цепочка, которую нужно заменить, не найдена, то строка не изменяется. Дана программа для исполнителя Редактор:
ПОКА нашлось (56) ИЛИ нашлось (1111)
заменить (1111, 1)
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 102 строк 561 (561561561…561)?
97. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
К исходной строке, содержащей не более 50 шестёрок и не содержащей других символов, применили приведённую ниже программу.
ПОКА нашлось (66)
В результате получилась строка 21. Какое наибольшее количество шестёрок могло быть в исходной строке?
98. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для Редактора:
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)
ТО заменить (>1, 22>)
ТО заменить (>2, 2>)
ТО заменить (>3, 1>)
На вход приведённой ниже программе поступает строка, начинающаяся с символа «>», а затем содержащая 11 цифр 1, 12 цифр 2 и 30 цифр 3, расположенных в произвольном порядке.
Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы. Так, например, если результат работы программы представлял бы собой строку, состоящую из 50 цифр 4, то верным ответом было бы число 200.
99. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для Редактора:
Исходная строка содержит 12 единиц и 4 двойки, других цифр нет, точный порядок расположения цифр неизвестен. Какую наибольшую сумму цифр может иметь строка, которая получится после
100. Исполнитель Редактор получает на вход строку цифр и преобразовывает её.
Определите максимально возможное количество цифр 1, которое может получиться в результате применения представленного ниже алгоритма к строке, состоящей из 30 цифр 2, 30 цифр 3 и 30 цифр 1, идущих в произвольном порядке.
101. На рисунке приведена схема дорог, соединяющих пункты А, Б, В, Г, Д, Е, Ж, З, И, К, Л. Передвигаться можно только по указанным дорогом в указанном направлении. Определите длину самого длинного маршрута из А в Л, не проходящего через пункт Г? Длиной маршрута считать количество пройденных дорог.
102. На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Е и при этом не проходящих через пункт Л?
103. На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно передвигаться только в направлении, указанном стрелкой, для каждой дороги указано время проезда в минутах. За какое минимальное время можно проехать из пункта А в пункт Л? В ответе укажите только число – время в минутах, указывать единицы измерения не нужно
104. Решите уравнение: 101x + 1310 = 101х+1
105. В системе счисления с основанием N запись числа 8710 оканчивается на 2 и содержит не менее трёх цифр. Чему равно число N?
106. Значение арифметического выражения: 64 150 + 4 300 – 32 записали в системе счисления с основанием 8. Сколько цифр «7» в этой записи?
107. Значение арифметического выражения 3 ⋅ 256 320 — 2 ⋅ 64 290 + 4 250 – 1023 записали в системе счисления с основанием 4. Найдите количество ненулевых разрядов в этой записи.
108. Число, являющееся результатом выражения 5 20 + 5 10 – 5 13 – 5 3 , записали в системе счисления с основанием 5. Чему равна сумма цифр в получившейся записи? В ответе укажите одно десятичное число – сумма разрядов пятеричного числа.
109. При каком наименьшем натуральном значении переменной x в выражении 81 20 – 9 x + 50 сумма цифр в девятеричной записи числа равна 138?
110. Сколько существует целых положительных чисел, которые соответствуют следующим условиям:
— в пятеричной записи содержится не более 4 цифр,
— в двоичной записи не менее 5 цифр,
— последняя цифра в шестнадцатеричной системе счисления – C?
111. Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?
112. Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Для какого наименьшего неотрицательного целого числа А формула
тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?
113. На числовой прямой даны два отрезка: Р = [3, 38] и Q = [21, 57]. Какова наибольшая возможная длина интервала A, что логическое выражение ((х ∈ Q) → (х ∈ Р)) → (х ∈ A) тождественно истинно, то есть принимает значение 1 при любом значении переменной х.
114. На числовой прямой даны два отрезка: Р = [22, 72] и Q = [42, 102]. Какова наименьшая возможная длина интервала A, что логическое выражение ((х ∈ А) ∧ (х ∈ Р)) ∨ (х ∈ Q) тождественно истинно, то есть принимает значение 1 при любом значении переменной х.
115. На числовой прямой даны два отрезка: P = [17, 54] и Q = [37, 83]. Какова наименьшая возможная длина интервала A, что формула (x ∈ P) → (((x ∈ Q) ∧ (x ∈ A)) → (x ∈ P))
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
116. Элементами множеств А, P, Q являются натуральные числа, причём P = <2, 4, 6, 8, 10, 12, 14, 16, 18, 20>, Q = <3, 6, 9, 12, 15, 18, 21, 24, 27, 30>.
Известно, что выражение ((x ∈ P) → (x ∈ A)) ∨ ((x ∈ A) → (x ∈ Q)) истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.
117. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула
ДЕЛ(120, A) ∧ (ДЕЛ(x, А) → (ДЕЛ(x, 18) → ДЕЛ(x, 24)))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
118. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула
ДЕЛ(A, 45) ∧ (ДЕЛ(750, x) → (ДЕЛ(A, x) → ДЕЛ(120, x)))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
119. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
120. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Сколько существует натуральных значений A на отрезке [1;1000], при которых формула ДЕЛ(A, 9) ∧ (ДЕЛ(280, x) → (ДЕЛ(A, x) → ДЕЛ(730, x))) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
121. Для какого наименьшего целого неотрицательного числа А выражение
тождественно истинно, т. е. принимает значение 1 при любых целых неотрицательных x и y?
122. Для какого наименьшего целого значения параметра А существует выражение
(x > 39) ∨ (y > 26) ∨ (2x + 4y < A) является тождественно истинным, то есть принимает значение 1 при любых целых положительных значениях переменных х и у.
123. Укажите наибольшее целое значение А, при котором выражение (2x + 3y = 101) ∧ (x + y < A) ложно для любых целых положительных значений x и y.
124. Для какого наибольшего целого числа А формула ((x ≤ 9) →(x ⋅ x ≤ A)) ⋀ ((y ⋅ y ≤ A) → (y ≤ 9)) тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?
125. На числовой прямой задан отрезок A. Известно, что формула
((x ∈ A) → (x 2 ≤ 100)) ∧ ((x 2 ≤ 64) → (x ∈ A)) тождественно истинна при любом вещественном x. Какую наибольшую длину может иметь отрезок A?
126. Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 1+2n при n < 5
F(n) = 2·(n + 1)·F(n–2), если n ≥ 5 и делится на 3,
F(n) = 2·n + 1 + F(n–1) + 2·F(n–2), если n ≥ 5 и не делится на 3.
Чему равно значение функции F(15)?
127. Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:
F(n) = 2·F(n–1) + G(n–1) – 2, если n > 1
G(n) = F(n–1) +2·G(n–1), если n > 1
Чему равно значение F(14) + G(14)?
128. Определите, сколько символов * выведет эта процедура при вызове F(35):
129. Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 5000000. Запишите в ответе найденное значение n
130. Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = n · n + 4 · n + 3, при n > 25
F(n) = F(n+1) + 2 · F(n+4), при n £ 25, кратных 3
F(n) = F(n+2) + 3 · F(n+5), при n £ 25, не кратных 3
Определите количество натуральных значений n из отрезка [1; 1000], для которых сумма цифр значения F(n) равна 24.
131. Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n + F(n / 5 + 1), когда n > 5 и делится на 5,
F(n) = n + F(n + 6) , когда n > 5 и не делится на 5.
Назовите минимальное значение n, для которого F(n) > 1000
132. Чему равно значение функции f(30):
Квадратные скобки в записи [x] применяются для обозначения целой части числа x
133. Рассматривается множество целых чисел, принадлежащих числовому отрезку [22500; 70813], которые оканчиваются на 3 и при этом не делятся ни на 7, ни на 13. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число.
134. Рассматривается множество целых чисел, принадлежащих числовому отрезку [2807; 8558], которые удовлетворяют следующим условиям:
− запись в двоичной системе заканчивается на 11;
− запись в девятеричной системе заканчивается на 5.
Найдите максимальное из таких чисел и их сумму. Гарантируется, что искомая сумма не превосходит 10 7 .
135. Рассматривается множество целых чисел, принадлежащих числовому отрезку [3905; 7998], которые удовлетворяют следующим условиям:
− цифра в разряде десятков отлична от 0 и 5;
− цифра в разряде сотен принадлежит отрезку [2; 6].
Найдите количество таких чисел и минимальное из них.
136. Рассматривается множество целых чисел, принадлежащих числовому отрезку [8800; 55535], которые удовлетворяют следующим условиям:
− произведение разрядов больше 35;
− один из разрядов равен 7.
Найдите наибольшее из таких чисел и их количество.
137. Рассматривается множество целых чисел, принадлежащих числовому отрезку [54123; 75321], которые имеют ровно 5 делителей в диапазоне [10;20].Найдите количество таких чисел и максимальное из них.
138. Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную.
139. Квадрат разлинован на N×N клеток (2 < N < 21). В каждой клетке записано целое положительное число – количество монет. Исполнитель Сборщик имеет две команды ВПРАВО и ВВЕРХ, которые, соответственно, перемещают его на одну клетку вправо или на одну клетку вверх. Проходя через клетку, Сборщик собирает все монеты, лежащие на ней. На поле существуют стены, обозначены жирной линией, через которые Сборщик проходить не может. Исполнитель начинает движение в левой нижней клетке и заканчивает в правой верхней. Какое максимальное и минимальное количество монет может собрать Сборщик, пройдя от начальной клетки до конечной? В ответе укажите сначала максимальный, затем минимальный результат, который может быть получен исполнителем.
140. Квадрат разлинован на NxN клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата записано натуральное число, не превышающее 100. Перемещаясь по клеткам квадрата, Робот вычисляет сумму следующим образом. Начальное значение суммы — значение той клетки, из которой Робот начинает движение. При посещении клетки, Робот прибавляет к сумме удвоенное значение, записанное в клетке, если он попал в эту клетку из соседней сверху клетки, и прибавляет к сумме утроенное значение, записанное в клетке, если он попал в эту клетку из соседней слева клетки. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала минимальную сумму, затем максимальную.
Здания 19 – 21
141. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в любую кучу один камень или увеличить количество камней в любой куче в четыре раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 133. В начальный момент в первой куче было 7 камней, а во второй – S камней, 1 ≤ S ≤ 125.
Назовите минимальное значение S, при котором Петя может выиграть своим первым ходом.
142. Для игры из задания 141 определите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
143. Для игры из задания 141 определите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ 32, 20 31, 30
144. Два игрока, Петя и Ваня, играют в следующую игру. Игроки передвигают фишку по целочисленным координатам числовой оси. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может сдвинуть фишку, увеличив её координату либо на 3, либо в два раза. Например, если фишка находится в точке с координатой 5, за один ход можно передвинуть фишку в точку с координатой 8 или 10. Игра завершается в тот момент, когда координата точки, в которой находится фишка, станет больше или равна 100. Победителем считается игрок, сделавший последний ход, т.е. первый сдвинувший фишку в точку, координата которой не менее 100.
В начальный момент координата точки с фишкой была S; 1 ≤ S ≤ 91.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от дальнейшей игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода
Пети. Укажите минимальное значение S, когда такая ситуация возможна.
145. Для игры, описанной в задании 144, найдите такие значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Из всех найденных значений запишите в ответе минимальное и максимальное в порядке возрастания.
146. Для игры, описанной в задании 144, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ 25, 24 46, 41
147. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в любую кучу один камень или добавить добавить в любую кучу столько камней, сколько их в данный момент в другой куче. Игра завершается в тот момент, когда общее количество камней в двух кучах становится не менее 79. В начальный момент в первой куче было 9 камней, а во второй – S камней, 1 ≤ S ≤ 69.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно.
148. Для игры, описанной в задании 147 найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
149. Для игры, описанной в задании 147 найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ 21, 20 34, 33
150. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в кучу один камень;
б) увеличить количество камней в куче в два раза;
в) увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 43. Если при этом в куче оказалось не более 72 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник (при этом победа учитывается как ход противника). В начальный момент в куче было S камней, 1 ≤ S ≤ 42.
Найдите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
151. Для игры, описанной в задании 150, определите сколько существует значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
152. Для игры, описанной в задании 150, найдите минимальное и максимальное значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.
Ответ 14, 3, 12 39
Задание 22
153. Ниже на четырёх языках программирования записан алгоритм. Получив на вход число а, этот алгоритм печатает два числа L и M. Укажите наибольшее число a, при вводе которого алгоритм печатает сначала 11, а потом 14.
154. Найдите минимальное число x > 100, при вводе которого приведенный алгоритм напечатает на экране число 30.
155. Ниже на четырёх языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, не содержащее нулей, при вводе которого алгоритм печатает сначала 14, а потом 3.
156. Ниже записана программа. Получив на вход число x, эта программа печатает два числа число L и M. Сколько существует натуральных чисел x, при вводе которых алгоритм печатает 6 и 0.
Задание 23
157. Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
2. Умножить на 3
Первая команда увеличивает число на экране на 2, вторая умножает его на 3. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 63 и при этом траектория вычислений содержит число 25 и не содержит число 6?
158. Исполнитель U18 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
3. Разделить нацело на 3
При выполнении команды 3 выполняется деление нацело (остаток отбрасывается). Программа для исполнителя U18 – это последовательность команд. Сколько существует таких программ, которые исходное число 22 преобразуют в число 2?
159. Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
2. Умножить на 2 и отнять 1
Первая команда увеличивает число на экране на 3, вторая умножает его на 2 и вычитает из результата 1.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 30, и при этом траектория вычислений содержит число 21 и не содержит 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 10, 19, 38.
160. Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:
2. сделай нечётное
Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ – это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 27, причём траектория вычислений не содержит число 26? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.
161. Текстовый файл состоит не более чем из 106 символов X, Y и Z.
Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.
Для выполнения этого задания следует написать программу.
162. Текстовый файл состоит не более чем из 106 символов F, A, I, L. Определите максимальное количество подряд идущих одинаковых букв.
163. Текстовый файл состоит не более чем из 106 символов J, O, B, S. Сколько раз встречаются комбинации «BOSS» при этом до и после этого слова нет символа «J». Например, комбинации «JBOSS», «BOSSJ» и «JBOSSJ» не должны учитываться. Для выполнения этого задания следует написать программу.
164. Текстовый файл состоит не более чем из 106 символов и содержит только заглавные латинские буквы и десятичные цифры. Определите максимальное нечётное число, записанное в этом файле.
165. Текстовый файл состоит не более чем из 106 символов и содержит только заглавные латинские буквы и десятичные цифры. Под словом подразумевается последовательность букв, ограниченная цифрами. Определите количество четырёхбуквенных слов. Словом считается любая произвольная последовательность букв.
166. Текстовый файл состоит не более чем из 1200000 символов, которые являются прописными буквами латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых нет подстроки XYZ. Для выполнения этого задания следует написать программу.
167. Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Текст разбит на строки различной длины. Необходимо найти строку, содержащую наибольшее количество букв Q (если таких строк несколько, надо взять ту, которая в файле встретилась позже). Определите, какая буква встречается в этой строке реже всего (но присутствует!). Если таких букв несколько, надо взять ту, которая стоит раньше в алфавите. Запишите в ответе эту букву, а затем – сколько раз она встречается во всем файле.
Пример. Исходный файл:
В этом примере в первой и второй строках по две букву Q, в третьей – одна. Берём вторую строку, т.к. она стоит в файле позже. В этой строке реже других встречаются буквы V и B (по одному разу), выбираем букву B, т. к. она раньше стоит в алфавите. В ответе для этого примера надо записать B4, так как во всех строках файла буква B встречается 4 раза.
168. В файле 24.txt записана последовательность символов. Укажите длину самой длинной последовательности, состоящей из одинаковых символов.
169. В файле 24.txt записана последовательность символов. На какой позиции от начала строки встречается 123 буква «f»? Нумерация символов в строке ведется с единицы.
170. Напишите программу, которая ищет среди целых чисел, превышающих 136179, первые четыре числа, удовлетворяющих условию: сумма всех различных делителей числа, отличных от 1 и самого числа, при делении на 385 даёт остаток 91.
В ответе запишите эти четыре пары чисел в порядке возрастания первого числа в паре: число и сумму его различных делителей (исключая 1 и само число).
171. Пусть S — сумма натуральных чётных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение S равным нулю.
Напишите программу, которая перебирает целые числа из отрезка [1204300; 1204380] в порядке возрастания и ищет среди них такие, для которых значение S не равно нулю и кратно 10. Программа должна найти и вывести такие числа и соответствующие им значения S.
Формат вывода: для каждого из найденных чисел в отдельной строке сначала выводится само число, затем значение S. Строки выводятся в порядке возрастания найденных чисел.
172. Рассмотрим произвольное натуральное число, представим его всеми возможными способами в виде произведения двух натуральных чисел и найдём для каждого такого произведения разность сомножителей. Например, для числа 18 получим: 18 = 18*1 = 9*2 = 6*3, множество разностей содержит числа 17, 7 и 3. Подходящей будем называть пару сомножителей, разность между которыми не превышает 120. Найдите все натуральные числа, принадлежащие отрезку [2000000; 3000000], у которых есть не менее трёх подходящих пар сомножителей. В ответе перечислите найденные числа в порядке возрастания, справа от каждого запишите наибольший из всех сомножителей, образующих подходящие пары.
173. Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Найдите все натуральные числа, принадлежащие отрезку [106732567; 152673836] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе само число и его наибольший нетривиальный делитель. Найденные числа расположите в порядке возрастания.
Например, для числа 2018 имеем следующие делители 2 и 1009. Поэтому результатом (не принимая во внимание количества делителей) будет пара чисел 2018 1009
174. Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. Администратор отбирает файлы в архив таким образом, что в него будут сохранены файлы наибольшего возможного количества пользователей.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимально возможный суммарный объём файлов в архиве, а также количество файлов, которые ни при каких условиях не могут попасть в архив.
В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала максимально возможный суммарный объём файлов в архиве, затем количество файлов, которые ни при каких условиях не могут попасть в архив, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример организации исходных данных во входном файле:
При таких исходных данных в архив можно записать файлы максимум 3 пользователей. При этом максимально возможная сумма будет из файлов размером 10, 34, 47. А файлы размером 65, 66, 90 не смогут попасть в архив ни при каких условиях.
Системы счисления, сложение, вычитание.
В задачах ЕГЭ по информатике иногда нужно выполнять арифметические действия над очень длинными числами в различных системах счисления. В частности, это требуется в задаче 14.
Вот типичная задача из ЕГЭ прошлых лет (задание 14 № 36027 с сайта «Решу ЕГЭ»):
Значение арифметического выражения
7 · 512 120 − 6 · 64 100 + 8 210 - 255
записали в системе счисления с основанием 8. Сколько цифр 0 содержится в этой записи?
В общем-то не так сложно решить эту задачу на бумаге. Однако в языке Питон есть две приятные особенности, которые позволяют решать подобные задачи программно. Это, во-первых, возможность работы с очень большими целыми числами, а во-вторых, операция возведения в степень (обозначается двумя звездочками — **).
Вспомним, как можно получать цифры некоторого целого числа в системе счисления с основанием b. Чтобы получить последнюю цифру числа, надо найти остаток от деления этого числа на b. А если разделить нацело число на b, то результатом будет исходное число без последней цифры. (Полагаю, читателю известно, что в Питоне операция нахождения остатка от деления обозначается знаком процента, а операция целочисленного деления — двумя слэшами.)
Вот универсальная программа для решения задач, подобных приведенной выше:
n = 7*512**120 — 6*64**100 + 8**210 — 255
base=8
d=[0]*base
while n>0:
d[n%base] += 1
n //= base
for i in range(base): print(i, d[i])
Подробно прокомментируем данную программу.
В первой строке вычисляется значение выражения из условия задачи и результат присваивается переменной n.
Во второй строке задается основание системы счисления.
В третьей строке создается масссив d из нулей. Размер массива — это основание системы счисления. В этом массиве будет храниться количество цифр записи числа в требуемой системе счисления.
Далее организуется цикл, который выполняется, пока число n не станет равным нулю (т.е. пока мы не получим все цифры, которые входят в его запись). Число n%base — это последняя цифра числа n в требуемой системе счисления. Соответствующий элемент массива d увеличивается на единицу, а само число делится нацело на основание системы счисления — в результате получается число без последней цифры. (Операторы += и //= работают следующим образом: берется значение переменной, которая записана слева от оператора, выполняется операция сложения или целочисленного деления на значение выражения в правой части оператора, а результат присваивается переменной в левой части.)
Когда цикл закончится, то элемент массива d[0] будет содержать количество нулей, d[1] — количество единиц и т.д. В последней строке производится печать этого массива. (К слову, если в условном операторе или операторе цикла присутствует лишь один оператор, то его можно писать не в отдельной строке, а после двоеточия.)
Программа выдает следующий результат:
Это означает, что в данном числе, записанном в восьмеричной системе счисления, содержится 151 ноль, две единицы, одна четверка и 207 семерок, а двоек, троек, пятерок и шестерок нет. Следовательно, ответ к задаче — 151.
Переменной n нужно присвоить выражение, которое вычисляет нужное число, а переменной base — основание системы счисления. Программа напечатает, сколько раз в записи этого числа встречается та или иная цифра. Чтобы решить практически любую задачу из соответствующего раздела сайта «Решу ЕГЭ», достаточно изменить в этой программе две первые строки: написать новое выражение для числа и изменить основание системы счисления.
В последнем году задачи на тему сложения и вычитания в различных системах счисления стали более разнообразными. Так, на сайте К.Полякова приводится следующая задача:
Для решения данной задачи приведенную выше программу необходимо переработать. Можно, например, получить и напечатать само число в системе счисления с основанием 4:
n = (64**25 + 4**10) — (16**20 + 32**3)
base=4
num = »
while n>0:
num = str(n%base) + num
n //= base
print(num)
Результат выполнения следующий:
Как видим, первый раз двойка появляется на восьмом месте справа. (Ответ к данной задаче — 7. Очевидно, автор считает, что нумерация разрядов справа налево начинается с нуля. Хорошо было бы явно указать это в условии задачи.)
Данная программа будет работать только для систем счисления с основанием, не превышающим 10. Если нужно большее основание (например, 16), то программу придется доработать, чтобы она корректно выводила шестнадцатеричные цифры A, B и т.д.
Можно также проверять по очереди все цифры числа (алгоритм получает их именно справа налево) и, как только встретится двойка, напечатать номер разряда. После этого можно прервать цикл.
Вот программа, работающая по такому методу:
n = (64**25 + 4**10) — (16**20 + 32**3)
base=4
k=0
while n>0:
if n%base == 2:
print(k)
break
k += 1
n //= base
В программе учтено, что нумерация разрядов (она содержится в переменной k) начинается с нуля. Поэтому программа печатает правильный ответ, т.е.7.
Есть и другие вариации данной задачи: например, подсчитать сумму цифр некоего большого числа, записанного в системе счисления с некоторым основанием. Решение этой и подобных задач оставляем читателю в качестве упражнения.
Дополнение: полезные функции Питона
В Питоне есть несколько полезных функций, относящихся к переводу чисел в различные системы счисления.
bin — переводит целое число в символьную строку, которая представляет запись данного числа в двоичной системе. В начале строки содержатся символы «0b», за ними следует собственно двоичное число.
oct — работает аналогично bin, переводит целое число в восьмеричную систему счисления, В начале строки содержатся символы «0o».
hex — перевод целого числа в шестнадцатеричную систему счисления, в начале строки содержатся символы «0x».
str — переводит целое число в символьную строку — запись этого числа в десятичной системе. Никаких дополнительных символов в начале строки нет.
int — переводит символьную строку в целое число. Ей пользуются для преобразования строк, прочитанных из файла, в числа. Однако эта функция может осуществлять перевод чисел, записанных в системе счисления с произвольным основанием, не превышающим 36. Для этого при вызове функции надо указать второй параметр: основание системы счисления, в которой представлено число. Для цифр со значением, большим, чем 9, используются латинские буквы A-Z (можно использовать как строчные, так и заглавные буквы). Так, для перевода строки «8A» (шестнадцатеричное число) в целое значение нужно написать вызов функции int(«8A»,16).
Если символы «0b» и т.п. в начале строки нам не нужны, их можно удалить, взяв подстроку без первых двух символов (вырезку). Для этого надо за строковым выражением написать операцию получения подстроки: [2:]
Приведем небольшой пример использования этих функций.
n = int( «235», 8 )
print( n )
print( bin(n) )
print( oct(n) )
print( hex(n) )
print( str(n) )
print( bin(n)[2:] )
Решение варианта ИН2010401 на Python
Рассмотрим решение некоторых задач из варианта ИН2010401 (Статград 2021 № 4).
Задача 2
Логическая функция F задаётся выражением ¬((?∨?)→(?∧?))∧(?→?) . Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F . Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w .
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
| . | . | . | . | F |
| 1 | 1 | 1 | 1 | |
| 1 | 1 | 1 | ||
| 1 | 1 | 1 |
В ответе напишите буквы x, y, z, w ; в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y , зависящее от двух переменных x и y , и фрагмент таблицы истинности:
| Переменная 1 | Переменная 1 | Функция |
| . | . | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y , а второму столбцу соответствует переменная x . В ответе нужно написать: yx .
Решение. Поскольку пока не известно, в каком столбце заголовка стоит какая переменная, дадим им произвольные имена по порядку, например a, b, c, d . После чего подставим их в функцию F и отобразим только строки, соответствующие значению F=1 . Рассмотрим два варианта решения:
Результат работы программы:
Ответ: zxy
Задача 5
Алгоритм получает на вход натуральное число ?>1 и строит по нему новое число ? следующим образом:
- Строится двоичная запись числа ?.
- Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется та цифра, которая встречается реже.
- Шаг 2 повторяется ещё два раза.
- Результат переводится в десятичную систему счисления.
Пример. Дано число ?=19. Алгоритм работает следующим образом:
- Двоичная запись числа N: 10011.
- В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110.
- В текущей записи нулей и единиц поровну, в конец записывается последняя цифра, это 0. Получается 1001100. В этой записи единиц меньше, в конец добавляется 1: 10011001.
- Результат работы алгоритма ?=153.
При каком наименьшем исходном числе ?>99 в результате работы алгоритма получится число, кратное 4?
Ответ: 103
Задание 6
Определите, при каком наименьшем введённом значении переменной ? программа выведет число 11. Для Вашего удобства программа представлена на двух языках программирования.
Ответ: 191
Задание 7
В информационной системе хранятся изображения размером 1024×768 пикселей. Методы сжатия изображений не используются. Каждое изображение дополняется служебной информацией, которая занимает 1280 Кбайт. Для хранения 2048 изображений потребовалось 4 Гбайт. Сколько цветов использовано в палитре каждого изображения?
Ответ: 256
Задача 8
Вероника составляет 3-буквенные коды из букв В,Е,Р,О,Н,И,К,А, причём буква В должна входить в код ровно один раз. Все полученные коды Вероника записала в алфавитном порядке и пронумеровала. Начало списка выглядит так:
- ААВ
- АВА
- АВЕ
- …
На каком месте будет записан первый код, не содержащий ни одной буквы А?
Ответ: 23
Задание 11
Каждый объект, зарегистрированный в информационной системе, получает уникальный код из 14 символов, каждый из которых может быть одной из 26 заглавных латинских букв или одной из 10 цифр. Для представления кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Кроме того, для каждого объекта в системе выделено 79 байт для хранения содержательной информации. Сколько байтов потребуется для хранения данных (код и содержательная информация) о 30 объектах? В ответе запишите только целое число – количество байтов.
Ответ: 2700
Задание 14
Значение выражения 729 7 +3 16 –18 записали в системе счисления с основанием 9. Сколько раз в этой записи встречается цифра 0?
Ответ: 14
Задание 15
Для какого наименьшего натурального числа ? формула ДЕЛ(?,45)∧(ДЕЛ(750,?)→(¬ДЕЛ(. )→¬ДЕЛ(120,?))) тождественно истинна, то есть принимает значение 1 при любом натуральном ??
Ответ: 90
Задача 16
Обозначим через . (. ) остаток от деления натурального числа ? на натуральное число ?. Алгоритм вычисления значения функции ?(?), где ? – целое неотрицательное число, задан следующими соотношениями:
- ?(0)=0;
- ?(?)=?(?/3), если ?>0 и при этом . (?,3)=0;
- ?(?)=. (?,3)+?(?–. (?,3)), если . (?,3)>0.
Назовите минимальное значение ?, для которого ?(?)=11.
Ответ: 485
Задача 17
Назовём натуральное число подходящим, если у него ровно 3 различных простых делителя. Например, число 180 подходящее (его простые делители – 2, 3 и 5), а число 12 – нет (у него только два различных простых делителя). Определите количество подходящих чисел, принадлежащих отрезку [10001;50000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.
Ответ: 15652 10002
Задача 22
Ниже записана программа, которая вводит натуральное число ?, выполняет преобразования, а затем выводит два числа. Укажите наименьшее возможное значение ?, при вводе которого программа выведет числа 3 и 10.
Ответ: 874
Задача 23
Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавить 1
- Умножить на 2
- Умножить на 3
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 2 в число 36, и при этом траектория вычислений содержит число 12 и не содержит числа 30?
Ответ: 60
Задача 24
Текстовый файл содержит строки различной длины. Общий объём файла не превышает 1 Мбайт. Строки содержат только заглавные буквы латинского алфавита (. …?).
Необходимо найти строку, содержащую наименьшее количество букв ? (если таких строк несколько, надо взять ту, которая находится в файле раньше), и определить, какая буква встречается в этой строке чаще всего. Если таких букв несколько, надо взять ту, которая позже стоит в алфавите.
Пример. Исходный файл:
В этом примере в первой строке две буквы G, во второй и третьей – по одной. Берём вторую строку, т. к. она находится в файле раньше. В этой строке чаще других встречаются буквы A и B (по два раза), выбираем букву B, т. к. она позже стоит в алфавите. В ответе для этого примера надо записать B.
Ответ: T
Задача 25
Найдите все натуральные числа, принадлежащие отрезку [35000000;40000000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.
Идея. Нас интересуют числа, являющиеся четвертой степенью простого числа, возможно умноженные на некоторую степень двойки.
Ответ: 35819648; 38950081; 39037448; 39337984
Задача 26
В текстовом файле записан набор натуральных чисел, не превышающих 10 9 . Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар.
Входные данные Первая строка входного файла содержит целое число ? – общее количество чисел в наборе. Каждая из следующих ? строк содержит одно число.
Пример входного файла
В данном случае есть две подходящие пары: 8 и 14 (среднее арифметическое 11), 14 и 2 (среднее арифметическое 8). В ответе надо записать числа 2 и 11. В ответе запишите два целых числа: сначала количество пар, затем наибольшее среднее арифметическое.
Ответ: 15; 976339247
Задача 27
В текстовом файле записан набор натуральных чисел, не превышающих 10 8 . Гарантируется, что все числа различны. Из набора нужно выбрать три числа, сумма которых делится на 3. Какую наибольшую сумму можно при этом получить?
Входные данные Первая строка входного файла содержит целое число ? – общее количество чисел в наборе. Каждая из следующих ? строк содержит одно число.
В данном случае есть две подходящие тройки: 5,14,11 (сумма 30) и 8,14,11 (сумма 33). В ответе надо записать число 33.
Вам даны два входных файла (? и ?), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла ?, затем для файла ?.