Есть калькулятор, на котором можно делать с числом только две операции: 1) Умножить это число на 3 (получить 3*x)
2) Отнять это число от 2 (получить 2-x)
Например, если с числом 2 сделать последовательность операций 12, то мы сначала должны умножить его на 3 и получить 6, а потом отнять получившееся от 2, и в ответе мы получим -4. Напишите длину самой короткой последовательности, которая из числа 1 получает 231.
В ответ запишите число.
7
Объяснение:
Заметим, что две операции типа 2 не меняют число: если было число x, то после первого вычитания получим 2 - x, после второго 2 - (2 - x) = x.
Значит, в самой короткой последовательности, которая получает 231 из числа 1, нет двух операций типа 2 подряд.
Рассмотрим самую короткую последовательность, получающую 231. Идем с конца:
231 делится на 3. Если бы последней операцией было вычитание, то на предыдущем шаге было бы -229, это число не делилось бы на 3, и получилось бы, что в последовательности два вычитания подряд, чего быть не должно. Значит, последняя операция - умножение, число на предыдущем шаге - 231 / 3 = 7777 не делится на 3, единственный вариант для предыдущего шага - получить из -75 путем вычитания-75 делится на 3, аналогично первому рассуждению это результат умножения числа -25 на 3-25 не делится на 3, оно получено из 27 путем вычитания27 делится на 3, аналогично, получено из 9 умножением9 делится на 3, аналогично, получено из 3 умножением3 могло получиться из 1 за один шаг умножением на 3.Итак, всё происходило так:
(1) 1 * 3 = 3
(1) 3 * 3 = 9
(1) 9 * 3 = 27
(2) 2 - 27 = -25
(1) -25 * 3 = -75
(2) 2 - (-75) = 77
(1) 77 * 3 = 231