Задано натуральное число из N цифр (N<=100). Найти минимальное счастливое число, которое больше заданного. Число называется счастливым, если: сумма цифр, которые стоят на четных позициях, равна сумме цифр, которые стоят на нечетных позициях.
Понятно, что "двигаясь" от заданного числа в сторону увеличения надо построить число-ответ. Задача, скорее всего решается через динамическое программирование. Однако, вопрос: какую эвристику тут следовало б использовать для сокращения перебора?
Здравствуйте, olimp_20, Вы писали:
_>Задано натуральное число из N цифр (N<=100). Найти минимальное счастливое число, которое больше заданного. Число называется счастливым, если: сумма цифр, которые стоят на непарных позициях, равна сумме цифр, которые стоят на парных позициях.
Здравствуйте, Chorkov, Вы писали:
C>Здравствуйте, olimp_20, Вы писали:
_>>Задано натуральное число из N цифр (N<=100). Найти минимальное счастливое число, которое больше заданного. Число называется счастливым, если: сумма цифр, которые стоят на непарных позициях, равна сумме цифр, которые стоят на парных позициях.
C>Непонятно, что подразумевается под "парной" позицией. Четная/нечетная? C>Классическое определение говорит о левой и правой половине числа: C>https://ru.wikipedia.org/wiki/%D0%A1%D1%87%D0%B0%D1%81%D1%82%D0%BB%D0%B8%D0%B2%D1%8B%D0%B9_%D0%B1%D0%B8%D0%BB%D0%B5%D1%82
Там же:
Региональные особенности
«Счастливость» билета можно определить несколькими методами. Наибольшее распространение получили три из них:
Московский — если на автобусном билете напечатано шестизначное число, и сумма первых трёх цифр равна сумме последних трёх, то этот билет считается счастливым.
Ленинградский, или Питерский (менее распространённый) — если сумма цифр, стоящих на чётных местах билета, равна сумме цифр, стоящих на нечётных местах билета, то билет считается счастливым (в Санкт-Петербурге, напротив, именно этот способ называют «московским»). Другой вариант — суммы каждой пары цифр равны.
Утверждается также, что метод подсчёта сумм первых и вторых троек чисел москвичи называют «московским», а ленинградцы — «ленинградским», причём и те, и другие приписывают метод подсчёта сумм на чётных и нечётных позициях другому городу.
Здравствуйте, olimp_20, Вы писали:
_>Задано натуральное число из N цифр (N<=100). Найти минимальное счастливое число, которое больше заданного. Число называется счастливым, если: сумма цифр, которые стоят на четных позициях, равна сумме цифр, которые стоят на нечетных позициях.
_>Понятно, что "двигаясь" от заданного числа в сторону увеличения надо построить число-ответ. Задача, скорее всего решается через динамическое программирование. Однако, вопрос: какую эвристику тут следовало б использовать для сокращения перебора?
Динамическое программирование здесь, имхо, не нужно.
Поскольку у нас требование "найти число больше заданного", то просто инкрементируем его и получим требование "не меньше заданного".
(Пусть, для определённости, у нас младшими разрядами вперёд, т.е. r0 — самый младший).
Если s=0, заданное число счастливое, ура.
Можем исправить одним разрядом?
Если s<0 и r0-s<=9, то r0' = r0-s, s' = s-s = 0. Ура.
Если s>0, то очевидно, не можем.
Можем исправить двумя разрядами?
Очевидно, что любой инкремент разряда r1 только уменьшит сумму.
Поэтому, если s<0 и мы не смогли на предыдущем шаге, то очевидно, что и сейчас не сможем.
Если s>0, то в нашем распоряжении 9-r1 + r0 — инкремент второго разряда и декремент вплоть до обнуления первого. Но инкремент обязателен.
Т.е.
— сперва r1' = r1+1 (если, разумеется, он не был равен 9), s' = s-1
— затем r0'' = max(0,r0-s'), — уменьшаем насколько нужно и возможно, — s'' = s'+(r0''-r0)
— наконец, r1''' = min(9, r1'+s''), s''' = s''-(r1'''-r1')
— если s''' = 0, — ура.
И т.д.
Отсюда напрашивается вопрос: сколько разрядов нам точно надо затронуть? И начать прямо со старшего.
Это несложно найти. Просто посмотрим, какое максимальное отклонение будет нам доступно.
Наивный итерационный процесс может выглядеть так:
— нашли старший разряд, который должен быть инкрементирован
— прибавили к нему 1 и тупо обнулили все младшие, посчитали сумму заново
— повторили процедуру.