Форум » Динамическое программирование » сложный 23 » Ответить
сложный 23
kvantor1616: Добрый день, коллеги. Условие задания. Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: А. Прибавить младший разряд числа. Б. Умножить на старший разряд числа. С. Умножить на 2 и прибавить сумму цифр числа. Первая команда увеличивает число на младший разряд числа, вторая – умножает на старший разряд числа, третья – умножает на 2 и прибавляет сумму цифр числа. Каждая команда изменяет число. Сколько существует таких программ, которые исходное число 10 преобразуют в число 4096? Моё решение [pre2] a = [0]*5000 a[10] = 1 for i in range(10,4096): if i+i%10<=4096: a[ i+i%10]+=a[ i] if i*(i//10**(len(str(i))-1))<=4096: a[ i*(i//10**(len(str(i))-1))]+=a[ i] if i*2+sum(map(int,str(i)))<=4096: a[ i*2+sum(map(int,str(i)))]+=a[ i] print(a[4096]) [/pre2] Ответ 564717868 сильно отличается от авторского 49340685. В чём может быть проблема?
Ответов - 2
Поляков: [pre2] N = 4096 a = [0]*(N+1) a[10] = 1 for i in range(10, N+1): ind = i*2 + sum(map(int, str(i))) if ind <= N: a[ind] += a[ i] last = i % 10 if last != 0 and i+last <= N: a[i+last] += a[ i] first = int(str(i)[0]) if first != 1 and i*first <= N: a[i*first] += a[ i] print( a[4096] ) [/pre2]
kvantor1616: Спасибо большое за подсказку! Не учёл, что нужно проверить младший разряд на ноль, а старший на единицу.
полная версия страницы