Задано натуральное число из N цифр (N<=100). Найти минимальное счастливое число, которое больше заданного. Число называется счастливым, если: сумма цифр, которые стоят на четных позициях, равна сумме цифр, которые стоят на нечетных позициях.

Понятно, что "двигаясь" от заданного числа в сторону увеличения надо построить число-ответ. Задача, скорее всего решается через динамическое программирование. Однако, вопрос: какую эвристику тут следовало б использовать для сокращения перебора?

Здравствуйте, olimp_20, Вы писали:

_>Задано натуральное число из N цифр (N<=100). Найти минимальное счастливое число, которое больше заданного. Число называется счастливым, если: сумма цифр, которые стоят на непарных позициях, равна сумме цифр, которые стоят на парных позициях.

Непонятно, что подразумевается под "парной" позицией. Четная/нечетная?
Классическое определение говорит о левой и правой половине числа:
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

Здравствуйте, 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). Найти минимальное счастливое число, которое больше заданного. Число называется счастливым, если: сумма цифр, которые стоят на четных позициях, равна сумме цифр, которые стоят на нечетных позициях.

_>Понятно, что "двигаясь" от заданного числа в сторону увеличения надо построить число-ответ. Задача, скорее всего решается через динамическое программирование. Однако, вопрос: какую эвристику тут следовало б использовать для сокращения перебора?

Динамическое программирование здесь, имхо, не нужно.

Поскольку у нас требование "найти число больше заданного", то просто инкрементируем его и получим требование "не меньше заданного".

Находим чексумму заданного числа: s(r) = +r0-r1+r2-r3+...

(Пусть, для определённости, у нас младшими разрядами вперёд, т.е. 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, — ура.

И т.д.

Отсюда напрашивается вопрос: сколько разрядов нам точно надо затронуть? И начать прямо со старшего.
Это несложно найти. Просто посмотрим, какое максимальное отклонение будет нам доступно.

В положительную сторону: 9-r0 + (r1 + 9-r2) + (r3 + 9-r4) + ...
В отрицательную: (r0 + 9-r1) + (r2 + 9-r3) + ...

Наивный итерационный процесс может выглядеть так:
— нашли старший разряд, который должен быть инкрементирован
— прибавили к нему 1 и тупо обнулили все младшие, посчитали сумму заново
— повторили процедуру.