ИТМО - 1

Петя научился переводить запись натурального числа в другую систему счисления и для тренировки переводил числа из десятичной в двоичную систему счисления. Он заметил, что для некоторых чисел выполняется следующее условие: количество разрядов в записи такого числа в двоичной системе счисления ровно в три раза больше количества разрядов в записи этого же числа в десятичной системе счисления. Петя случайно нашел два таких числа: 6₁₀=110₂ и 300₁₀=100101100₂, но уверен, что таких чисел больше, и решил подойти к их поиску системно. Он написал программу, последовательно перебирающую все натуральные числа и добавляющую в список очередное число, если оно удовлетворяет указанному выше условию, и запустил её на суперкомпьютере. Какое число оказалось в списке под номером 10⁸-1? В ответе укажите целое число. Примечание: числа в списке Пети нумеруются с 1.

Найдите максимальное рациональное число R, меньшее 1 такое, что если его сложить с числом (1/255)₁₀ и перевести результат в четверичную систему счисления, то в дробной части будут встречаться только цифры 1. В ответе укажите несократимую дробь в виде m/n, представив числитель и знаменатель в десятичной системе счисления, например, 9/41.

Таня готовится к ЕГЭ по информатике и решает задачу, связанную с траекторией вычислений. Задача звучит следующим образом: Исполнитель Апрель преобразует число на экране. У исполнителя есть три команды:

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

2. Умножить на 3 и поделить нацело на 2.

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

Программа для исполнителя Апрель - это последовательность команд. Сколько существует программ, для которых при исходном числе 10 результатом является число 5094 и при этом траектория вычислений программы содержит число 51?

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

Например, для программы 213 при исходном числе 8 траектория будет состоять из чисел 12, 13, 26.

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

1. Траектория вычислений программы содержит числа 19 и 33.

2. Траектория вычислений программы содержит числа 18 и 35.

3. Траектория вычислений программы содержит числа 17 и 31.

Необходимо упорядочить эти три сообщения по возрастанию количества собственной информации в каждом из этих сообщений. В ответе запишите номера сообщений в нужном порядке без пробелов. Если некоторые сообщения содержат в себе одинаковое количество информации, укажите их номера в порядке возрастания.

Алфавит сообщений состоит из 10 символов. Символы записываются с помощью префиксного двоичного кодирования: символам алфавита соответствуют кодовые слова переменной длины так, что для всех кодовых слов выполняется прямое условие Фано (никакое кодовое слово не может быть началом другого кодового слова). Будем считать длиной кодового слова количество двоичных цифр в этом кодовом слове. Петя решил использовать следующие кодовые слова для кодирования символов алфавита:

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

Вася получил длинную последовательность из цифр следующим образом. Он брал подряд натуральные числа, начиная с 1, переводил их в четверичную систему счисления и записывал результаты перевода друг за другом. Вот начало этой последовательности: 123101112132021222330313233100… Вася остановился только тогда, когда дописал в конец последовательности четверичную запись числа 102310. Затем он представил, что это одно большое число, записанное в четверичной системе счисления, и перевел его в шестнадцатеричную систему счисления. Определите, какая шестнадцатеричная цифра стоит в этом числе на 60-ой позиции, считая слева направо от начала числа, а затем какая шестнадцатеричная цифра стоит на 1000-ой позиции. В ответе укажите эти две шестнадцатеричные цифры в указанном порядке через пробел.

Известен результат вычисления следующего выражения: (245 or X) and (187 xor not X) = 85, где not, and, or и xor обозначают операции побитового отрицания, побитового И, побитового ИЛИ и побитового исключающего ИЛИ соответственно Считается, что для вычислений используется 16-ти битное двоичное представление всех чисел, и любая побитовая операция применяется ко всем битам, включая незначащие нули. Найдите минимальное натуральное число X, для которого будет справедлив этот результат вычисления. В ответе укажите целое число.

Дана исходная последовательность из семи цифр: "1234567". Из нее строится новая последовательность по следующему цикличному алгоритму: на каждом шаге берутся последние семь цифр последовательности, полученной на предыдущем шаге, первые три из них переставляются в конец и результат присоединяется справа к последовательности, полученной на предыдущем шаге. Алгоритм выполняется до тех пор, пока после очередного присоединения не получится последовательность длиной 3500 цифр. Вот результаты выполнения первых двух шагов: Шаг 1: 12345674567123 Шаг 2: 123456745671237123456 Определите, какая цифра стоит на позиции 1024, а какая на позиции 2048 в получившейся последовательности. В ответе укажите через пробел две цифры. Сначала цифру, которая оказалась на позиции 1024, а затем цифру, которая оказалась на позиции 2048.

Пусть Z = (7775₈)^X , где X – это 1111-я цифра после запятой в записи результата вычисления выражения: 0,(41)₈ * 0,6(25)_8, представленного в восьмеричной системе счисления. Найти последнюю цифру в записи числа Z, записанного в шестнадцатеричной системе счисления. В ответе укажите одну шестнадцатеричную цифру.