yzman: Вчера был тренировочный ЕГЭ по информатике. Знакомый препод поделился одним подъ**истым заданием "на

Вчера был тренировочный ЕГЭ по информатике. Знакомый препод поделился одним подъ**истым заданием "на алгоритмизацию", которое стояло 27 номером.

На вход дана строка - двоичная запись нечётного положительного числа X, меньшего 2 в степени 500. Необходимо вывести строку - двоичную запись минимального произведения чисел Y и Z, где Y и Z - любые числа, удовлетворяющие условиям:
1) X=Y+Z
2) оба Y и Z являются простыми
Гарантируется корректность вводной строки, а так же, что существует хотя бы одна пара Y и Z.

И даны два числа, что-то вроде 110011100111 и последовательность из 450+ ноликов и единичек , заканчивающаяся на 110011. В ответ нужно записать результат работы алгоритма для каждого из двух чисел.

Ответ - гениален. Но учит делать костыли )

Замечаем, что числа заканчиваются на 11. Заменяем эти 11 на 010 в любом текстовом редакторе, вот он и ответ.

По сути, мы пользуемся тем, что нам гарантируют, что решение есть. Если число нечётное, и представлено в виде суммы слагаемых, то одно - всегда чётное, второе - всегда нечётное. Значит, если Y и Z существуют, то Y будет простым чётным, а Z - простым нечётным. Простое чётное - одно - двойка. Поэтому, если решение есть, то оно будет единственным.

Так что нам нужно в двоичной записи числа вычесть 2 и умножить на 2 (Y*Z = 2(X-2)). А это, если число заканчивается в двоичной записи на 11 эквивалентно тому, что предпоследний ноль поменяли на единицу, и дописали к этому результату ноль.

Вот таки дела, малята.

#егэ #реал #школа

28 апреля 2021

Отключить рекламу