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

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами A и F, если передвигаться можно только по построенным дорогам.

Миша заполнял таблицу истинности логической функции $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$.

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите ID женщины, ставшей матерью в наиболее молодом возрасте. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.

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

Напишите число, которое будет выведено в результате выполнения алгоритма. Алгоритм перебирает целые значения $t$ от $-20$ до $20$ и сохраняет значение $M$, при котором функция принимает наименьшее найденное значение.

Лена записывает голосовое сообщение для своей подруги. Перед отправкой сообщение оцифровывается в формате стерео с частотой дискретизации 32 000 Гц и глубиной кодирования 8 бит. Определите наименьшее количество Кбайт, необходимое для сохранения сообщения в памяти без учёта заголовка, если его длительность — 2 минуты 36 секунд.

Все 3-буквенные слова, составленные из букв Е, И, К, Н, У, Ч, записаны в алфавитном порядке и пронумерованы, начиная с 1. Под каким номером в списке идёт первое слово, которое начинается с буквы Н?

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

С помощью текстового редактора определите, сколько раз встречается сочетание букв «след» или «След» в составе других слов, но не как отдельное слово, в тексте глав IX и X романа И. С. Тургенева «Отцы и дети».

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, то есть 26 различных символов. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей: все символы кодируют одинаковым и минимально возможным количеством бит. Кроме пароля, для каждого пользователя хранятся дополнительные сведения, для чего отведено 15 байт на одного пользователя. Определите объём памяти в байтах, необходимый для хранения сведений о 50 пользователях.

Исполнитель Редактор получает на вход строку цифр. К строке, состоящей из 109 идущих подряд цифр 7, применяют программу: пока в строке встречается $33333$ или $777$, если встречается $33333$, первое слева вхождение $33333$ заменяется на $7$, иначе первое слева вхождение $777$ заменяется на $3$. Какая строка получится в результате?

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

Для узла с IP-адресом 117.191.208.37 адрес сети равен 117.191.192.0. Чему равно наименьшее возможное значение третьего слева байта маски? Ответ запишите в виде десятичного числа.

Значение арифметического выражения $25^{18} \times 5^{10} - 5^6 - 25$ записали в системе счисления с основанием 5. Сколько цифр 4 содержится в этой записи?

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

Алгоритм вычисления функции $F(n)$, где $n$ — целое число, задан следующими соотношениями: $F(n)=n$ при $n<10$; $F(n)=n-1+F(n-1)$ при $n\geqslant 10$. Чему равно значение выражения $F(8567)-F(8563)$?

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

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

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

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

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

В прилагаемом файле содержится таблица с информацией о совокупности $N$ вычислительных процессов. Для каждого процесса указаны его идентификатор, время выполнения в миллисекундах и идентификаторы процессов, от которых он зависит. Если процесс независимый, указано значение 0. Приостановка выполнения процессов не допускается.

Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_6, y_1, y_2, \ldots, y_6$, удовлетворяющих условиям: для каждого $i=1,2,\ldots,5$ выполняется $((x_i \equiv y_i) \to (x_{i+1} \equiv y_{i+1})) \land (x_i \lor y_i)=1$, а также $x_6 \lor y_6=1$?

Требовалось написать программу, которая решает уравнение $ax+b=0$ относительно $x$ для любых действительных чисел $a$ и $b$, введённых с клавиатуры. Программист написал программу неправильно. Во всех трёх вариантах программы вводятся числа $a$, $b$ и $x$, затем сначала проверяется условие $b=0$, а при $b\ne0$ — условие $a=0$.

Назовём маской числа последовательность цифр, в которой символ «?» означает ровно одну произвольную цифру, а символ «*» — любую последовательность цифр произвольной длины, включая пустую. Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих $10^8$, найдите все числа, соответствующие маске 1234*67 и делящиеся на 19 без остатка. Запишите найденные числа в порядке возрастания, а рядом с каждым числом — результат его деления на 19. Количество строк для ответа избыточно.

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

Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на $p=33$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар нет, нужно вывести два нуля.

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

Напишите эффективную по времени и памяти программу для решения задачи. Эффективная по времени программа должна работать за время, не превышающее линейное относительно $N$. Эффективная по памяти программа должна использовать не более $1$ Кбайт памяти, причём объём памяти не должен увеличиваться с ростом $N$.

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