ИН2210201 ИН2210202 статград информатика 11 класс ЕГЭ 2023 варианты и ответы
Тренировочная работа №2 статград пробный ЕГЭ 2023 по информатике 11 класс 2 тренировочных варианта ИН2210201 и ИН2210202 с ответами и решением. Официальная дата проведения работы: 15 декабря 2022 год.
Статград информатика 11 класс ЕГЭ 2023 варианты и ответы
Вариант ИН2210201 и ответы
Задание 1. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что дорога АБ длиннее дороги БД. Определите длину дороги ГЖ.
Задание 2. Логическая функция F задаётся выражением: (x ≡ ¬y) → ((z → ¬w) ∧ (w → y)) Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Задание 3. В файле приведён фрагмент базы данных «Продукты», содержащей информацию о поставках товаров и их продаже. База данных состоит из трёх таблиц. Таблица «Торговля» содержит записи о поставках и продажах товаров в магазинах города в июне 2021 г. Таблица «Товар» содержит данные о товарах. Таблица «Магазин» содержит данные о магазинах. На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. Используя информацию из приведённой базы данных, определите магазин, получивший наибольшую общую сумму выручки от продаж товаров отдела «Молоко» с 10 по 12 июня. В ответе запишите число – найденную наибольшую сумму выручки в рублях.
Задание 4. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова некоторых букв: А – 00, М – 0100, Д – 101, Х – 11. Известно также, что код слова ЛИЛИЯ содержит 17 двоичных знаков. Сколько двоичных знаков содержит код слова МИЛЯ?
Задание 5. Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Если сумма цифр десятичной записи заданного числа нечётна, то в конец двоичной записи дописывается 1, если чётна – 0. 3–4. Пункт 2 повторяется для вновь полученных чисел ещё два раза. 5. Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример. Дано число N = 17. Алгоритм работает следующим образом: 1. Строим двоичную запись: 1710 = 100012. 2. Сумма цифр числа 17 – чётная, дописываем к двоичной записи 0, получаем 1000102 = 3410. 3. Сумма цифр числа 34 – нечётная, дописываем к двоичной записи 1, получаем 10001012 = 6910. 4. Сумма цифр числа 69 – нечётная, дописываем к двоичной записи 1, получаем 100010112 = 13910. 5. Результат работы алгоритма R = 139. Определите наименьшее возможное значение R > 1028, которое может получиться в результате работы алгоритма.
Задание 6. Исполнитель Черепаха передвигается по плоскости и оставляет след в виде линии. Черепаха может выполнять три команды: Вперёд n (n – число), Направо m (m – число), и Налево m (m – число). По команде Вперёд n Черепаха перемещается вперёд на n единиц. По команде Направо m Черепаха поворачивается на месте на m градусов по часовой стрелке, при этом соответственно меняется направление дальнейшего движения. По команде Налево m Черепаха поворачивается на месте на m градусов против часовой стрелки, при этом соответственно меняется направление дальнейшего движения.
В начальный момент Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат). Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что заданная последовательность из S команд повторится k раз. Черепаха выполнила следующую программу: Повтори 4 [ Вперёд 7 Направо 90 Вперёд 7 Налево 90 Вперёд 7 Направо 90 ] Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, полученной при выполнении данной программы. Точки, расположенные на линии, не учитывать.
Задание 7. Изображение было отсканировано с разрешением 150 dpi, а затем сохранено со сжатием на 20 %. Размер полученного файла составил 4 Мбайт. Затем то же изображение было отсканировано с разрешением 300 dpi и сохранено со сжатием на 40 %. Определите размер нового файла. В ответе запишите только число – размер файла в Мбайтах.
Задание 8. Вероника составляет коды из букв слова ВЕРОНИКА. Код должен состоять из 6 букв, любую букву можно использовать произвольное число раз или не использовать вовсе. Вероника хочет, чтобы гласных в каждом коде было больше, чем согласных. Сколько кодов, удовлетворяющих этому условию, она сможет составить?
Задание 9. В каждой строке электронной таблицы записаны пять натуральных чисел. Определите, сколько в таблице строк, для которых выполнены следующие условия: – все числа в строке различны; – нечётных чисел больше, чем чётных; – сумма нечётных чисел меньше суммы чётных. В ответе запишите число – количество строк, для которых выполнены эти условия.
Задание 10. Определите, сколько раз в тексте романа Михаила Булгакова «Мастер и Маргарита» встречается фамилия Лиходеев в начальной форме.
Задание 11. В базе данных хранится информация об объектах определённой структуры. Каждый объект описывается как последовательность из 290 простых элементов, при этом всего используется 1012 различных простых элементов. Каждое описание объекта записывается как последовательность кодов простых элементов, при этом код каждого элемента содержит одинаковое для всех элементов минимально возможное число битов, а для описания в целом отводится минимально возможное целое число байтов. Сколько Кбайтов потребуется для хранения 32 768 описаний, построенных по такой схеме? В ответе запишите только число – количество Кбайтов.
Задание 12. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Задание 13. На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в пункте Д, не содержат этот пункт в качестве промежуточного и проходят через любой другой пункт не более одного раза.
Задание 14. В выражении 123×37 + 4×5937 x обозначает некоторую цифру из алфавита системы счисления c основанием 37. Определите наименьшее значение x, при котором значение данного выражения кратно 36. Для найденного x вычислите частное от деления данного выражения на 36 и запишите его в ответе в десятичной системе счисления.
Задание 15. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Укажите наименьшее целое значение A, для которого формула (ДЕЛ(144, x)→ ¬ДЕЛ(x, y)) ∨ (x + y > 100) ∨ (A – x > y) тождественно истинна при любых натуральных значениях переменных x и y.
Задание 16. Обозначим частное от деления натурального числа a на натуральное число b как a div b, а остаток как a mod b. Например, 13 div 3 = 4, 13 mod 3 = 1. Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями: F(0) = 0; F(n) = F(n div 10) + (n mod 10). Укажите количество таких чисел n из интервала 237 567 892 ≤ n ≤ 1 134 567 009, для которых F(n) > F(n + 1)
Задание 17. Файл содержит последовательность целых чисел, по модулю не превышающих 10 000. Назовём парой два идущих подряд элемента последовательности. Определите количество таких пар, в которых запись меньшего элемента заканчивается цифрой 5, а сумма квадратов элементов пары меньше, чем квадрат наименьшего из элементов последовательности, запись которых заканчивается цифрой 5. В ответе запишите два числа: сначала количество найденных пар, затем максимальную сумму квадратов элементов этих пар.
Задание 18. Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз, по диагонали вправо-вниз или по диагонали влево-вниз. Числа показывают расход энергии робота на прохождение клетки. Определите максимальный расход энергии при переходе робота в правую нижнюю клетку поля и количество клеток с нечётными числами, через которые робот проходит на пути с максимальным расходом энергии.
В ответе запишите два числа: сначала максимальный расход энергии, затем – количество пройденных клеток с нечётными значениями. Исходные данные записаны в электронной таблице. Пример входных данных (для таблицы размером 4×4).
При указанных входных данных максимальный расход получится при движении по маршруту 43 + 90 + 72 + 30 + 36 + 63 + 61 + 84 + 49 + 51 = 579. При этом робот проходит через 5 клеток с нечётными числами (43, 63, 61, 49, 51). В ответе в данном случае надо записать числа 579 и 5.
Задание 19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче 5 камней, а во второй – 8 камней, будем обозначать такую позицию (5, 8).
Петя первым ходом должен добавлять камни в первую кучу, он может получить позиции (6, 8), (7, 8) и (10, 8). Если Петя получает позиции (6, 8) и (7, 8), Ваня следующим ходом тоже должен добавлять камни в первую кучу, а если Петя получает позицию (10, 8), Ваня должен добавлять камни во вторую кучу, так как теперь она стала меньшей. Игра завершается, когда общее количество камней в двух кучах становится более 80. Победителем считается игрок, сделавший последний ход, то есть первым получивший 81 или больше камней в двух кучах. В начальный момент в первой куче было 12 камней, а во второй – S камней, 1 ≤ S ≤ 68. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите минимальное из таких значений S, при которых Петя не может выиграть за один ход, но при любом ходе Пети Ваня сможет выиграть своим первым ходом.
Задание 20. Для игры, описанной в задании 19, укажите минимальное и максимальное из таких значений S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани. В ответе запишите сначала минимальное значение, затем максимальное.
Задание 21. Для игры, описанной в задании 19, найдите максимальное из таких значений S, при которых у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
Задание 22. В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени.
Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов. В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов. Определите, какое наибольшее количество процессов может быть завершено за первые 170 мс с момента запуска первого процесса.
Задание 23. Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 2, 3, 6. Сколько существует программ, которые преобразуют исходное число 1 в число 14, и при этом никакая команда не повторяется более двух раз подряд?
Задание 24. Текстовый файл содержит только буквы A, C, D, F, O. Определите длину самой длинной цепочки символов, которая начинается и заканчивается буквой F, а между двумя последовательными буквами F содержит не более двух букв A и произвольное количество других букв.
Задание 25. Маска числа – это последовательность цифр, в которой могут встречаться специальные символы «?» и «*». Символ «?» означает ровно одну произвольную цифру, символ «*» означает произвольную (в том числе пустую) последовательность цифр. Пример. Маске 123*4?5 соответствуют числа 123405 и 12376415. Найдите все натуральные числа, не превышающие 109 , которые соответствуют маске 12*63?5? и при этом без остатка делятся на 3123. В ответе запишите все найденные числа в порядке возрастания.
26. На складе хранятся кубические контейнеры двух цветов различного размера. Чтобы сократить занимаемое при хранении место, контейнеры вкладывают друг в друга. Чтобы вложенные контейнеры было лучше видно, их цвета при вложении обязательно должны чередоваться, то есть нельзя вкладывать контейнер в контейнер такого же цвета. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на 5 и более условных единиц. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку. Зная размеры и цвета всех контейнеров, определите максимально возможное количество контейнеров в одном блоке и минимальное количество ячеек для хранения всех контейнеров.
27. Дана последовательность натуральных чисел. Назовём парой любые два числа из последовательности. Необходимо определить количество пар, в которых сумма чисел в паре делится без остатка на 4, а их произведение на 6561. Входные данные Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 100 000. Гарантируется, что число в ответе не превышает 2 ∙ 10 9 . Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала искомое количество пар для файла A, затем – для файла B.
Вариант ИН2210202 и ответы
1. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что дорога АБ длиннее дороги БГ. Определите длину дороги ДЖ.
2. Логическая функция F задаётся выражением: (z ≡ ¬x) → ((w → ¬y) ∧ (y → x)) Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
3.В файле приведён фрагмент базы данных «Продукты», содержащей информацию о поставках товаров и их продаже. База данных состоит из трёх таблиц. Таблица «Торговля» содержит записи о поставках и продажах товаров в магазинах города в июне 2021 г. Таблица «Товар» содержит данные о товарах. Таблица «Магазин» содержит данные о магазинах. На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. Используя информацию из приведённой базы данных, определите магазин, получивший наибольшую общую сумму выручки от продаж товаров отдела «Мясная гастрономия» с 7 по 9 июня. В ответе запишите число – найденную наибольшую сумму выручки в рублях.
4. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова некоторых букв: Б – 00, Г – 010, Д – 1011, О – 11. Известно также, что код слова ЗАКАЗ содержит 17 двоичных знаков. Сколько двоичных знаков содержит код слова КОЗА?
5. Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Если сумма цифр десятичной записи заданного числа нечётна, то в конец двоичной записи дописывается 1, если чётна – 0. 3–4. Пункт 2 повторяется для вновь полученных чисел ещё два раза. 5. Результатом работы алгоритма становится десятичная запись полученного числа R.
6. Исполнитель Черепаха передвигается по плоскости и оставляет след в виде линии. Черепаха может выполнять три команды: Вперёд n (n – число), Направо m (m – число), и Налево m (m – число). По команде Вперёд n Черепаха перемещается вперёд на n единиц. По команде Направо m Черепаха поворачивается на месте на m градусов по часовой стрелке, при этом соответственно меняется направление дальнейшего движения. По команде Налево m Черепаха поворачивается на месте на m градусов против часовой стрелки, при этом соответственно меняется направление дальнейшего движения. В начальный момент Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат).
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что заданная последовательность из S команд повторится k раз. Черепаха выполнила следующую программу: Повтори 4 [ Вперёд 6 Направо 90 Вперёд 6 Налево 90 Вперёд 6 Направо 90 ] Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, полученной при выполнении данной программы. Точки, расположенные на линии, не учитывать.
7. Изображение было отсканировано с разрешением 200 dpi, а затем сохранено со сжатием на 25 %. Размер полученного файла составил 15 Мбайт. Затем то же изображение было отсканировано с разрешением 300 dpi и сохранено со сжатием на 40 %. Определите размер нового файла. В ответе запишите только число – размер файла в Мбайтах.
8. Полина составляет коды из букв слова ПОЛИНА. Код должен состоять из 8 букв, любую букву можно использовать произвольное число раз или не использовать вовсе. Полина хочет, чтобы согласных в каждом коде было больше, чем гласных. Сколько кодов, удовлетворяющих этому условию, она сможет составить?
9. Каждой строке электронной таблицы записаны пять натуральных чисел. Определите, сколько в таблице строк, для которых выполнены следующие условия: – все числа в строке различны; – чётных чисел больше, чем нечётных; – сумма чётных чисел меньше суммы нечётных. В ответе запишите число – количество строк, для которых выполнены эти условия.
10. Определите, сколько раз в тексте романа Михаила Булгакова «Мастер и Маргарита» встречается имя Фагот в начальной форме.
11. В базе данных хранится информация об объектах определённой структуры. Каждый объект описывается как последовательность из 310 простых элементов, при этом всего используется 980 различных простых элементов. Каждое описание объекта записывается как последовательность кодов простых элементов, при этом код каждого элемента содержит одинаковое для всех элементов минимально возможное число битов, а для описания в целом отводится минимально возможное целое число байтов. Сколько Кбайтов потребуется для хранения 16 384 описаний, построенных по такой схеме? В ответе запишите только число – количество Кбайтов.
12. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
13. На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в пункте Д, не содержат этот пункт в качестве промежуточного и проходят через любой другой пункт не более одного раза.
14. В выражении 317×37 + 4×2937 x обозначает некоторую цифру из алфавита системы счисления c основанием 37. Определите наименьшее значение x, при котором значение данного выражения кратно 36. Для найденного x вычислите частное от деления данного выражения на 36 и запишите его в ответе в десятичной системе счисления.
15. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Укажите наименьшее целое значение A, для которого формула (ДЕЛ(108, x)→ ¬ДЕЛ(x, y)) ∨ (x + y > 80) ∨ (A – y > x) тождественно истинна при любых натуральных значениях переменных x и y.
16. Обозначим частное от деления натурального числа a на натуральное число b как a div b, а остаток как a mod b. Например, 13 div 3 = 4, 13 mod 3 = 1. Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями: F(0) = 0; F(n) = F(n div 10) + (n mod 10). Укажите количество таких чисел n из интервала 765 432 015 ≤ n ≤ 1 542 613 239, для которых F(n) > F(n + 1)
17. Файл содержит последовательность целых чисел, по модулю не превышающих 10 000. Назовём парой два идущих подряд элемента последовательности. Определите количество таких пар, в которых запись меньшего элемента заканчивается цифрой 3, а сумма квадратов элементов пары меньше, чем квадрат наименьшего из элементов последовательности, запись которых заканчивается цифрой 3. В ответе запишите два числа: сначала количество найденных пар, затем максимальную сумму квадратов элементов этих пар.
18. Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вверх, по диагонали вправо-вверх или по диагонали влево-вверх. Числа показывают расход энергии робота на прохождение клетки. Определите максимальный расход энергии при переходе робота в правую верхнюю клетку поля и количество клеток с нечётными числами, через которые робот проходит на пути с максимальным расходом энергии. В ответе запишите два числа: сначала максимальный расход энергии, затем – количество пройденных клеток с нечётными значениями. При указанных входных данных максимальный расход получится при движении по маршруту 21 + 84 + 49 + 50 + 61 + 42 + 36 + 90 + 2 + 45 = 480. При этом робот проходит через 4 клетки с нечётными числами (21, 49, 61, 45). В ответе в данном случае надо записать числа 480 и 4.
19.Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче 5 камней, а во второй – 8 камней, будем обозначать такую позицию (5, 8). Петя первым ходом должен добавлять камни в первую кучу, он может получить позиции (6, 8), (7, 8) и (10, 8). Если Петя получает позиции (6, 8) и (7, 8), Ваня следующим ходом тоже должен добавлять камни в первую кучу, а если Петя получает позицию (10, 8), Ваня должен добавлять камни во вторую кучу, так как теперь она стала меньшей. Игра завершается, когда общее количество камней в двух кучах становится более 60. Победителем считается игрок, сделавший последний ход, то есть первым получивший 61 или больше камней в двух кучах. В начальный момент в первой куче было 8 камней, а во второй – S камней, 1 ≤ S ≤ 52. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите минимальное из таких значений S, при которых Петя не может выиграть за один ход, но при любом ходе Пети Ваня сможет выиграть своим первым ходом.
20. Для игры, описанной в задании 19, укажите минимальное и максимальное из таких значений S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани. В ответе запишите сначала минимальное значение, затем максимальное.
21. Для игры, описанной в задании 19, найдите максимальное из таких значений S, при которых у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
22. В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов. В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов. Определите, какое наибольшее количество процессов может быть завершено за первые 120 мс с момента запуска первого процесса.
23. Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 2, 3, 6. Сколько существует программ, которые преобразуют исходное число 1 в число 16, и при этом никакая команда не повторяется более двух раз подряд?
24. Текстовый файл содержит только буквы A, C, D, F, O. Определите длину самой длинной цепочки символов, которая начинается и заканчивается буквой D, а между двумя последовательными буквами D содержит не более двух букв O и произвольное количество других букв.
25. Маска числа – это последовательность цифр, в которой могут встречаться специальные символы «?» и «*». Символ «?» означает ровно одну произвольную цифру, символ «*» означает произвольную (в том числе пустую) последовательность цифр. Пример. Маске 123*4?5 соответствуют числа 123405 и 12376415. Найдите все натуральные числа, не превышающие 109 , которые соответствуют маске 12*93?1? и при этом без остатка делятся на 3127. В ответе запишите все найденные числа в порядке возрастания.
26. На складе хранятся кубические контейнеры двух цветов различного размера. Чтобы сократить занимаемое при хранении место, контейнеры вкладывают друг в друга. Чтобы вложенные контейнеры было лучше видно, их цвета при вложении обязательно должны чередоваться, то есть нельзя вкладывать контейнер в контейнер такого же цвета. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на 7 и более условных единиц. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку. Зная размеры и цвета всех контейнеров, определите максимально возможное количество контейнеров в одном блоке и минимальное количество ячеек для хранения всех контейнеров.
27. Дана последовательность натуральных чисел. Назовём парой любые два числа из последовательности. Необходимо определить количество пар, в которых сумма чисел в паре делится без остатка на 4, а их произведение – на 59 049.