ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Преобразование записи числа.
| КЭС: | 3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность 3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат 3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена» 3.5 Многоразрядные целые числа, задачи длинной арифметики |
| Тип ответа: | Краткий ответ |
Ответ: 49
Дано: N — натуральное число. Укажите такое наибольшее число N, для которого R не превышает 210. В ответе запишите это число в десятичной системе счисления.
Пусть k — длина двоичной записи N, s — количество её единиц, d — длина двоичной записи s. В чётной ветви слева появляется 1, справа — 00. В нечётной ветви справа дописывается вся двоичная запись s, поэтому её длина может меняться.
Общие формулы: R = 4 · 2ᵏ + 4N при чётном N; R = 2ᵈ · N + s при нечётном N.
В чётной ветви R больше 8N. В нечётной s ≥ 1 и d ≥ 1, поэтому R ≥ 2N + 1. Для обеих ветвей достаточно оценки R ≥ 2N. Предполагать, что R возрастает при каждом увеличении N, нельзя: меняются ветвь и число дописываемых разрядов.
Обоснование конечного перебора.
Достаточно проверить 1 ≤ N ≤ 105. При N ≥ 106 нижняя оценка даёт R ≥ 2 · 106 = 212, что больше 210.
Такие N нарушают верхнюю границу из условия.
Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 3; N = 2, R = 24; N = 3, R = 14; N = 4, R = 48.
N = 5, R = 22; N = 6, R = 56; N = 7, R = 31; N = 8, R = 96.
N = 9, R = 38; N = 10, R = 104; N = 11, R = 47; N = 12, R = 112.
N = 13, R = 55; N = 14, R = 120; N = 15, R = 124; N = 16, R = 192.
N = 17, R = 70; N = 18, R = 200; N = 19, R = 79; N = 20, R = 208.
N = 21, R = 87; N = 22, R = 216; N = 23, R = 188; N = 24, R = 224.
N = 25, R = 103; N = 26, R = 232; N = 27, R = 220; N = 28, R = 240.
N = 29, R = 236; N = 30, R = 248; N = 31, R = 253; N = 32, R = 384.
N = 33, R = 134; N = 34, R = 392; N = 35, R = 143; N = 36, R = 400.
N = 37, R = 151; N = 38, R = 408; N = 39, R = 316; N = 40, R = 416.
N = 41, R = 167; N = 42, R = 424; N = 43, R = 348; N = 44, R = 432.
N = 45, R = 364; N = 46, R = 440; N = 47, R = 381; N = 48, R = 448.
N = 49, R = 199; N = 50, R = 456; N = 51, R = 412; N = 52, R = 464.
N = 53, R = 428; N = 54, R = 472; N = 55, R = 445; N = 56, R = 480.
N = 57, R = 460; N = 58, R = 488; N = 59, R = 477; N = 60, R = 496.
N = 61, R = 493; N = 62, R = 504; N = 63, R = 510; N = 64, R = 768.
N = 65, R = 262; N = 66, R = 776; N = 67, R = 271; N = 68, R = 784.
N = 69, R = 279; N = 70, R = 792; N = 71, R = 572; N = 72, R = 800.
N = 73, R = 295; N = 74, R = 808; N = 75, R = 604; N = 76, R = 816.
N = 77, R = 620; N = 78, R = 824; N = 79, R = 637; N = 80, R = 832.
N = 81, R = 327; N = 82, R = 840; N = 83, R = 668; N = 84, R = 848.
N = 85, R = 684; N = 86, R = 856; N = 87, R = 701; N = 88, R = 864.
N = 89, R = 716; N = 90, R = 872; N = 91, R = 733; N = 92, R = 880.
N = 93, R = 749; N = 94, R = 888; N = 95, R = 766; N = 96, R = 896.
N = 97, R = 391; N = 98, R = 904; N = 99, R = 796; N = 100, R = 912.
N = 101, R = 812; N = 102, R = 920; N = 103, R = 829; N = 104, R = 928.
N = 105, R = 844.
Наибольший допустимый вход: N = 49, R = 199. Его результат не больше 210; все большие входы в таблице нарушают условие, а входы за таблицей исключены оценкой.
Проверка выбранного входа: N = 49 = 110001₂.
Число единиц в исходной записи: 3; применяем нечётную ветвь, дописывая 11.
Преобразованная запись: 11000111₂.
R = 128 + 64 + 4 + 2 + 1 = 199.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем N.
Ответ: 49.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFFD3C06.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.