Форум » Выполнение и анализ алгоритмов для исполнителей » Задача 12-6634: порядок цифр важен! » Ответить
Задача 12-6634: порядок цифр важен!
gutgut: Входная строка для Редактора (по условию) содержит 40 цифр 1, 40 цифр 2 и n цифр 3 в произвольном порядке. Но если задать именно такой порядок, то при любом n сумма цифр строки-результата равна 120, т.е. условие задачи - сумма цифр равна 100 никогда не выполнится!
Ответов - 3
Ж: Здесь важно именно то, что порядок произвольный! Заметим, что - первая замена никак не влияет на сумму цифр строки - вторая уменьшает сумму на 4 - третья уменьшает сумму на 3 Пусть вторых замен - а, а третьих - b Тогда сумма изменится так: 1*40+2*40+3*n - a*4-b*3=100 С помощью небольшого кода переберем варианты [pre2] from itertools import * for n in range(25): for (a,b) in product(range(n+1),range(n+1)): if 40+80+3*n-4*a-3*b==100 and a+b<=n: print(n); exit() [/pre2] Результат: 20 Минимальное значение n=20 Пример строки: '3213213213213213213213213213213213213213213213213213213213211111111111111111111122222222222222222222'
gutgut: По моему мнению, вопрос задачи следовало бы сформулировать следующим образом: "Определите наименьшее значение n, для которого существует порядок цифр исходной строки, такой, что сумма цифр строки, полученной после выполнения алгоритма, будет равна 100."
Ж: В задании как раз просят как-то перебрать все варианты расположения цифр и найти тот, при котором выполнится условие. Это весьма стандартное условие для этого типа задач. Есть специальная функция, которая умеет перемешивать строки from random import * shuffle('123') И в некоторых задач ответ не зависит от порядка. Но не в этой задаче - здесь программа при каждом перемешивании выдает разные ответы. Значит, это тот тип задач, в которых код не поможет - только логика. Она помогает сделать оценку (минимум 20 троек), но требуется привести пример такой строки. т.к. оценка может быть и недостижима...
полная версия страницы