OpenFIPI 2.0

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

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

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

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

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

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

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

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

Цикл

ПОКА  условие 

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

КОНЕЦ ПОКА

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

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

ЕСЛИ  условие

     ТО команда1

КОНЕЦ ЕСЛИ

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

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

ЕСЛИ  условие

     ТО команда1

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

КОНЕЦ ЕСЛИ

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

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 101 идущих подряд цифр 1? В ответе запишите полученную строку.

НАЧАЛО

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

         ЕСЛИ  нашлось (111) 

              ТО заменить (111, 88)

         ИНАЧЕ

             ЕСЛИ  нашлось (88888) 

                 ТО заменить (88888, 8)

             КОНЕЦ ЕСЛИ

         КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и F на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1; для буквы Б  кодовое слово 01. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?

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

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

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

2)    К этой записи дописываются справа ещё два разряда по следующему правилу: если N нечётное, в конец числа (справа) дописывается сначала ноль, а затем единица.  В противном случае, если N чётное, справа дописывается сначала единица, а затем ноль.

Например, двоичная запись 1001 числа 9 будет преобразована в 100101, а двоичная запись 1100 числа  12 будет преобразована в 110010. 

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R – результата работы данного алгоритма.

Укажите минимальное число R, которое больше 74 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

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

(69 ≠ y + 2x)  \/ (A < x) \/ (A < y)

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

Значение арифметического выражения 9¹⁹ + 3⁵⁷  – 9 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А, причём в каждом слове есть ровно одна гласная буква и она встречается ровно 1 раз. Каждая из допустимых согласных букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Исполнитель Вычислитель преобразует число, записанное на экране.

У исполнителя есть три команды, которым присвоены номера:

1.    Прибавить 1

2.    Умножить на 2

3.    Прибавить 3

Первая из них увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает его на 3.

Программа для Вычислителя  это последовательность команд.

Сколько существует таких программ, которые преобразуют исходное число 3 в число 15 и при этом траектория вычислений программы содержит число 10?

Траектория вычислений программы  это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 11, 22.

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

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