Подготовка

Подготовка 3

Задание №4
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова, представленные в таблице.
Укажите кратчайшее кодовое слово для буквы Е, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Fill in the Blanks

Ответ

Задание №4
По каналу связи передаются сообщения, содержащие только буквы из набора: А, В, Е, Т, М, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Т – 00, М – 010. Для четырех оставшихся букв А, Н, В и Е кодовые слова неизвестны. Какое количество двоичных знаков требуется для кодирования слова АНТЕННА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Fill in the Blanks

Ответ

Задание №5
На вход алгоритма подаётся неотрицательное число N. Алгоритм строит по нему новое число R следующим образом.

1) Число переводится в четверичную систему счисления.
2) Полученная запись преобразуется по следующему алгоритму:
  а) если число чётное, то слева дописывается 12, а справа – утроенное значение младшего разряда четверичной записи в четверичной системе счисления;
  б) если число нечётное, то слева дописывается 13, а справа – 21.

Полученная таким образом запись является четверичной записью искомого числа R. Укажите минимальное значение большее 50, которое может являться результатом работы автомата.

Fill in the Blanks

Ответ

Задание №7
Виталий делает снимки интересных мест и событий цифровой камерой своего смартфона. Каждая фотография представляет собой растровое изображение размером 1920×1080 пикселей и с палитрой из 2²⁴ цветов. В конце дня Виталий отправляет снимки друзьям с помощью приложения-мессенджера. Для экономии трафика приложение сжимает снимки, используя размер 1280×1024 пикселей и глубину цвета 23 бита. Сколько Кбайт трафика экономится таким образом при передаче 120 фотографий? В ответе укажите целую часть полученного числа.

Fill in the Blanks

Ответ

Задание №7
Фотограф делает цветные фотографии размером 3840×2160 пикселей, используя палитру из 2²⁴ цветов. Для сохранения снимков фотограф использует сменные карты памяти, каждая из которых вмещает не более 8 Гбайт данных. Когда на карте остаётся недостаточно места для записи новой фотографии, фотограф заменяет карту на следующую свободную. Известно, что фотограф сделал 5922 снимка. Какое минимальное количество карт понадобится фотографу? В ответе запишите целое число.

Fill in the Blanks

Ответ

Задание №8
Все пятибуквенные слова, составленные из букв Л, И, С, Ё, Н, О, К, записаны в алфавитном порядке и пронумерованы начиная с 1. Начало списка выглядит так:

1. ЁЁЁЁЁ
2. ЁЁЁЁИ
3. ЁЁЁЁК
4. ЁЁЁЁЛ
5. ЁЁЁЁН
6. ЁЁЁЁО
7. ЁЁЁЁС
...

Под каким номером стоит последнее слово, в котором буква Ё встречается не менее двух раз, буква О не стоит в начале слова, а вторая с начала буква – К?

Fill in the Blanks

Ответ

Задание №9 В файле электронной таблицы в каждой строке записаны четыре натуральных числа. Определите количество строк таблицы, для которых выполнены следующие условия:
– только одно число встречается в строке дважды;
– сумма двух самых больших чисел строки более чем в два раза больше суммы двух самых малых;
– максимальное число строки не кратно минимальному.
В ответе запишите только число.

Fill in the Blanks

Ответ

Задание №10 файле приведен текст второго тома романа «Война и мир» Л. Толстого. Определите, сколько раз встречается в тексте глав XII и XIV третьей части сочетание букв «по» или «По» только в составе других слов, в том числе в сложных словах, соединённых дефисом, но не как отдельное слово. В ответе укажите только число.

Fill in the Blanks

Ответ

Задание №11
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 119 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что 125 300 серийных номеров занимают более 23 Мбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Fill in the Blanks

Ответ

Задание №11
На складе каждой упаковке товара присваивают уникальный идентификатор, который может содержать десятичные цифры, 26 латинских букв (без учёта регистра) и символы из 476-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 5000 идентификаторов отведено не более 1 Мбайт памяти. Определите максимально возможную длину идентификатора. В ответе запишите только целое число.

Fill in the Blanks

Ответ

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

ПОКА нашлось (27) ИЛИ нашлось (777) ИЛИ нашлось (377)
ЕСЛИ нашлось (27)
ТО заменить (27, 7)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (777)
ТО заменить (777, 3)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (377)
ТО заменить (377, 72)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

На вход приведённой выше программе поступает строка, начинающаяся с цифры «2», а затем содержащая n цифр «7» (3 < n < 10000). Определите наибольшее возможное значение n такое, что произведение числовых значений цифр получившейся строки кратно 3 и оканчивается на 1.

Fill in the Blanks

Ответ

Задание №13
В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Узлы с IP-адресами 113.188.14.51 и 113.188.6.86 принадлежат одной сети. Какое наименьшее количество IP-адресов, в двоичной записи которых ровно 17 единиц, может содержаться в этой сети?

Fill in the Blanks

Ответ

Задание №13
В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Широковещательным адресом называется специализированный адрес, в котором все младшие биты, соответствующие нулям в маске, равны 1. Сеть задана IP-адресом одного из входящих в неё узлов 123.215.104.78 и сетевой маской 255.255.252.0. Найдите наибольший IP-адрес в данной сети, который может быть назначен компьютеру. В ответе укажите найденный IP-адрес без разделителей. Например, если бы найденный адрес был равен 111.22.3.44, то в ответе следовало бы записать 11122344.

Fill in the Blanks

Ответ

Задание №14
Операнды арифметического выражения

11353x12₂₅ + 135x21₂₅

записаны в системе счисления с основанием 25. В записи чисел переменной x обозначена неизвестная цифра из алфавита 25-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 24. Для найденного x вычислите частное от деления значения арифметического выражения на 24 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.

Fill in the Blanks

Ответ

Задание №14
Значение арифметического выражения 5²⁰²⁵ + 5⁴⁰⁰ – х, где х – натуральное число в диапазоне от 10 до 70000, записали в системе счисления с основанием 5. Определите максимальное значение x, при котором данная запись содержит наибольшее количество цифр «4».

Fill in the Blanks

Ответ

Задание №15
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Пусть на числовой прямой дан отрезок В = [70, 90]. Для какого наибольшего натурального числа А логическое выражение

ДЕЛ(х, А) ∨ ((х ∈ В) → ¬ДЕЛ(х, 22))

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

Fill in the Blanks

Ответ

Задание №17 В файле содержится последовательность целых чисел, не превышающих по модулю 100 000. Определите количество троек элементов последовательности, в которых произведение максимального и минимального элементов тройки больше суммы всех отрицательных элементов последовательности. В ответе запишите количество найденных троек, затем абсолютное значение максимальной из сумм элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

Fill in the Blanks

Ответ

Задание №18 Исполнитель Робот стоит в левом верхнем углу поля, разлинованного на клетки. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.

Fill in the Blanks

Ответ

Задание №23
У исполнителя имеются три команды, которые обозначены латинскими буквами:

A. Вычти 1
B. Вычти 6
C. Найди целую часть от деления на 2

Первая команда уменьшает число на экране на 1, вторая команда уменьшает это число на 6, третья команда делит число нацело на 2. Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 34 преобразуют в число 6, и при этом траектория вычислений содержит числа 19 и 29 и не содержит числа 24?

Fill in the Blanks

Ответ

Задание №23
У исполнителя имеются две команды, которые обозначены латинскими буквами:

A. Вычти 2
B. Если число чётное, раздели на 2, иначе вычти 3

Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 55 в число 3 и при этом траектория вычислений не содержит число 18?

Fill in the Blanks

Ответ

Задание №25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Среди натуральных чисел, не превышающих 10⁹, найдите все числа, соответствующие маске 6323*353?, делящиеся на 28 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 28.

Задание №25
632303532 22582269
632363536 22584412
632373532 22584769

Задание №19-21
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень, добавить три камня или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 174. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах оказывается 174 или больше камней. В начальный момент в первой куче было 19 камней, во второй куче – S камней; 1 ≤ S ≤ 154.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
  Вопрос 1. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.
  Вопрос 2. Найдите два наименьших значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
  Вопрос 3. Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Задание №19-21
1) 39
2) 74 76
3) 75

Задание №25
Пусть R – сумма всех различных натуральных делителей целого числа. Например, для числа 20 имеем R = 1 + 2 + 4 + 5 + 10 + 20 = 42. Напишите программу, которая перебирает целые числа, бо́льшие 500 000, в порядке возрастания и ищет среди них такие, для которых значение R оканчивается на цифру 6. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – пять соответствующих этим числам значений R.

Задание №25
500032 1070356
500035 606816
500039 501456
500050 949716
500052 1333696

Задание №24 Текстовый файл состоит не более чем из 4×10⁶ символов и содержит только символы F, G, Q, R, S и W. Определите в этом файле максимальное количество идущих подряд символов, среди которых подстрока FSRQ встречается ровно 80 раз.

Fill in the Blanks

Ответ

Задание №24 Текстовый файл состоит не более чем из 10⁶ символов и содержит только десятичные цифры и заглавные буквы латинского алфавита. Определите в этом файле последовательность идущих подряд символов, представляющих собой 12-ричную запись максимального нечётного числа. В ответе запишите индекс (номер) первого символа (первой значащей цифры), с которого начинается запись этого числа в прилагаемом файле. Нумерация символов в текстовом файле начинается с нуля.

Fill in the Blanks

Ответ

Задание №26 Участники викторины отвечают на 10 вопросов, сложность которых оценивается числом от 10 до 100. При удачном ответе на вопрос стоимостью Q участник получает Q баллов, при неправильном ответе на такой вопрос он получает Q штрафных баллов, которые вычитаются из результата. Участник может не отвечать на какие-то вопросы, при этом его сумма баллов не изменяется. Чтобы определить победителей, для каждого участника вычисляются три показателя:
  1) сумма – сумма набранных баллов;
  2) штрафы – сумма штрафных баллов за неправильные ответы;
  3) пропуски – количество вопросов, на которые участник вообще не отвечал.
В таблице результатов участники располагаются по убыванию суммы, при равенстве сумм – по возрастанию штрафов, при равенстве сумм и штрафов – по возрастанию пропусков. При равенстве всех трёх показателей участники располагаются в итоговой таблице в порядке возрастания их личных номеров. Победителями считаются участники, занявшие места в первой четверти
итоговой таблицы, а также те, у которых все три показателя такие же, как у занявшего последнее место в первой четверти таблицы. Определите личный код участника, показавшего лучший результат среди тех, кто не стал победителем викторины, а также количество участников, у которых все три показателя такие же, как у участника, занявшего в итоговой таблице 1000 место (включая самого этого участника).
Входные данные представлены в файле 26-156.txt следующим образом. В первой строке входного файла записано натуральное число N, не превышающее 10 000 — количество участников викторины. Вторая строка содержит 10 чисел, разделённых пробелом: «стоимости вопросов». В каждой из следующих N строках через пробел записаны через пробел 11 чисел: сначала код участника, а затем 10 чисел, характеризующих ответы этого участника на вопросы (1, если ответ верный; -1, если ответ неверный и 0, если участник не отвечал на вопрос).
Запишите в ответе два числа: сначала личный код участника, показавшего лучший результат среди тех, кто не стал победителем викторины, а затем количество участников, у которых все три показателя такие же, как у участника, занявшего в итоговой таблице 1000 место (включая самого этого участника).

Fill in the Blanks

Ответ

Задание №27

А В

Задание №27

А В

​208364 305606
544492 600793