Задание 14 (ЕГЭ по информатике). Значение арифметического выражения 3^2000 + 3^10 - x, где х – натуральное число, записали в троичной системе счисления. Определите наименьшее значение x, при котором троичная запись значения данного выражения содержит 2000 цифр "2".
Источник: kompege.ru
Как будем решать задачу
- Запустим цикл по переменной x в диапазоне от 3^10 до 2*3^10(такой диапазон выбираем потому, что если вычтем 3**10, то получим 3**2000, а это число в 3 с.с. записывается, как 1 и 2000 нулей, а нам нужно получить число, в котором ровно 2000 двоек, а это число меньше на 1 разряд, значит, как минимум, нужно вычитать 3^10, так как ищем наименьшее, значит запускать можно не так далеко (), по сути, можно и теоретически решать эту задачу, в общем, кто понял, тот уже решил). Ну, в общем далее.
спасибо за комментарий: правая граница подбираемая, но можно запустить и бесконечный цикл, брейковать, когда число x найдено. - В цикле формируем число n = 3^2000 + 3^10 - x
- Переводим число n в троичную с.с. и считаем количество цифр "2"
- Во внешнем цикле проверяем, если количество цифр "2" равно 2000, выводим число x на экран
Программа решения задачи на языке Python
for x in range(3**10,2*3**10):
n = 3**2000 + 3**10 - x
p = 0
while n!=0:
d = n % 3
n//=3
if d==2:
p+=1
if p==2000:
print(x)
break
Ответ: 59050
Если не очень понятно, почему запускаем цикл по такому диапазону, то можно запускать цикл сначала от 1 до 1000 (не получим никакого ответа), затем от 1000 до 10000 (тоже не получим ответа), затем от 10000 до 50000 (тоже не получим ответа), затем от 50000 до 10000, получим ответ. То есть, экспериментально подбираем диапазон. Поскольку ищем минимальное число x, то после успешной проверки, можно его вывести и выполнить оператор break (выйти из цикла и не гнать его дальше).
Другие задания 14 из ЕГЭ по информатике в разделе Разбор задач ЕГЭ.
