Задания ЕГЭ

На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Г. В ответе запишите целое число  — так, как оно указано в таблице.

Миша заполнял таблицу истинности логической функции F:

(x ∧¬ y)∨(x ≡ z) ∨ w,

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z в том в ответе напишите буквы w, x, y, z том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Функция F задана выражением ¬ x ∨ y, зависящее от двух переменных, а фрагмент таблицы имеет следующий вид:

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б , Г , Е , И , М, Р , Т . Для передачи и спользуется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:

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

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Автомат обрабатывает натуральное число N по следующему алгоритму:

1.  Строится троичная запись числа N.

2.  В конец записи (справа) дописывается остаток от деления числа N на 3.

3.  Результат переводится из троичной системы в десятичную и выводится на экран.

Пример. Дано число N  =  11. Алгоритм работает следующим образом:

1.  Троичная запись числа N: 102.

2.  Остаток от деления 11 на 3 равен 2, новая запись 1022.

3.  На экран выводится число 35.

Какое наименьшее четырёхзначное число может появиться на экране в результате работы автомата?

Изображение было отсканировано с разрешением 200 dpi, а затем сохранено со сжатием на 25%. Размер полученного файла составил 15 Мбайт. Затем то же изображение было отсканировано с разрешением 300 dpi и сохранено со сжатием на 40%. Определите размер нового файла. В ответе запишите только число  — размер файла в Мбайтах.

Полина составляет коды из букв слова ПОЛИНА. Код должен состоять из 8 букв, любую букву можно использовать произвольное число раз или не использовать вовсе. Полина хочет, чтобы согласных в каждом коде было больше, чем гласных. Сколько кодов, удовлетворяющих этому условию, она сможет составить?

Каждый объект, зарегистрированный в информационной системе, получает уникальный код, состоящий из двух частей. Первая часть определяет категорию объекта и состоит из 5 символов, каждый из которых может быть одной из 26 заглавных латинских букв. Вторая часть кода определяет уникальный идентификатор объекта и состоит из 9 символов, каждый из которых может быть латинской буквой (строчной или заглавной) или одной из 9 цифр (цифра 0 не используется). Для представления кода используют посимвольное кодирование, все символы в пределах одной части кода кодируют одинаковым минимально возможным для данной части количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Кроме того, для каждого объекта в системе выделено 120 байт для хранения содержательной информации.

Сколько байтов потребуется для хранения данных (код и содержательная информация) о 20 объектах? В ответе запишите только целое число  — количество байтов.

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

А)  заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

заменить (111, 27)

преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б)  нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка

исполнителя при этом не изменяется.

Цикл

    ПОКА условие

        последовательность команд

    КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкции

    ЕСЛИ условие

        ТО команда1

    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно).

В конструкции

    ЕСЛИ условие

        ТО команда1

        ИНАЧЕ команда2

    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора:

НАЧАЛО

ПОКА нашлось (111)

    заменить (111, 2)

    заменить (222, 11)

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке, состоящей из 78 единиц?

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

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

Узлы с IP-адресами 98.162.71.150 и 98.162.71.140 находятся в одной сети. Чему равно наибольшее количество возможных единиц в маске этой сети?

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

4Cx4₁₅ + x62A₁₃

Для какого наибольшего целого неотрицательного числа A выражение

(x > A) ∨ (y > x) ∨ (2y + x < 110)

тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных x и y?

Алгоритм вычисления значения функции F(n), где n  — целое число, задан следующими соотношениями:

если

если

Определите количество значений n, не превышающих 3⁴⁰, для которых

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 36 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 35.

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Две логические функции заданы выражениями:

F₁  =  (x → y)≡(w ∨ ¬ z)

F₂  =  (x → y)∧(¬w≡z)

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

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала  — буква, соответствующая первому столбцу; затем  — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Г  — 11, И  — 000, К  — 1011, Р  — 001. Известно также, что код слова ГРАММАТИКА содержит 29 двоичных знаков. Укажите возможный код минимальной длины для буквы М. Если таких кодов несколько, укажите тот из них, который имеет минимальное числовое значение.

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n  — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, и Направо m (где m  — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись

Повтори k [Команда1 Команда2 … КомандаS]

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

Повтори 5 [Вперёд 9 Направо 90 Вперёд 3 Направо 90]

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

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и

его движения. У исполнителя существует две команды: Вперёд n (где n  — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, и Направо m (где m  — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись

Повтори k [Команда1 Команда2 … КомандаS]

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

Повтори 5 [Вперёд 9 Направо 120]

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

Автоматическая фотокамера с 400 Кбайт видеопамяти производит растровые изображения c фиксированным разрешением и 16-цветной палитрой. Сколько цветов можно будет использовать в палитре, если увеличить видеопамять до 800 Кбайт?

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * F(n–1) − F(n–1) * n + 2 * n, при n >1

Чему равно значение функции F(4)?

В ответе запишите только натуральное число.