Количество чисел, делящихся на 11

[CrazyRabbit]

Доброго времени суток!
Есть задача: Н-ти все числа, делящиеся на 11, на промежутке от a до b(1<=a<=b<=10^19), сумма цифр которых лежит на промежутке от p до q.
Подскажите, пжл, идею динамического решения.
Заранее спасибо)))

[puporev]

А при чем деление на 11 в заголовке?

[CrazyRabbit]

все, исправил.

[puporev]

Признак делимости на 11.

Число делится на 11 тогда и только тогда, когда сумма цифр с чередующимися знаками равна 0 или делится на 11 (то есть 182 919 делится на 11, так как 1 — 8 + 2 — 9 + 1 — 9 = −22 делится на 11) — следствие факта, что все числа вида 10n при делении на 11 дают в остатке (-1)n.

Если Вы работаете в обычном Паскале, где не поддерживается тип Int64, то число нужно вводить строкой. Затем идти по строке и складывать или вычитать цифры(преобразовав их через val(s,t,c) или через ord(s)). Оформить это в виде функции логического типа. Затем в цикле считать все такие числа в заданном интервале, интервал тоже вводится строками.

[puporev]

Вот недавно разбирали похожую задачу, правда в Делфи, но суть таже.
http://programmersforum.ru/showpost....66&postcount=1

[CrazyRabbit]

это в принципе обычный перебор...и задача не пройдет по времени. надо какой-то другой способ!!!!

[Serge_Bliznykov]

это в принципе обычный перебор

ага. надо брать все числа от a до b и "перебирать" - проверять подходит ли данное число. кстати, в проходе по разрядам числа сразу формировать две суммы: одну с чередующимся знаком (для проверки делимости на 11), вторую сумму обычную - для проверки попадания в диапазон сумм разрядов (p <= SumРазрядов <= q) (да, и если сумма оказывается больше q - можно цикл сразу прерывать - дальше уже суммировать разряды смысла нет!)

и задача не пройдет по времени.

1) Вы ничего не говорили про ограничение по времени.
2) не смешите мои тапочки... 19 цифр просуммировать это много займёт времени?!
Хотя, конечно, цикл по числа 1 до 10^19 - это весьма небыстро... Ну тогда можно после первого найденного подходящего числа увеличивать проверяемые числа с шагом 11... это должно дать 10кратное ускорение...

[Gapro]

А какие значения могут принимать p и q ?

[puporev]

Ну видимо от 1 до 18*9

[CrazyRabbit]

на счет значений p и q puporev прав. На один тест отводится 2 сек, поэтому вышеизложенное решение не подойдет. Нужно как-то применить динамику.