Алгоритм подсчета количества чисел в промежутке от А до B, сумма цифр которых четна?
======================================================================================

 Здравствуйте.   

Помогаю школьникам подготовиться к олимпиаде по программированию. Разбираю решения некоторых задач. Решение одной задачи, на мой взгляд не рационально. Однако найти более оптимальное решение у меня не получается.  
  

Условие задачи: даны два числа A и B. Посчитайте количество натуральных чисел на отрезке от A до B, сумма цифр которых четна.  

Программа получает два натуральных числа A и B, не превосходящих 10^9, A <= B.  

Программа должна вывести одно число - количество натуральных чисел, больше или равных A и меньших или равных B, сумма цифр которых четна.  
  

Решение, что приходит на ум: два цикла (цикл в цикле) - В первом перебираем сами числа, а во втором цифры каждого числа.   
  

Стоит учитывать, что ребятам приходится писать на линейном языке программирования (поэтому некоторые решения в принципе не могут быть оптимальными, но не настолько)  
  

Хотелось бы получить идею, как реализовать данную программу без второго цикла (а может и без первого - путем математических вычислений) или ваши мысли по поводу алгоритма для нахождения чисел, сумма цифр которых четна, без перебора самих чисел (если возможно).  
  

Кстати, странно, что у таких чисел еще нет названия :)  
  

Заранее благодарен, Артем. 

На каждом отрезке от 10*n до 10*n+9 таких чисел ровно 5. Поэтому нам достаточно посчитать число таких полных отрезков, и обработать краевые отрезки.
Пусть sumdig(n) - функуция, которая выдаёт остаток от деления суммы цифр n на 2.
Тогда:
int s0=(B/10-A/10-1)*5;
int s1=(10+sumdig(A/10)-A%10)/2;
int s2=(2+B%10-sumdig(B/10))/2;
return s0+s1+s2;

 

А если банально (1+B-A)/2 (без дробной части) ?
Вроде как сходится для малых чисел :-)

 

Берём число A, определяем для него чётность суммы чисел, потом рассуждаем так: если A нечётно, то A+1 будет чётно, если A чётно, то A+1 - нечётно. Исключение делаем для перехода xx9 - xy0 (там по-моему xx9 и xy0 имет одинакоую чётность).
В общем, так чередуясь бежим до B. Я бы делал так.

 

Правильно ли я понял условия задачи?

Выдается произвольный диапазон, например от 2000 до 5000.
Нужно для каждого числа, например 2013 сложить цифры, 2 + 0 + 1 + 3 и в случае если полученное число четно, увеличить счетчик на 1 ?

т.е. лобовое решение

1) Цикл: создали массив с данными в заданном диапазоне
2) Цикл: Разобрали числа на составляющие, сложили, разделили на два, определили четное или нет
3) Если четное увеличили счетчик на 1
4) Вывели результат по окончанию работы программы

Самым быстрым будет в данном случае математическое решение без циклов, но школьный ли это уровень?