Задание 12. Здания 19 – 21

Задание 12

91. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a, b) (где a, b – целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Чертёжнику был дан для исполнения следующий алгоритм:

Сместиться на (1, -3)

Повтори ... раз

Сместиться на (..., …)

Сместиться на (-1, -2)

конец

Сместиться на (-25, -33)

После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «Повтори … раз»?

Ответ 12

92. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (333) ИЛИ нашлось (555)

ЕСЛИ нашлось (555)

ТО заменить (555, 3)

ИНАЧЕ заменить (333, 5)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке, состоящей из 184 идущих подряд цифр 5? В ответе запишите полученную строку.

Ответ 5335

93. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (4555)

ЕСЛИ нашлось (25) ТО заменить (25, 3) КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (355) ТО заменить (355, 4) КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (4555) ТО заменить (4555, 2) КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке, состоящей из цифры 3 и следующих за ней 57 цифр 5? В ответе запишите полученную строку.

Ответ 45

94. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (63) ИЛИ нашлось (664) ИЛИ нашлось (6665)

ЕСЛИ нашлось (63) ТО заменить (63, 4)

ИНАЧЕ

ЕСЛИ нашлось (664) ТО заменить (664, 5)

ИНАЧЕ

ЕСЛИ нашлось (6665) ТО заменить (6665, 3) КОНЕЦ ЕСЛИ

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке, в которой первая и последняя цифры – 4, а между ними стоит 125 цифр 6? В ответе запишите полученную строку.

Ответ 43

95. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

ПОКА нашлось (555) ИЛИ нашлось (333)

ЕСЛИ нашлось (333)

ТО заменить (333, 5)

ИНАЧЕ заменить (555, 3)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

Дана строка, состоящая из 500 цифр 5. Сколько пятёрок было удалено за время обработки строки по этой программе?

Ответ 561

96. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Если при выполнении команды заменить цепочка, которую нужно заменить, не найдена, то строка не изменяется. Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (56) ИЛИ нашлось (1111)

заменить (56, 1)

заменить (1111, 1)

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 102 строк 561 (561561561…561)?

Ответ 111

97. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

заменить (v, w)

нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

К исходной строке, содержащей не более 50 шестёрок и не содержащей других символов, применили приведённую ниже программу.

НАЧАЛО

ПОКА нашлось (66)

заменить (66, 1)

заменить (11, 2)

заменить (22, 6)

КОНЕЦ ПОКА

КОНЕЦ

В результате получилась строка 21. Какое наибольшее количество шестёрок могло быть в исходной строке?

Ответ 48

98. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

заменить (v, w)

нашлось (v)

Дана программа для Редактора:

НАЧАЛО

ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)

ЕСЛИ нашлось (>1)

ТО заменить (>1, 22>)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (>2)

ТО заменить (>2, 2>)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (>3)

ТО заменить (>3, 1>)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

На вход приведённой ниже программе поступает строка, начинающаяся с символа «>», а затем содержащая 11 цифр 1, 12 цифр 2 и 30 цифр 3, расположенных в произвольном порядке.

Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы. Так, например, если результат работы программы представлял бы собой строку, состоящую из 50 цифр 4, то верным ответом было бы число 200.

Ответ 98

99. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

заменить (v, w)

нашлось (v)

Дана программа для Редактора:

Исходная строка содержит 12 единиц и 4 двойки, других цифр нет, точный порядок расположения цифр неизвестен. Какую наибольшую сумму цифр может иметь строка, которая получится после

выполнения программы?

Ответ 34

100. Исполнитель Редактор получает на вход строку цифр и преобразовывает её.

Определите максимально возможное количество цифр 1, которое может получиться в результате применения представленного ниже алгоритма к строке, состоящей из 30 цифр 2, 30 цифр 3 и 30 цифр 1, идущих в произвольном порядке.

Ответ 90

Задание 13.

101. На рисунке приведена схема дорог, соединяющих пункты А, Б, В, Г, Д, Е, Ж, З, И, К, Л. Передвигаться можно только по указанным дорогом в указанном направлении. Определите длину самого длинного маршрута из А в Л, не проходящего через пункт Г? Длиной маршрута считать количество пройденных дорог.

Ответ 5

102. На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Е и при этом не проходящих через пункт Л?

Ответ 14

103. На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно передвигаться только в направлении, указанном стрелкой, для каждой дороги указано время проезда в минутах. За какое минимальное время можно проехать из пункта А в пункт Л? В ответе укажите только число – время в минутах, указывать единицы измерения не нужно

Ответ 200

Задание 14

104. Решите уравнение: 101_x + 13₁₀ = 101_х+1

Ответ 6

105. В системе счисления с основанием N запись числа 87₁₀ оканчивается на 2 и содержит не менее трёх цифр. Чему равно число N?

Ответ 5

106. Значение арифметического выражения: 64¹⁵⁰ + 4³⁰⁰ – 32 записали в системе счисления с основанием 8. Сколько цифр «7» в этой записи?

Ответ 198

107. Значение арифметического выражения 3 ⋅ 256³²⁰ - 2 ⋅ 64²⁹⁰ + 4²⁵⁰ – 1023 записали в системе счисления с основанием 4. Найдите количество ненулевых разрядов в этой записи.

Ответ 657

108. Число, являющееся результатом выражения 5²⁰ + 5¹⁰ – 5¹³ – 5³, записали в системе счисления с основанием 5. Чему равна сумма цифр в получившейся записи? В ответе укажите одно десятичное число – сумма разрядов пятеричного числа.

Ответ 56

109. При каком наименьшем натуральном значении переменной x в выражении 81²⁰ – 9^x + 50 сумма цифр в девятеричной записи числа равна 138?

Ответ 24

110. Сколько существует целых положительных чисел, которые соответствуют следующим условиям:

- в пятеричной записи содержится не более 4 цифр,

- в двоичной записи не менее 5 цифр,

- последняя цифра в шестнадцатеричной системе счисления – C?

Ответ 38

Задание 15

111. Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа А формула x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

Ответ 12

112. Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

Для какого наименьшего неотрицательного целого числа А формула

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?

Ответ 44

113. На числовой прямой даны два отрезка: Р = [3, 38] и Q = [21, 57]. Какова наибольшая возможная длина интервала A, что логическое выражение ((х ∈ Q) → (х ∈ Р)) → (х ∈ A) тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

Ответ 19

114. На числовой прямой даны два отрезка: Р = [22, 72] и Q = [42, 102]. Какова наименьшая возможная длина интервала A, что логическое выражение ((х ∈ А) ∧ (х ∈ Р)) ∨ (х ∈ Q) тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

Ответ 20

115. На числовой прямой даны два отрезка: P = [17, 54] и Q = [37, 83]. Какова наименьшая возможная длина интервала A, что формула (x ∈ P) → (((x ∈ Q) ∧ (x ∈ A)) → (x ∈ P))

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

Ответ 17

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.

Ответ 36

117. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула

ДЕЛ(120, A) ∧ (ДЕЛ(x, А) → (ДЕЛ(x, 18) → ДЕЛ(x, 24)))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Ответ 24

118. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула

ДЕЛ(A, 45) ∧ (ДЕЛ(750, x) → (ДЕЛ(A, x) → ДЕЛ(120, x)))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Ответ 90

119. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула

(A < 50) ∧ (ДЕЛ(x, А) → (ДЕЛ(x, 10) → ДЕЛ(x, 12)))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Ответ 30

120. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Сколько существует натуральных значений A на отрезке [1;1000], при которых формула ДЕЛ(A, 9) ∧ (ДЕЛ(280, x) → (ДЕЛ(A, x) → ДЕЛ(730, x))) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Ответ 11

121. Для какого наименьшего целого неотрицательного числа А выражение

(3x + 7y < A) ∨ (x ≥ y) ∨ (y > 6)

тождественно истинно, т. е. принимает значение 1 при любых целых неотрицательных x и y?

Ответ 58

122. Для какого наименьшего целого значения параметра А существует выражение

(x > 39) ∨ (y > 26) ∨ (2x + 4y < A) является тождественно истинным, то есть принимает значение 1 при любых целых положительных значениях переменных х и у.

Ответ 183

123. Укажите наибольшее целое значение А, при котором выражение (2x + 3y = 101) ∧ (x + y < A) ложно для любых целых положительных значений x и y.

Ответ 34

124. Для какого наибольшего целого числа А формула ((x ≤ 9) →(x ⋅ x ≤ A)) ⋀ ((y ⋅ y ≤ A) → (y ≤ 9)) тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?

Ответ 99

125. На числовой прямой задан отрезок A. Известно, что формула

((x ∈ A) → (x² ≤ 100)) ∧ ((x² ≤ 64) → (x ∈ A)) тождественно истинна при любом вещественном x. Какую наибольшую длину может иметь отрезок A?

Ответ 20

Задание 16

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)?

Ответ 5158048

127. Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:

F(1) = G(1) = 1

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)?

Ответ 1594324

128. Определите, сколько символов * выведет эта процедура при вызове F(35):

def F( n ):

print('*')

if n >= 1:

print('*')

F(n-1)

F(n-2)

print('*')

Ответ 96631265

129. Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 5000000. Запишите в ответе найденное значение n

def F( n ):

print(2*n+1)

if n > 1:

print(3*n-8)

F(n-1)

F(n-4)

Ответ 40

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.

Ответ 100

131. Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = n, при n <= 5,

F(n) = n + F(n / 5 + 1), когда n > 5 и делится на 5,

F(n) = n + F(n + 6) , когда n > 5 и не делится на 5.

Назовите минимальное значение n, для которого F(n) > 1000

Ответ 131

132. Чему равно значение функции f(30):

Квадратные скобки в записи [x] применяются для обозначения целой части числа x

Ответ 26

Задание 17

133. Рассматривается множество целых чисел, принадлежащих числовому отрезку [22500; 70813], которые оканчиваются на 3 и при этом не делятся ни на 7, ни на 13. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число.

Ответ 382370813

134. Рассматривается множество целых чисел, принадлежащих числовому отрезку [2807; 8558], которые удовлетворяют следующим условиям:

− запись в двоичной системе заканчивается на 11;

− запись в девятеричной системе заканчивается на 5.

Найдите максимальное из таких чисел и их сумму. Гарантируется, что искомая сумма не превосходит 10⁷.

Ответ 8555910880

135. Рассматривается множество целых чисел, принадлежащих числовому отрезку [3905; 7998], которые удовлетворяют следующим условиям:

− цифра в разряде десятков отлична от 0 и 5;

− цифра в разряде сотен принадлежит отрезку [2; 6].

Найдите количество таких чисел и минимальное из них.

Ответ 16004210

136. Рассматривается множество целых чисел, принадлежащих числовому отрезку [8800; 55535], которые удовлетворяют следующим условиям:

− произведение разрядов больше 35;

− один из разрядов равен 7.

Найдите наибольшее из таких чисел и их количество.

Ответ 5552710958

137. Рассматривается множество целых чисел, принадлежащих числовому отрезку [54123; 75321], которые имеют ровно 5 делителей в диапазоне [10;20].Найдите количество таких чисел и максимальное из них.

Ответ 19375180

Задание 18

138. Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную.

Ответ 1372648

139. Квадрат разлинован на N×N клеток (2 < N < 21). В каждой клетке записано целое положительное число – количество монет. Исполнитель Сборщик имеет две команды ВПРАВО и ВВЕРХ, которые, соответственно, перемещают его на одну клетку вправо или на одну клетку вверх. Проходя через клетку, Сборщик собирает все монеты, лежащие на ней. На поле существуют стены, обозначены жирной линией, через которые Сборщик проходить не может. Исполнитель начинает движение в левой нижней клетке и заканчивает в правой верхней. Какое максимальное и минимальное количество монет может собрать Сборщик, пройдя от начальной клетки до конечной? В ответе укажите сначала максимальный, затем минимальный результат, который может быть получен исполнителем.

Ответ 45073066

140. Квадрат разлинован на NxN клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата записано натуральное число, не превышающее 100. Перемещаясь по клеткам квадрата, Робот вычисляет сумму следующим образом. Начальное значение суммы - значение той клетки, из которой Робот начинает движение. При посещении клетки, Робот прибавляет к сумме удвоенное значение, записанное в клетке, если он попал в эту клетку из соседней сверху клетки, и прибавляет к сумме утроенное значение, записанное в клетке, если он попал в эту клетку из соседней слева клетки. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала минимальную сумму, затем максимальную.

Ответ 11721771

Здания 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.

Ответ 249

154. Найдите минимальное число x > 100, при вводе которого приведенный алгоритм напечатает на экране число 30.

Ответ 120

155. Ниже на четырёх языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, не содержащее нулей, при вводе которого алгоритм печатает сначала 14, а потом 3.

Ответ 999419

156. Ниже записана программа. Получив на вход число x, эта программа печатает два числа число L и M. Сколько существует натуральных чисел x, при вводе которых алгоритм печатает 6 и 0.

Ответ 4915200

Задание 23

157. Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 2

2. Умножить на 3

Первая команда увеличивает число на экране на 2, вторая умножает его на 3. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 63 и при этом траектория вычислений содержит число 25 и не содержит число 6?

Ответ 8

158. Исполнитель U18 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Вычесть 1

2. Вычесть 3

3. Разделить нацело на 3

При выполнении команды 3 выполняется деление нацело (остаток отбрасывается). Программа для исполнителя U18 – это последовательность команд. Сколько существует таких программ, которые исходное число 22 преобразуют в число 2?

Ответ 2196

159. Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 3

2. Умножить на 2 и отнять 1

Первая команда увеличивает число на экране на 3, вторая умножает его на 2 и вычитает из результата 1.

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 30, и при этом траектория вычислений содержит число 21 и не содержит 10?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 10, 19, 38.

Ответ 8

160. Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:

1. прибавь 1

2. сделай нечётное

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ – это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 27, причём траектория вычислений не содержит число 26? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Ответ 13

Задание 24

161. Текстовый файл состоит не более чем из 106 символов X, Y и Z.

Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.

Для выполнения этого задания следует написать программу.

Ответ 35

162. Текстовый файл состоит не более чем из 106 символов F, A, I, L. Определите максимальное количество подряд идущих одинаковых букв.

Ответ 75

163. Текстовый файл состоит не более чем из 106 символов J, O, B, S. Сколько раз встречаются комбинации «BOSS» при этом до и после этого слова нет символа «J». Например, комбинации «JBOSS», «BOSSJ» и «JBOSSJ» не должны учитываться. Для выполнения этого задания следует написать программу.

Ответ 2198

164. Текстовый файл состоит не более чем из 106 символов и содержит только заглавные латинские буквы и десятичные цифры. Определите максимальное нечётное число, записанное в этом файле.

Ответ 7642289

165. Текстовый файл состоит не более чем из 106 символов и содержит только заглавные латинские буквы и десятичные цифры. Под словом подразумевается последовательность букв, ограниченная цифрами. Определите количество четырёхбуквенных слов. Словом считается любая произвольная последовательность букв.

Ответ 30

166. Текстовый файл состоит не более чем из 1200000 символов, которые являются прописными буквами латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых нет подстроки XYZ. Для выполнения этого задания следует написать программу.

Ответ 305

167. Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Текст разбит на строки различной длины. Необходимо найти строку, содержащую наибольшее количество букв Q (если таких строк несколько, надо взять ту, которая в файле встретилась позже). Определите, какая буква встречается в этой строке реже всего (но присутствует!). Если таких букв несколько, надо взять ту, которая стоит раньше в алфавите. Запишите в ответе эту букву, а затем – сколько раз она встречается во всем файле.

Пример. Исходный файл:

ZZQAQB

QAVQAB

BAQTUB

В этом примере в первой и второй строках по две букву Q, в третьей – одна. Берём вторую строку, т.к. она стоит в файле позже. В этой строке реже других встречаются буквы V и B (по одному разу), выбираем букву B, т. к. она раньше стоит в алфавите. В ответе для этого примера надо записать B4, так как во всех строках файла буква B встречается 4 раза.

Ответ C38412

168. В файле 24.txt записана последовательность символов. Укажите длину самой длинной последовательности, состоящей из одинаковых символов.

Ответ 4

169. В файле 24.txt записана последовательность символов. На какой позиции от начала строки встречается 123 буква «f»? Нумерация символов в строке ведется с единицы.

Ответ 4276

Задание 25

170. Напишите программу, которая ищет среди целых чисел, превышающих 136179, первые четыре числа, удовлетворяющих условию: сумма всех различных делителей числа, отличных от 1 и самого числа, при делении на 385 даёт остаток 91.

В ответе запишите эти четыре пары чисел в порядке возрастания первого числа в паре: число и сумму его различных делителей (исключая 1 и само число).

Ответ 13877869391

171. Пусть S - сумма натуральных чётных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение S равным нулю.

Напишите программу, которая перебирает целые числа из отрезка [1204300; 1204380] в порядке возрастания и ищет среди них такие, для которых значение S не равно нулю и кратно 10. Программа должна найти и вывести такие числа и соответствующие им значения S.

Формат вывода: для каждого из найденных чисел в отдельной строке сначала выводится само число, затем значение S. Строки выводятся в порядке возрастания найденных чисел.

Ответ 1204378172070

172. Рассмотрим произвольное натуральное число, представим его всеми возможными способами в виде произведения двух натуральных чисел и найдём для каждого такого произведения разность сомножителей. Например, для числа 18 получим: 18 = 18*1 = 9*2 = 6*3, множество разностей содержит числа 17, 7 и 3. Подходящей будем называть пару сомножителей, разность между которыми не превышает 120. Найдите все натуральные числа, принадлежащие отрезку [2000000; 3000000], у которых есть не менее трёх подходящих пар сомножителей. В ответе перечислите найденные числа в порядке возрастания, справа от каждого запишите наибольший из всех сомножителей, образующих подходящие пары.

Ответ 26928001700

173. Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Найдите все натуральные числа, принадлежащие отрезку [106732567; 152673836] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе само число и его наибольший нетривиальный делитель. Найденные числа расположите в порядке возрастания.

Например, для числа 2018 имеем следующие делители 2 и 1009. Поэтому результатом (не принимая во внимание количества делителей) будет пара чисел 2018 1009

Ответ 1411581611295029

Задание 26

174. Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. Администратор отбирает файлы в архив таким образом, что в него будут сохранены файлы наибольшего возможного количества пользователей.

По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимально возможный суммарный объём файлов в архиве, а также количество файлов, которые ни при каких условиях не могут попасть в архив.

Входные данные.

В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.

Запишите в ответе два числа: сначала максимально возможный суммарный объём файлов в архиве, затем количество файлов, которые ни при каких условиях не могут попасть в архив, при условии, что сохранены файлы максимально возможного числа пользователей.

Пример организации исходных данных во входном файле:

100 7

При таких исходных данных в архив можно записать файлы максимум 3 пользователей. При этом максимально возможная сумма будет из файлов размером 10, 34, 47. А файлы размером 65, 66, 90 не смогут попасть в архив ни при каких условиях.

Ответ к приведённому при

⇐ Предыдущая 12