Периодическая дробь

Задача №1 3 балла

[Периодическая дробь]
Дано число A, запись которого в одиннадцатеричной системе счисления является бесконечной периодической дробью: 0,(51)11. На какое минимальное целое положительное число B нужно умножить число A, чтобы в результате получилось целое положительное число. В ответе запишите число B в десятичной системе счисления. Ваш ответ: 3

Задача №2 3 балла

[Палиндромы]
Снусмумрику очень нравятся красивые числа. Больше всего его привлекают числа-палиндромы, то есть такие числа, которые читаются одинаково слева направо и справа налево. Например, число 122110 и число C4C16 будут палиндромами. Недавно Снусмумрик обнаружил, что существуют числа, запись которых сразу в нескольких позиционных системах счисления будет палиндромом. Пока он нашел один такой пример: шестнадцатеричное число F6F16 в восьмеричной системе будет записываться как 75578, то есть запись этого числа является палиндромом и в шестнадцатеричной, и в восьмеричной системе счисления. Снусмумрик решил поэкспериментировать и с другими позиционными системами счисления. Помогите ему в этом и определите, сколько существует целых положительных чисел, таких, что их запись будет палиндромом и в троичной, и в девятеричной системе счисления, причем в девятеричной системе счисления будет содержать ровно 5 значащих разрядов. В ответе укажите целое число. Ваш ответ: 18

Задача №3 2 балла

[Случайные последовательности]
Генератор случайных чисел создал последовательность из N чисел, каждое из которых с равной вероятностью является одним из натуральных чисел из диапазона от 0 до 7 включительно. Чему равна длина последовательности N, если известно, что сообщение «вся последовательность состоит из одинаковых чисел» несет в себе ровно 21 бит информации. В ответе запишите целое число. Ваш ответ: 7

Задача №4 2 балла

[Программа для робота]
Хемуль программирует робота, который может передвигаться по квадратному полю. Поле разбито на равные квадратные клетки так, что длина каждой стороны поля – ровно M клеток. Со свойственной ему педантичностью, Хемуль пронумеровал все клетки поля, присвоив каждой клетке уникальный номер. Поскольку робот Хемуля может передвигаться только в пределах поля, Хемуль решил записывать программу для управления роботом как набор номеров клеток в порядке, в котором робот должен их посетить, используя для записи каждого номера одинаковое минимально возможное количество бит. Никакой дополнительной информации кроме этой последовательности номеров программа Хемуля не содержит.
Снорк обратил внимание, что робот Хемуля за один ход может переместиться только в одну из восьми клеток, окружающих клетку, в которой он находился перед началом хода, и предложил записывать программу другим способом – как последовательность команд роботу на единичное перемещение в одном из восьми направлений. Для записи каждой команды на единичное перемещение Снорк решил использовать одинаковое минимально возможное количество бит. Перед первой командой на единичное перемещение Снорк решил записывать номер клетки, из которой робот начинает движение, также как и Хемуль, используя для записи этого номера минимально возможное количество бит. Никакой дополнительной информации кроме последовательности команд и номера первой клетки программа Снорка не содержит.
Снорк выбрал маршрут, в котором робот последовательно посещает 32 клетки, включая начальную и конечную клетку маршрута, и сравнил записи своей программы и программы Хемуля, описывающих этот маршрут. В результате сравнения Снорк обнаружил, что для хранения его программы требуется на 341 бит меньше, чем для хранения программы Хемуля. Определите, при каком максимальном размере поля это возможно. В ответе укажите одно целое число M – количество клеток по одной из сторон поля. Ваш ответ: 128

Задача №5 2 балла

[Логический конструктор]
Снифф нашел конструктор, состоящий из логических элементов и инструкцию по сборке. В инструкции была приведена схема, и было описано, какой логический элемент реализует какую логическую операцию, преобразуя значения, подаваемые слева элемента на вход в значение, получаемое справа элемента на выходе.

Снифф собрал в соответствии с инструкцией следующую схему и стал экспериментировать, подавая различные значения Ai и Bi на вход и наблюдая значения Si и P3 на выходе схемы:

Определите значения, которые Снифф подал на входы Bi, если известно, что на входы Ai он подал значения A0=0, A1=1, A2=1, A3=0, а на выходе получил значения S0=1, S1=0, S2=0, S3=0, P3=1.
В ответе укажите подряд без пробелов четыре значения в следующем порядке: значение, поданное на вход B0, значение, поданное на вход B1, значение, поданное на вход B2, значение, поданное на вход B3. Ваш ответ: 1101

Задача №6 2 балла

[Странная симметрия]
Упростите логическое выражение или укажите его результат (при его однозначности). Результат упрощения может содержать только операции инверсии, конъюнкции и дизъюнкции.
(A and B and not C → A) ↔ (A → not C and B and A)


Комментарий по вводу ответа: операнды вводятся большими латинскими буквами; логические операции обозначаются, соответственно как not, and и or.
Скобки используются только для изменения порядка выполнения операций. Если порядок выполнения операций очевиден из их приоритетов – дополнительное использование скобок считается ошибкой.
При однозначном ответе – истинный ответ обозначается как 1, а ложный как 0.
Пример записи ответа: (A ornot B) and C Вашответ: not A or not C and B

Задача №7 1 балл

[Циклический сдвиг]
Тофсла построил таблицу истинности логической функции от трех аргументов F(A,B,C) и обнаружил, что функция принимает истинное значение только для двух наборов значений аргументов, причем эти два набора расположены в таблице истинности подряд друг за другом. Комбинации значений аргументов в таблице истинности Тофслывыстроены сверху вниз в лексикографическом порядке. Порядок следования столбцов: первый столбец – A, второй – B, третий – C.
Вифсла сдвинул столбец значений логической функции Тофслы циклически вниз на две позиции и обнаружил, что логическая функция G(A,B,C), задаваемая получившимися после сдвига значениями, принимает истинное значение для комбинаций аргументов, каждая из которых является противоположной одной из комбинаций, для которых была истина функция Тофслы. Противоположной комбинацией значений аргументов будем считать комбинацию, в которой значение каждого аргумента является инверсией значения соответствующего аргумента в исходной комбинации.
Найдите функцию F(A,B,C), которую построил Тофсла и приведите в ответе логическое выражение, описывающее эту функцию в наиболее упрощенном виде. Логическое выражение может содержать логические переменные A, B и C и логические операции отрицания, конъюнкции или дизъюнкции, обозначаемые как not, and и or соответственно, и не должно содержать скобок. Если таких функций несколько – приведите одну любую из них. Вашответ: not A and not B

Задача №8 4 балла

[Рекурсивная заливка]
Дано растровое изображение, исходно содержащее точки двух цветов – белого (фон) и черного (фигура). На изображении введена система координат с центром в верхнем левом углу и направлением осей как показано на рисунке:

Муми-папа решил использовать метод, позволяющий закрасить все точки внутри фигуры зеленым цветом. Метод представляет собой рекурсивный вызов процедуры «Залить», которой при каждом вызове передаются два параметра. Первый параметр – координата X и второй параметр – координата Y некоторой точки.
В процедуре «Залить» реализован следующий алгоритм:
1. Проверить цвет в точке с координатами X, Y, переданными при вызове процедуры в качестве первого и второго параметров, соответственно.
2. Если точка с этими координатами – белого цвета, то выполнить следующие действия:
a. Окрасить точку с координатами X, Y зеленым цветом.
b. Вызвать процедуру «Залить», передав ей значения параметров: первый параметр равен X-1, второй параметр равен Y.
c. Вызвать процедуру «Залить», передав ей значения параметров: первый параметр равен X, второй параметр равен Y-1.
d. Вызвать процедуру «Залить», передав ей значения параметров: первый параметр равен X+1, второй параметр равен Y.
e. Вызвать процедуру «Залить», передав ей значения параметров: первый параметр равен X, второй параметр равен Y+1.
3. Если точка с этими координатами не белого цвета, то завершить работу процедуры.
Муми-папа вызвал процедуру со значениями параметров X=7 и Y=7 и стал наблюдать за закрашиванием фигуры. Первой закрасилась точка с координатами X=7 и Y=7, затем точка с координатами X=6 и Y=7, затем X=5 и Y=7 и т.д. В результате все точки внутри фигуры оказались окрашены в зеленый цвет. Определите координаты точки, которая была последней окрашена в зеленый цвет. В ответе укажите через запятую два целых числа – сначала координату X, а затем координату Y. Ваш ответ: 5, 9

Задача №9 4 балла

[Настройка телескопа]
Хемуль построил телескоп для наблюдения за кометой. Поскольку это очень сложный прибор, его требуется настроить. Настройка телескопа заключается в последовательном выполнении шести операций строго в указанном порядке: O1, O2, O3, O4, O5, O6. В Муми-доле живут четыре мастера, каждый из которых умеет осуществлять некоторые из этих операций. Ниже приведена таблица, указывающая, какие операции может осуществлять какой мастер:
Мастер Операции, которые он умеет выполнять
Мастер1 O1, O5, O6
Мастер2 O2, O3, O5
Мастер3 O1, O2, O4
Мастер4 O3, O4, O6
Жилища мастеров расположены на некотором расстоянии друг от друга. Время, которое необходимо Хемулю, чтобы перенести телескоп от жилища одного мастера до жилища другого мастера, приведено в таблице:
Мастер1 Мастер2 Мастер3 Мастер4
Мастер1 -------- 1 час 2 часа 3 часа
Мастер2 1 час -------- 3 часа 2 часа
Мастер3 2 часа 3 часа -------- 1 час
Мастер4 3 часа 2 часа 1 час --------
Хемуль очень педантичен, поэтому он начинает свой путь с посещения одного из мастеров, которые могут выполнить операцию O1, затем переносит телескоп к мастеру, который может выполнить операцию O2 и т.д., всегда используя прямую дорогу между соответствующими мастерами и затрачивая на нее время, указанное в таблице.
Каждый мастер затрачивает на каждую операцию одинаковое количество времени – 1 час. Мастер начинает работать тот час же, как только Хемуль приходит в его жилище. Хемуль покидает жилище мастера и отправляется к следующему тот час же, как только мастер заканчивает операцию. Если мастер может выполнить две идущие подряд операции – Хемуль может остаться в его жилище и дать ему возможность выполнить обе операции.
Найдите для Хемуля оптимальную последовательность посещения мастеров, чтобы он затратил минимальное время на полную настройку телескопа. Посчитайте для этой последовательности (она может быть не единственна) время в часах от момента, когда Хемуль пришел в жилище мастера, который может выполнить операцию O1 до окончания одним из мастеров выполнения операции O6. В ответе укажите целое число. Ваш ответ: 10

Задача №10 1 балл

[Кручу-верчу]
Дана блок-схема алгоритма. Перед началом его выполнения целочисленный одномерный массив A из 10 элементов был равен (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). После завершения выполнения алгоритма массив A оказался равен (2, 3, 1, 4, 7, 5, 8, 9, 0, 6). Определите, какие значения были у элементов целочисленного одномерного массива mas перед началом выполнения алгоритма, если известно, что каждый его элемент может принимать только значения в диапазоне от 1 до 4. Нумерация элементов массивов начинается с 1. В ответе укажите через запятую 4 числа – элементы массива mas в порядке их следования в массиве.