Информатика

(PRO100 ЕГЭ) На вход алгоритма подаётся натуральное число N (N > 3). Алгоритм строит по нему новое число R следующим образом:

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если N делится на 4, то в конец этой записи дописывается две последние цифры двоичной записи;

б) если N не делится на 4, то остаток от деления N на 4 умножается на 2 в двоичной системе счисления и дописывается в начало двоичной записи числа N.

3. Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 110000₂ = 48₁₀, а для исходного числа 10₁₀ = 1010₂ результатом является число 1001010₂ = 74₁₀.

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

(PRO100 ЕГЭ) На вход алгоритма подаётся натуральное число N (N > 3). Алгоритм строит по нему новое число R следующим образом:

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если N делится на 5, то в конец этой записи дописывается три последние цифры двоичной записи;

б) если N не делится на 5, то остаток при делении на 5 числа N умножается на 5, переводится в двоичную запись и дописывается в конец двоичной записи числа N.

3. Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 11001010₂ = 202₁₀, а для исходного числа 10₁₀ = 1010₂ результатом является число 1010010₂ = 82₁₀.

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

(Досрочный ЕГЭ-2023) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если N делится на 3, то в конец этой записи дописывается три последние цифры двоичной записи.

б) если N не делится на 3, то остаток при делении на 3 числа N умножается на 3, переводится в двоичную запись и дописывается в конец двоичной записи числа N.

3. Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 1100100₂ = 100₁₀, а для исходного числа 4₁₀ = 100₂ результатом является число 10011₂ = 19₁₀.

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

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

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

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

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

Пример. Дано число N=23. Алгоритм работает следующим образом: 23 113₄ 11132₄ 350₁₀.

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

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

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

2. К этой записи дописываются еще несколько разрядов по следующему правилу:

а) если N четное, то к нему справа приписываются два нуля, а слева единица;

б) если N нечетное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи;

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

Например, исходное число 4₁₀=100₂ преобразуется число 11000₂ = 48₁₀, а исходное число 13₁₀ = 1101₂ преобразуется в число 110111₂ = 55₁₀. Укажите такое число N большее 8, для которого число R является наименьшим среди чисел, превышающих 88. В ответе это число запишите в десятичной системе счисления.

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

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 00, а затем два левых разряда заменяются на 11;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 11, а затем два левых разряда заменяются на 10.

3. Для полученной записи повторно выполняется п. 2.

Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6₁₀ = 110₂ результатом является число 96₁₀ = 1100000₂, а для исходного числа 4₁₀ = 100₂ результатом является число 79₁₀ = 1001111₂. Найдите минимальное число R, большее, чем 1500, которое может получится в результате работы алгоритма.

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

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 00, а затем два левых разряда заменяются на 11;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 11, а затем два левых разряда заменяются на 10.

3. Пункт 2 повторяется ещё раз для записи, полученной после второго пункта.

Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6₁₀ = 110₂ результатом является число 96₁₀ = 1100000₂, а для исходного числа 4₁₀ = 100₂ результатом является число 79₁₀ = 1001111₂. Найдите максимальное число R, меньшее, чем 1500, которое может получится в результате работы алгоритма.

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

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

2. Далее к этой записи справа дописывается 0, а два левых разряда заменяются на 1.

3. Полученная таким образом запись является двоичной записью искомого числа R.

Например, для числа 13 двоичные коды цифр: 1 = 0001₂, 3 = 0011₂. С добавленными битами чётности: 00011 и 00110, результат шага 1: 0001100110. Заменяем два левых разряда на 1 и добавляем справа 0: 1011001100₂ = 716.

Укажите минимальное N, после обработки которого с помощью этого алгоритма получится 674890.

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

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если сумма цифр в двоичной записи числа чётная, то 4 младших бита инвертируются, т.е. 0 изменяется на 1, а 1 на 0;

б) если сумма цифр в двоичной записи числа нечётная, то инвертируются 4 бита в двоичных разрядах 1-4 (нумерация разрядов справа налево, начиная с 0).

3. Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 36₁₀ = 100100₂. результатом является число 43₁₀ = 101011₂ а для исходного числа 37₁₀ = 100101₂ результатом является число 59₁₀ = 111011₂. Укажите число N, большее 63, после обработки которого с помощью этого алгоритма получается минимальное число R. В ответе запишите число в десятичной системе счисления.

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

1. Из числа N вычитается количество нулей в двоичной записи числа N.

2. Строится двоичная запись полученного числа.

3. К полученной записи слева дописывается три младших разряда.

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

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

1. 13 = 1101₂, двоичная запись содержит один 0. 13 – 1 = 12.

2. 12₁₀ = 1100₂

3. 1100 -> 1001100.

4. 1001100₂ = 76

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

(А. Игнатюк) Компьютер по имени Иннокентий преобразует натуральное число N по следующим правилам и получает число R:

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

2) Если количество цифр в двоичной записи числа N четно, то справа приписывается 10, если нечётно, то слева приписывается 11.

Полученная таким образом запись является двоичной записью искомого числа R. Найдите количество чисел N из отрезка [100; 200], для которых результат работы компьютера будет четным.

(Е. Усов) Исполнитель Сыщик получает на вход натуральное число N и строит новое число R следующим образом.

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

2) Далее эта запись обрабатывается по следующему правилу:

а) Если число чётное, справа приписывается максимально возможная цифра, в противном случае справа приписывается 0.

б) Справа приписывается шестнадцатеричная цифра – остаток от деления суммы цифр шестнадцатеричной записи на 16.

в) Пункт б выполняется ещё один раз.

Полученная таким образом запись является шестнадцатеричной записью искомого числа R.

Укажите минимальное число N, для которого максимальная цифра в полученной шестнадцатеричной записи встречается в пять раз чаще, чем минимальная. В ответе это число запишите в десятичной системе счисления.

(Е. Усов) Исполнитель Сыщик получает на вход натуральное число N и строит новое число R следующим образом.

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

2) Далее эта запись обрабатывается по следующему правилу:

а) Если число чётное, справа приписывается максимально возможная цифра, в противном случае справа приписывается 0.

б) Справа приписывается шестнадцатеричная цифра – остаток от деления суммы цифр шестнадцатеричной записи на 16.

в) Пункт б выполняется ещё один раз.

Полученная таким образом запись является шестнадцатеричной записью искомого числа R.

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

(А. Игнатюк) Исполнитель «Аппо» получает на вход четырехзначное число N и строит новое число R по следующим правилам:

1. Если первая цифра числа N делится на 4, то заменяем её на цифру 9.

2. Если первая цифра числа N делится на 2 и не делится на 4, то заменяем её на цифру 3.

Сколько существует чисел N, для которых соответствующее число R начинается с цифры 9, а восьмеричная запись числа R оканчивается цифрой 4?

(А. Игнатюк) Исполнитель «Аполлон» получает на вход четырёхзначное число N и строит новое число R по следующим правилам:

1. Если число N начинается с чётной цифры, то число R вычисляется как сумма первой и третьей цифр и модуля разности второй и четвёртой цифр.

2. Если число N начинается с нечётной цифры, то цифры числа N располагают в неубывающем порядке. Число R вычисляется как сумма цифр в двоичной записи полученного числа.

Сколько существует чисел N, для которых результат работы алгоритма будет более 20?

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

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 6 = 110₂ результатом является число 1000₂ = 8, а для исходного числа 4 = 100₂ результатом является число 1101₂ = 13.

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

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

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

2. Из полученной записи убирается старшая (левая) единица.

3. Если в полученной записи количество единиц четное, то слева дописывается 10, иначе слева дописывается 1, а справа – 0.

Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 4₁₀ = 100₂ результатом будет являться число 8₁₀ = 1000₂, а для исходного числа 6₁₀ = 110₂ результатом будет являться число 12₁₀ = 1100₂.

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

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

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

2. Складываются все цифры двоичной записи числа N. Если полученная сумма чётна, из числа убирают ведущую единицу (а также ставшие незначащими нули). В противном случае слева приписывается 1, а справа – два ноля.

3. Над новой записью снова производятся действия, описанные в пункте 2.

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

Например, N = 5₁₀ = 101₂ => 1 => 1100₂ = 12₁₀ = R

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

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

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

2. Если количество единиц в этой записи чётно, стирается ведущая единица. В противном случае из записи числа убираются все нули, а в конец приписывается 1.

3. Над новой записью снова производятся действия, описанные в пункте 2.

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

Например, N = 5₁₀ = 101₂ => 1 => 11₂ = 3₁₀ = R.

Сколько существует чисел N, не превосходящих 1000, таких что R = 7?

(В. Шубинкин) Автомат получает на вход номер банковской карты (число N из 16 цифр) и строит по нему контрольное число S следующим образом (вариант алгоритма Лу́на):

– цифры числа нумеруются справа налево, начиная с ноля;

– цифры, стоящие на нечётных позициях, увеличиваются в два раза. Если при этом получается двузначное число, его цифры складываются;

– результат S вычисляется как сумма всех цифр на чётных позициях и преобразованных цифр на нечётных позициях.

Например, для числа 4096 8308 0309 8323 сумма цифр на чётных позициях (с конца) 3+3+9+3+8+3+6+0=35, сумма преобразованных цифр на нечётных позициях 4+7+0+0+0+7+9+8=35. Общая сумма S = 70.

Найдите наименьший номер банковской карты N, для которого результатом работы алгоритма будет число 30. В ответе укажите остаток от деления найденного числа N на 10₈.