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

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

Символом $F$ обозначено одно из логических выражений от трёх аргументов: $X$, $Y$, $Z$. Дан фрагмент таблицы истинности выражения $F$. Какое выражение соответствует $F$?

В файле приведён фрагмент базы данных «Кондитерские изделия» о поставках конфет и печенья в магазины районов города. База данных состоит из трёх таблиц: «Движение товаров», «Товар» и «Магазин». Используя информацию из базы данных, определите, на сколько увеличилось количество упаковок конфет «Суфле в шоколаде», имеющихся в наличии в магазинах Центрального района, за период с 2 по 14 августа включительно.

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

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

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

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

1. Строится троичная запись числа $N$.
2. Если число $N$ делится на 3, то к этой записи дописываются две последние троичные цифры. Если число $N$ на 3 не делится, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конец числа. Полученная запись является троичной записью числа $R$.
3. Результат переводится в десятичную систему.

Например, для исходного числа $11_{10}=102_3$ результатом является число $102101_3=307_{10}$, а для исходного числа $12_{10}=110_3$ это число $11010_3=111_{10}$.

Укажите минимальное число $R$, большее 133, которое может быть получено с помощью описанного алгоритма.

Исполнитель Чертёжник перемещается на координатной плоскости. Команда «сместиться на $(a, b)$» перемещает его из точки $(x, y)$ в точку $(x+a, y+b)$, где $a$ и $b$ — целые числа. Чертёжнику был дан алгоритм: сначала сместиться на $(4, 6)$, затем $n$ раз выполнить команды «сместиться на $(a, b)$» и «сместиться на $(4, -6)$», после чего сместиться на $(-28, -22)$. Величины $a$, $b$ и число повторений $n$ неизвестны. В результате выполнения алгоритма Чертёжник возвращается в исходную точку. Найдите наибольшее возможное значение $n$.

Виталий фотографирует интересные места и события с помощью цифровой камеры своего смартфона. Каждая фотография представляет собой растровое изображение размером 1024×768 пикселей, при этом используется палитра из $2^{30}$ цветов. В конце дня Виталий отправляет снимки друзьям с помощью приложения-мессенджера. Для экономии трафика приложение оцифровывает снимки повторно, используя размер 800×600 пикселей и глубину цвета 28 бит. Сколько Кбайт трафика экономится при передаче 100 фотографий?

Все пятибуквенные слова, в составе которых могут быть только русские буквы Ц, И, Т, Р, У, С, записаны в алфавитном порядке и пронумерованы начиная с 1. Под каким номером в списке идёт последнее слово, которое содержит ровно одну букву И и не содержит букв У, стоящих рядом?

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

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

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 76 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 31 598 серийных номеров отведено не более 1894 Кбайт памяти. Определите максимально возможную мощность алфавита, используемого для записи серийных номеров.

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

Дана программа:

НАЧАЛО
ПОКА нашлось (19) ИЛИ нашлось (399) ИЛИ нашлось (999)
ЕСЛИ нашлось (19)
ТО заменить (19, 9)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (399)
ТО заменить (399, 91)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (999)
ТО заменить (999, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

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

В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла относится к адресу сети, а какая — к адресу самого узла. Маска записывается в виде четырёх байтов, причём в ней сначала стоят единицы, а затем нули. Адрес сети получается в результате применения поразрядной конъюнкции к IP-адресу узла и маске.

Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-адресом 119.134.58.57 адрес сети равен 119.134.48.0. Чему равно значение третьего слева байта маски?

Операнды арифметического выражения записаны в системе счисления с основанием 19:

$98x79731_{19} + 36x14_{19}$

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

Обозначим через $\mathrm{ДЕЛ}(n,m)$ утверждение «натуральное число $n$ делится без остатка на натуральное число $m$»; пусть на числовой прямой дан отрезок $B=[70;90]$. Для какого наибольшего натурального числа $A$ логическое выражение $\mathrm{ДЕЛ}(x,A) \mathbin{\lor} ((x \in B) \to \neg\mathrm{ДЕЛ}(x,22))$ истинно при любом целом положительном значении переменной $x$?

Ниже на пяти языках программирования записан рекурсивный алгоритм F. При вызове функции сначала выводится значение параметра n. Если n >= 4, затем выполняются вызовы F(n - 3) и F(n - 1) именно в указанном порядке. Запишите подряд без пробелов и разделителей все числа, которые будут выведены на экран при выполнении вызова F(6). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» — символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Какое количество страниц (в сотнях тысяч) будет найдено по запросу «Бабочка & Гусеница»? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.

Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке — это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.

Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. Исходные данные представлены в форме электронной таблицы размером $N \times N$, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.

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

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

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

Ниже на четырёх языках программирования записан один и тот же алгоритм. Получив на вход число $x$, алгоритм печатает два числа: $a$ и $b$. Найдите наименьшее число $x$, при вводе которого алгоритм печатает сначала $10$, а затем $7$.

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

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

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от −10 000 до 10 000 включительно. Гарантируется, что хотя бы один элемент массива делится нацело на 5. Опишите алгоритм, который находит максимум среди элементов массива, делящихся нацело на 5, а затем заменяет каждый элемент, делящийся нацело на 5, на найденный максимум. В качестве результата необходимо вывести изменённый массив, каждый элемент — с новой строки.

Например, для исходного массива из шести элементов 5, 7, 10, 25, 39, 15 программа должна вывести 25, 7, 25, 25, 39, 25.

В программе используются массив a из 30 элементов и целочисленные переменные i, j, k. Для Python исходные данные считываются следующим образом:
a = []
n = 30
for i in range(0, n):
a.append(int(input()))

Приведите фрагмент программы, который должен находиться на месте многоточия после ввода исходных данных. Можно использовать Python или другой язык программирования, указав его название и версию. Используйте только предложенные исходные данные и переменные.

Два игрока, Петя и Ваня, по очереди приписывают буквы к концу составляемого слова. Каждое промежуточное слово должно быть началом одного из заданных слов. Выигрывает тот, кто получает одно из заданных слов целиком. Первый ход делает Петя. Ни одно из заданных слов не является началом другого.

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

1а) Определите, у кого есть выигрышная стратегия при наборе слов {АБВГДАБВГДХ, ДГВБАДГВБА}. Опишите стратегию. Укажите количество различных партий при этой стратегии и конечное слово каждой партии.

1б) Определите, у кого есть выигрышная стратегия при наборе слов {ТРИ, повторённое 33 раза, РИТА, повторённое 44 раза}. Длина первого слова — 99 букв, длина второго — 176 букв. Опишите стратегию.

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

3) Для набора слов {ВОРОНА, ВОЛК, ВОЛНА, КРОНА, КРОШКА, КРОКОДИЛИЩЕ} определите игрока, у которого есть выигрышная стратегия. Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.

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

В первой строке входных данных задаётся количество чисел $N$ ($4 \le N \le 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее 10000.

В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 19.

Пример входных данных:
7
38
2
3
5
4
1
19

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

Из семи заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: $38 \cdot 4$, $38 \cdot 1$, $38 \cdot 19$, $2 \cdot 1$, $2 \cdot 19$, $3 \cdot 19$. Из них на 19 делятся 5 произведений.

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