Поделитесь своими знаниями, ответьте на вопрос:
Решить на python или c++ числау миши развитое эстетическое чувство. он считает, что не все числа одинаково . когда ему грустно, он начинает придумывать числа и приводить их в порядок.миша любит рассматривать сумму цифр числа. для того чтобы в порядок число a, он сначала записывает само число. потом он пишет сумму цифр этого числа. затем сумму цифр суммы цифр и так далее, до тех пор, пока очередное число не станет однозначным. он считает, что результатом в порядок числа a является сумма всех выписанных чисел, включая само число a.миша настолько любит этот процесс, что он даже заменяет ему счет овец, когда долго не получается заснуть. он помнит, что вчера ночью, когда он в уме в порядок число a, у него получилось число b. но вот беда - он не помнит, какое именно он взял число a! ему в отыскании этого числа.входные данныеодно целое число b (1 ≤ b ≤ 109выходные данныеесли существует такое число a, что после его в порядок, получается b, то выведите любое такое число. если же миша где-то ошибся в расчетах и такого числа не существует, то выведите -1.на python: a=int(s=1f=truewhile s ch=s count=ch while ch> 9: ch=sum(map(int, str( count+=ch if count==a: print(s) f=false break s+=1if f: print(-1)проходит 7/12 тестов
самая оптимальная стратегия угадывания - дихотомия, то есть деление отрезка пополам и задавание вопроса больше? (или меньше? )
например, загадано 50
последовательность
32 64/2 больше
48 (32+64)/2 больше
56 (48+64)/2 меньше
52 (48+56)/2 меньше
50 (48+52)/2 попал
теперь о . вопрос некорректный, если бы он звучал, как сколько попыток нужно сделать, чтобы угадать? , то решение простое
64 = 2^6, поэтому нужно 6 попыток 6 = 110b, значит 3 бит достаточно, чтобы в них разместить это количество попыток.
но в вопрос-то другой! потому что в процессе отгадывания на каждом шаге нужно знать 1. концы отрезка, 2. ответ
концы это 6 бит и 6 бит +ответ 1 бит, итого 13 бит на шаг *6 = 78 бит. можно ещё сократить немного, так как в последующем вопросе используется информация из предыдущего(один из концов интервала).
уточни, что имеется в виду под фразой "какое количество информации", иначе неопределена и допускает многочисленные толкования.