Информатика · ЕГЭ

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт В.

Миша заполнял таблицу истинности логической функции $F = ((x \equiv \neg y) \to \neg(z \to x)) \lor \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, не указав, какому столбцу таблицы соответствует каждая из переменных $w$, $x$, $y$, $z$.

В первой строке первые два значения переменных равны $0$ и $0$, а значение функции равно $0$. Во второй строке третье и четвёртое значения переменных равны $0$ и $0$, а значение функции равно $0$. В третьей строке первое значение переменной равно $1$, а значение функции равно $0$.

В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц: «Движение товаров», «Товар» и «Магазин». Используя информацию из базы данных, определите общий вес (в кг) крахмала картофельного, поступившего в магазины Заречного района за период с 1 по 8 июня 2021 года включительно.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали кодовые слова 100, 101, 00, 01 соответственно. Для двух оставшихся букв — Д и Е — коды неизвестны. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Строится двоичная запись числа $N$. К этой записи справа дописываются два разряда: сначала остаток от деления суммы цифр двоичной записи на 2, затем остаток от деления суммы цифр полученной записи на 2. Полученная запись переводится в десятичную систему счисления. Укажите наименьшее число $N$, для которого результат работы алгоритма больше числа 253.

Запишите число, которое будет напечатано в результате выполнения следующей программы. Программа представлена на пяти языках программирования.

Для хранения растрового изображения размером $240 \times 2048$ пикселей отведено не более $404$ Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в палитре изображения?

Все 5-буквенные слова, составленные из букв К, М, Р, записаны в алфавитном порядке. Под каким номером стоит слово РРРМР?

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

С помощью текстового редактора определите, сколько раз встречается отдельное слово «все» или «Все» в тексте главы III повести А.И. Куприна «Поединок». Другие формы этого слова учитывать не следует.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только цифры и буквы У, Ч, И, Т, Е, Л, Ь. Таким образом, используется 17 различных символов. Каждый пароль записывается минимально возможным и одинаковым целым количеством байт: используется посимвольное кодирование, а все символы кодируются одинаковым и минимально возможным количеством бит. Определите объём памяти, отводимый системой для записи 80 паролей.

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки цифр $v$ на цепочку $w$. Если в строке нет вхождений цепочки $v$, строка не изменяется. Команда «нашлось (v)» проверяет наличие цепочки $v$ в строке, не изменяя её. Цикл выполняется, пока условие истинно.

Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (73) ИЛИ нашлось (322) ИЛИ нашлось (2222)
ЕСЛИ нашлось (73)
ТО заменить (73, 2)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (322)
ТО заменить (322, 27)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (2222)
ТО заменить (2222, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход программе поступает строка, начинающаяся с цифры «7», а затем содержащая $n$ цифр «2», где $3 < n < 10\,000$. Определите наименьшее значение $n$, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 15.

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

Значение арифметического выражения $9^{11} \times 3^{20} - 3^9 - 27$ записали в системе счисления с основанием 3. Сколько цифр $2$ содержится в этой записи?

Для какого числа $X$ истинно высказывание: $((X > 2) \lor (X < 2)) \to (X > 4)$?

Алгоритм вычисления функций $F(n)$ и $G(n)$, где $n$ — целое число, задан следующими соотношениями: $F(n)=2\cdot(G(n-3)+8)$; $G(n)=2\cdot n$, если $n<10$; $G(n)=G(n-2)+1$, если $n\geq 10$. Чему равно значение выражения $F(15548)$?

Текст романа М. А. Булгакова «Собачье сердце» представлен в виде файлов различных форматов. Откройте один из файлов и определите, сколько раз встречаются в тексте слова с сочетанием букв «род», например «народ», «пригород». Отдельные слова «род» и «Род» учитывать не следует.

Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо или вниз. Посетив клетку, Робот забирает монету с собой. Внутренние и внешние стены обозначены утолщёнными линиями; сквозь стену Робот пройти не может. В клетках, ограниченных справа и снизу стенами, движение прекращается, и накопленная сумма считается итоговой. Определите максимальную и минимальную денежные суммы среди всех возможных маршрутов.

В игре с кучей камней за один ход можно добавить 1 или 4 камня либо увеличить количество камней в 3 раза. Игра заканчивается, когда в куче становится не менее 91 камня. Найдите такое начальное количество камней $S$, при котором Петя не может выиграть первым ходом, но после любого хода Пети Ваня может выиграть своим первым ходом.

Для игры, описанной в задании 19, найдите два таких минимальных значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: Петя не может выиграть за один ход; Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Для игры, описанной в задании 19, найдите минимальное значение $S$, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, а стратегии, позволяющей ему гарантированно выиграть первым ходом, нет.

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит число $R$: к двоичной записи числа $N$ дважды справа дописывается остаток от деления суммы её цифр на $2$. Укажите наименьшее число $N$, для которого результат работы алгоритма больше $100$. Ответ запишите в десятичной системе счисления.

Миша заполнял таблицу истинности логической функции $F = \neg(x \to z) \lor (y \equiv w) \lor y$, но успел заполнить лишь фрагмент из трёх различных строк, не указав, какому столбцу таблицы соответствует каждая из переменных $w$, $x$, $y$, $z$. Определите соответствие переменных столбцам.

На обработку поступает натуральное число, не превышающее $10^9$. Нужно написать программу, которая выводит на экран минимальную цифру числа, делящуюся на 3. Если в числе нет цифр, делящихся на 3, на экран требуется вывести «NO». Напоминание: 0 делится на любое натуральное число.

Программа на языке Python:

N = int(input())
minDigit = 9
while N > 0:
digit = N % 10
if digit % 3 == 0:
if digit < minDigit:
digit = minDigit
N = N // 10
if minDigit <= 9:
print(minDigit)
else:
print("NO")

Последовательно выполните следующие действия:
1. Напишите, что выведет эта программа при вводе числа 143.
2. Приведите пример такого трёхзначного числа, при вводе которого программа выдаёт верный ответ.
3. Найдите все ошибки в этой программе. Известно, что каждая ошибка затрагивает только одну строку и может быть исправлена без изменения других строк. Для каждой ошибки выпишите строку, в которой сделана ошибка, и приведите правильный вариант этой строки. Исправление должно затрагивать только строку, в которой находится ошибка.

Напишите программу, которая перебирает целые числа, большие 1 481 011, в порядке возрастания и ищет среди них представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно одну цифру 7.

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

Количество строк в таблице для ответа избыточно.

Каждый кандидат в отряд космонавтов проходит 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме того, можно получить дополнительно от 0 до 10 баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) — натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке выше стоит участник с большими баллами за собеседование, а при равенстве и этих баллов — с меньшим ID.

Минимальная сумма баллов, с которой зачисляются в отряд все её набравшие, называется проходным баллом. Гарантируется, что всегда есть участники, набравшие проходной балл.

Если после зачисления всех кандидатов с проходным баллом в отряде остались места, на которые претендуют несколько кандидатов с одинаковой суммой баллов, то такая сумма баллов называется полупроходным баллом, в противном случае полупроходной балл отсутствует.

Входные данные находятся в прилагаемом файле. В первой строке записаны числа N и K: количество кандидатов и количество мест в отряде. В следующих N строках находятся ID кандидата и четыре числа: результаты трёх испытаний и результат собеседования.

Определите ID кандидата, который последним из рейтингового списка набрал проходной балл, и количество кандидатов, набравших полупроходной балл.

На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на $14$.

В первой строке входных данных задаётся количество чисел $N$ ($1 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10\,000$. Программа должна вывести количество пар, в которых произведение элементов кратно $14$.

Пример входных данных:
4
2
6
7
21

Пример выходных данных:
4

Требуется написать эффективную по времени и по памяти программу. Алгоритм должен работать за время $O(N)$, а используемая память не должна зависеть от $N$ и не должна превышать 1 килобайт. Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.