1 Ответ
Задание 1. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что дорога КИ короче дороги АГ. Определите длину дороги ДЖ.
Ответ: 22
Задание 2. Логическая функция F задаётся выражением: (w → ¬(z ≡ y)) ∧ (z ∨ (y → x))
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Ответ: yxwz
Задание 3. В файле приведён фрагмент базы данных «Продукты», содержащей информацию о поставках товаров и их продаже. База данных состоит из трёх таблиц.
Таблица «Торговля» содержит записи о поставках и продажах товаров в магазинах города в июне 2021 г. Таблица «Товар» содержит данные о товарах. Таблица «Магазин» содержит данные о магазинах.
На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними.
Используя информацию из приведённой базы данных, определите, в какой день в магазинах Заречного района выручка от продажи товаров отдела «Молоко» была наибольшей.
В ответе запишите целое число от 1 до 30, соответствующее числу искомой даты. Например, ответ 1 означает, что наибольшая выручка была получена 1 июня.
Ответ: 20
Задание 4. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: И – 110, Н – 011, Ф – 00, О – 1111, Р – 11100, М – 11101, А – 1001, Т – 101, К – 1000 Сколько существует способов назначить для буквы Ю код, длина которого не превышает шести двоичных знаков?
Ответ: 14
Задание 5. Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1 Строится троичная запись числа N.
2 В полученной записи все нули заменяются на двойки, все двойки – на нули.
Из полученного числа удаляются ведущие нули.
3 Результат переводится в десятичную систему счисления.
4 Результатом работы алгоритма становится модуль разности исходного числа N и числа, полученного на предыдущем шаге.
Пример. Дано число N = 35 Алгоритм работает следующим образом.
1 Строим троичную запись числа N: 3510 = 10223
2 Заменяем цифры и удаляем ведущие нули: 1022 → 1200
3 Переводим в десятичную систему: 12003 = 4510
4 Вычисляем модуль разности: | 35 – 45 | = 10
Результат работы алгоритма R = 10
При каком наименьшем N в результате работы алгоритма получится R = 1 864 246?
Ответ: 3 323 607
Задание 6. Исполнитель Черепаха передвигается по плоскости и оставляет след в виде линии. Черепаха может выполнять две команды: Вперёд n (n – число) и Направо m (m – число). По команде Вперёд n Черепаха перемещается вперёд на n условных единиц. По команде Направо m Черепаха поворачивается на месте на m градусов по часовой стрелке, при этом соответственно меняется направление дальнейшего движения.
В начальный момент Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат).
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что заданная последовательность из S команд повторится k раз.
Черепаха выполнила следующую программу:
Повтори 3 [Вперёд 19 Направо 90 Вперёд 3 Направо 90]
Повтори 3 [Вперёд 5 Направо 90 Вперёд 11 Направо 90]
Полученный при выполнении этой программы рисунок можно рассматривать как набор непересекающихся прямоугольников. Определите наибольшее количество точек с целочисленными координатами, находящихся внутри одного из этих прямоугольников.
Точки, находящиеся на линиях, не учитывать.
Ответ: 28
Задание 7. Книгу объёмом 1,5 Мбайт записали как аудиокнигу. Запись велась в формате стерео (2 канала) с частотой 32 кГц и разрешением 16 бит. За одну минуту записывалось в среднем 1,5 Кбайт текста. Записанный аудиофайл сжали и разделили на 60 фрагментов со средним размером 25 Мбайт. Определите, на сколько процентов уменьшился размер файла при сжатии. Заголовки и другую служебную информацию не учитывать. В ответе запишите число округлённый до целого процент сжатия.
Ответ: 80
Задание 8. Сколько существует натуральных чисел, не превышающих 855 000 000, запись которых в системе счисления с основанием 15 содержит ровно 8 различных цифр?
Ответ: 69 189 120
Задание 9. В каждой строке электронной таблицы записаны восемь натуральных чисел, разбитых на две четвёрки. Первая четвёрка занимает столбцы с 1 по 4, вторая – с 5 по 8
Определите количество строк таблицы, для которых одновременно выполнены все следующие условия:
– максимальное число строки встречается в ней ровно один раз;
– максимальное число строки находится в первой четвёрке;
– среднее арифметическое чисел первой четвёрки меньше среднего арифметического чисел второй четвёрки.
Ответ: 1246
Задание 10. Повесть братьев Стругацких «Понедельник начинается в субботу» состоит из трёх историй. Один из персонажей носит фамилию Хунта. Определите, сколько раз встречается эта фамилия в любом падеже в каждой из историй.
В ответе запишите наибольшее из найденных чисел.
Ответ: 23
Задание 11. Предприятие выпускает партии изделий. Каждая партия получает уникальный код из 21 символа. Каждый символ кода может быть любой строчной или заглавной латинской буквой. Все изделия в партии получают последовательные номера от 1 до общего числа изделий в партии.
Запись о каждом изделии заносится в информационную систему. Запись содержит код изделия и некоторую дополнительную информацию.
Код изделия состоит из кода партии и номера изделия в партии. Для записи кода партии используется посимвольное кодирование, каждый символ кодируется одинаковым минимально возможным количеством битов. Номер изделия записывается как двоичное целое число, для записи каждого номера используется одинаковое минимально возможное количество битов. Для записи кода изделия в целом используется минимально возможное целое количество байтов.
Для записи дополнительной информации о каждом изделии требуется 60 байт.
Известно, что для хранения информации обо всех изделиях одной партии используется не более 80 Кбайт. Какое наибольшее количество изделий может быть в партии?
Ответ: 1050
Задание 12. Исполнитель Редактор получает на вход строку цифр и преобразует её.
Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 527150
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (111) ИЛИ нашлось (22)
заменить (111, 2)
заменить (222, 1)
заменить (221, 1)
заменить (122, 1)
заменить (22, 2)
КОНЕЦ ПОКА
КОНЕЦ
Определите, сколько различных строк, содержащих ровно 5 единиц, может получиться в результате применения этой программы к строкам, состоящим только из единиц и двоек.
Ответ: 32
Задание 13. В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места – нули.
Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.
Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.
Известно, что в двоичной записи адреса сети, к которой принадлежит узел 68.30.20.77, содержится столько же единиц, сколько нулей в двоичной записи маски этой сети.
Сколько адресов, в двоичной записи которых ровно 10 единиц, содержится в этой сети?
Ответ: 28
Задание 14. В системе счисления с основанием p выполняется равенство y27x + wy86 = xxz3y. Буквами x, y, z и w обозначены некоторые цифры из алфавита системы счисления с основанием p.
Определите значение числа xyzwp и запишите это значение в десятичной системе счисления.
Ответ: 2790
Задание 15. Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14&5 = 11102&01012 = 01002 = 4
Для какого наименьшего неотрицательного целого числа А формула
(x&5160 > 0 \/ x&3650 > 0) → (x&9545 = 0 → x&А > 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Ответ: 6690
16. Обозначим через a%b остаток от деления натурального числа a на натуральное число b, а через a//b – целую часть от деления a на b. Функция F(n), где n – неотрицательное целое число, задана следующими соотношениями:
F(n) = 0, если n = 0
F(n) = F(n//4) + n%4, если n>0 и n%4 < 2
F(n) = F(n//4) + n%4 – 1, если n%4 ≥ 2.
Найдите минимальное n, для которого F(n) = 27, а F(n + 1) = 16.
Ответ: 268 431 359
17. Файл содержит последовательность натуральных чисел, не превышающих 100 000. Назовём тройкой три идущих подряд элемента последовательности.
Определите количество троек, для которых выполняются следующие условия:
– в тройке есть четырёхзначные числа
– в тройке не более одного числа, у которого остаток от деления на 5 равен остатку от деления на 5 минимального элемента всей последовательности
– в тройке не менее двух чисел, у которых остаток от деления на 7 равен остатку от деления на 7 максимального элемента всей последовательности.
В ответе запишите два числа: сначала количество найденных троек, затем максимальную величину суммы элементов этих троек.
Ответ: 103 194 888
18. Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано число –1, в эти клетки роботу заходить нельзя. Для вашего удобства такие клетки выделены тёмным фоном. В остальных клетках записаны положительные числа.
За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз. Клетка, из которой робот не может сделать допустимого хода (справа и снизу находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток.
В начальный момент робот обладает некоторым запасом энергии. Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках.
Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом. Исходные данные записаны в электронной таблице. В ответе запишите два
числа: сначала ответ на задание 1, затем ответ на задание 2.
Ответ: 767,2002
19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. Если количество камней в куче делится на целое k (2 ≤ k ≤ 9), то игрок может убрать из кучи k камней. Если количество камней в куче не делится ни на одно
из указанных чисел, игрок убирает один камень, после чего выполняет ход по описанному выше правилу.
Например, если в куче 12 камней, то за один ход можно убрать 2, 3, 4 или 6 камней, а если в куче 11 камней, то игрок за один ход сначала убирает один камень (остаётся 10), а затем убирает 2 или 5 камней. Игра завершается, когда количество камней в куче становится не более 15. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 15 или меньше камней. В начале игры в куче было S камней, S > 15. Укажите минимальное значение S, при котором Петя не может выиграть первым ходом, но при любом первом ходе Пети Ваня может выиграть своим
первым ходом.
Ответ: 22
20. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани. В ответе запишите найденные значения в порядке возрастания.
Ответ: 24 30
21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволила бы ему гарантированно выиграть первым ходом.
Ответ: 26
22. В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или нескольких
других процессов – поставщиков данных. Если зависимый процесс получает данные от других процессов (поставщиков данных), то выполнение зависимого процесса не может начаться раньше завершения всех процессов- поставщиков. (сокращено)
Ответ: 32
23. Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены буквами.
A. Вычти 2
B. Если число кратно 3, Раздели на 3, Иначе Вычти 4
Программа для исполнителя – это последовательность команд.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы BAB при исходном числе 99 траектория будет состоять из чисел 33, 31, 27. Сколько существует программ, которые преобразуют исходное число 36 в число 4 и при этом траектория вычислений не содержит числа 16?
Ответ: 40
24. Текстовый файл содержит строку, состоящую из цифр от 1 до 9, знаков операций «+», «–» и «*» (сложение, вычитание и умножение) и заглавных латинских букв A, B, C, D.
Назовём правильной суммой строку, которая содержит последовательность из одного или более десятичных чисел, в которой между каждыми двумя соседними числами стоит ровно один знак «+» или «–» и нет других знаков. Примеры правильных сумм: «23», «115+6», «1980+12–123–51+3». Назовём результатом правильной суммы число, которое получится при выполнении записанных в соответствующей строке действий. Например, результат правильной суммы «2+3» – число 5, а результат правильной суммы
«1+2–8+3» – число –2. Найдите в данной строке расположенную непосредственно после буквы A
правильную сумму, содержащую наибольшее число символов, и вычислите её результат. Если несколько правильных сумм содержат одинаковое наибольшее число символов, выберите ту, которая имеет больший результат. В ответе запишите результат найденной суммы. Гарантируется, что ответ не превышает 2·109.
Ответ: 127
25. Маска числа – это последовательность цифр, в которой могут встречаться специальные символы «?» и «*». Символ «?» означает ровно одну произвольную цифру, символ «*» означает произвольную (в том числе пустую) последовательность цифр.
Например, маске 123*4?5 соответствуют числа 123405 и 12376415. Найдите все натуральные числа, не превышающие 109, которые соответствуют маске 4?5*07*3 и при этом без остатка делятся на 9341.
В ответе запишите все найденные числа в порядке возрастания.
Ответ: 495073
26. При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе
фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000).
Ответ: 20,58612
27. В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем
испытаниям. (сокращено)
Ответ: -10496, 10763