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

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

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

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

По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 000, 010, 100, 1110 соответственно.

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

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

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Сначала строится двоичная запись числа $N$. Если число $N$ делится на 3, к этой записи дописываются три последние двоичные цифры. Если число $N$ на 3 не делится, остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа. Полученная запись является двоичной записью числа $R$, после чего результат переводится в десятичную систему. Например, для исходного числа $12_{10}=1100_2$ результатом является число $1100100_2=100_{10}$, а для исходного числа $4_{10}=100_2$ — число $10011_2=19_{10}$. Укажите минимальное число $N$, после обработки которого получается число $R$, не меньшее 200.

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

Сколько секунд потребуется обычному модему, передающему сообщения со скоростью 12 800 бит/с, чтобы передать цветное растровое изображение размером 1024 на 600 пикселей, при условии, что цвет каждого пикселя кодируется 2 байтами?

Сколько существует десятичных пятизначных чисел, не содержащих в своей записи цифру 5, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?

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

С помощью текстового редактора определите, сколько раз встречается отдельное слово «вот» или «Вот» в тексте глав III, IV и V романа И. С. Тургенева «Отцы и дети». В ответе укажите только число.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственного пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 24 байт на одного пользователя. Определите объём памяти в байтах, необходимый для хранения данных о 40 пользователях.

На ленте в соседних ячейках записано двоичное представление числа 2027 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Определите результат выполнения программы. Получившееся число запишите в десятичной системе счисления.

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

Сколько существует различных путей из города А в город М, проходящих через город В?

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

Какое логическое выражение равносильно выражению $\neg(\neg A \lor B) \lor \neg C$?

Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n=1$; $F(n)=n\times F(n-1)$, если $n>1$. Чему равно значение выражения $\dfrac{F(3238)/2+F(3237)}{F(3236)}$?

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

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

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

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

Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход игрок может добавить в кучу 1 или 3 камня либо увеличить количество камней в куче в 2 раза. Игра завершается, когда количество камней становится не менее 435. Побеждает игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, $1 \leq S \leq 434$. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.

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

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

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

Для какого наибольшего целого неотрицательного числа $A$ выражение $(y + 3x > A) \lor (x < 20) \lor (y < 20)$ тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных $x$ и $y$?

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

В программе используется одномерный целочисленный массив $A$ с индексами от $0$ до $10$. Фрагмент программы выполняет следующие действия: $s := 0$, $n := 10$; для $i$ от $0$ до $n-1$ вычисляется $s := s + A[i] - A[i+1]$. В начале выполнения фрагмента в массиве находились числа $10, 8, 7, 6, 5, 4, 3, 2, 9, 0, 1$, то есть $A[0] = 10$, $A[1] = 8$ и так далее. Чему будет равно значение переменной $s$ после выполнения фрагмента программы?

Входной файл содержит информацию о заявках граждан, обращающихся в многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом в минутах от начала суток. Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с 1. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит. Определите, сколько граждан смогут попасть на приём в МФЦ в течение 24 часов, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.

В первой строке входного файла находится натуральное число K, не превышающее 1000, — количество окон в МФЦ. Во второй строке находится натуральное число N (N ≤ 10 000), обозначающее количество граждан. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: время начала и время окончания приёма в минутах от начала суток.

Для выполнения задания используйте данные из прилагаемого файла.

Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле $d(A,B)=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$.

В файле А хранятся координаты точек двух кластеров, где $H=6$ и $W=4{,}5$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Известно, что количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где $H=6$, $W=5$ для каждого кластера. Известно, что количество точек не превышает 10\,000. Структура хранения информации в файле Б аналогична структуре в файле А.

Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: $P_x$ — минимальную из абсцисс центров кластеров и $P_y$ — минимальную из ординат центров кластеров.

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: $Q_1$ — расстояние между центрами кластеров с минимальным и максимальным количеством точек и $Q_2$ — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

Используйте данные из прилагаемых файлов. В ответе запишите четыре числа: в первой строке — сначала абсолютную величину целой части произведения $P_x\times10\,000$, затем абсолютную величину целой части произведения $P_y\times10\,000$; во второй строке — сначала целую часть произведения $Q_1\times10\,000$, затем целую часть произведения $Q_2\times10\,000$.