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

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

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдёт поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» — символ &.

Ниже в табличной форме представлен фрагмент базы данных о результатах тестирования учащихся (используется стобалльная шкала). Сколько записей в данном фрагменте удовлетворяют условию «Пол = ’м’ ИЛИ Химия > Биология»?

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

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

На вход алгоритма подаётся натуральное число $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.

Значения двух массивов $A[1..100]$ и $B[1..100]$ задаются с помощью следующего фрагмента программы:

Бейсик:
FOR n=1 TO 100
A(n)=n-10
NEXT n
FOR n=1 TO 100
B(n)=A(n)*n
NEXT n

Паскаль:
for n:=1 to 100 do
A[n]:=n-10;
for n:=1 to 100 do
B[n]:=A[n]*n

Алгоритмический язык:
нц для n от 1 до 100
A[n]=n-10
кц
нц для n от 1 до 100
B[n]=A[n]*n
кц

Сколько элементов массива $B$ будут иметь положительные значения?

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

Все пятибуквенные слова, составленные из букв С, Т, Р, О, К, А, записаны в алфавитном порядке и пронумерованы. Определите, под каким номером в этом списке стоит последнее слово с чётным номером, которое не начинается с букв А или К и содержит в своей записи ровно одну букву С. Слово — последовательность идущих подряд букв, не обязательно осмысленная.

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

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

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 115 символов и содержащий только десятичные цифры и символы из 2500-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.

Определите объём памяти (в Кбайт), необходимый для хранения сведений о 16 384 объектах.

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

Цикл «ПОКА условие последовательность команд КОНЕЦ ПОКА» выполняется, пока условие истинно. В конструкции «ЕСЛИ условие ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ» выполняется команда1, если условие истинно, и команда2 — если условие ложно.

Какая строка получится в результате применения программы к строке, состоящей из 84 идущих подряд цифр 1?

ПОКА нашлось (1111) ИЛИ нашлось (8888)
ЕСЛИ нашлось (1111)
ТО заменить (1111, 888)
ИНАЧЕ заменить (8888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

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

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

Для узла с IP-адресом 111.81.176.27 адрес сети равен 111.81.160.0. Чему равен третий слева байт маски?

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

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

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

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

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

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

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

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

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число $x$, этот алгоритм печатает два числа: $L$ и $M$. Укажите наибольшее число $x$, при вводе которого алгоритм выводит сначала $12$, а потом $3$.

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

Определите, какому столбцу таблицы соответствует каждая из переменных $w$, $x$, $y$, $z$.

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

Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна $k = 53$. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

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

Пример организации исходных данных во входном файле:
$7, 1, 3, 4, 43, 8, 5, 95$.

Для указанных входных данных при $k = 50$ искомая длина последовательности равна 2.

В ответе укажите два числа: значение длины искомой подпоследовательности сначала для файла А, затем для файла В.

Для обработки файла В не следует использовать переборный алгоритм для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

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

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

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

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

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

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

Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с элемента с номером $L$ и заканчивая элементом с номером $R$ включительно. Требуется найти подпоследовательность $S(L, R)$ максимальной длины, сумма элементов которой положительна и чётна. Гарантируется, что хотя бы одна такая подпоследовательность существует.

Даны два входных файла, файл A и файл B. В первой строке каждого файла содержится число $N$ ($5 \leq N \leq 10\,000\,000$), затем следуют $N$ целых чисел, каждое по модулю не превышает 1000. Для каждого файла определите длину искомой подпоследовательности. Типовой пример из условия является иллюстративным; используйте данные из приложенных файлов.