九度oj 题目1358：陈博的平均主义

题目描述：

在JOBDU团队里，陈博是最讲平均主义的人了，但并不是像梁山好汉那样能够做到有钱同花，有肉同吃，毕竟，他还是被家里的领导管着的……陈博的平均主义，就只能体现在他对数字的喜好了。陈博特别喜欢一类“平均数”，“平均数”的具体定义为：

对于一个数字，当其以十进制形式表示时，我们可以将其每一位的数字分为两堆，两堆数字的和是相等的。

例如，数字363就是一个理想的平均数，因为我们可以将其分为相等的两堆{3, 3}, {6}。

现在陈博就要考考你了，看你是否掌握了他的平均主义。假如给你一个整数范围[A, B]，你是否能找出，在这个范围内，究竟有多少“平均数“？

输入：

每个测试文件包含多个测试案例，每个测试案例一行，每行包括两个整数A、B，其中[A，B]这个待查看的整数范围。其中我们能保证1 <= A <= B <= 10⁹，且0 <= B – A <= 10⁵。

输出：

对于每个整数范围[A, B]，返回一个整数，表明这个整数范围内有多少个整数是陈博所喜欢的“平均数”。

样例输入：

1 50
1 1000

样例输出：

4
135

本来以为有更精妙的方法，但参考了一下别人的，直接遍历判断就可以
代码如下

#include <cstdio>
#include <cmath>

int a, b;
int num[35];

bool find(int sum, int n) {
    if(sum == 0) {
        return true;
    }
    if(n < 0 || sum < 0) {
        return false;
    }
    return find(sum,n-1) || find(sum-num[n],n-1);
}

bool isA(int m) {
    int j = 0;
    int sum = 0;
    while(m >= 10) {
        int mo = m % 10;
        num[j++] = mo;
        sum = sum + mo;
        m = m/10;
    }
    num[j++] = m;
    sum = sum + m;
    if(sum&1) {
        return false;
    }
    else {
        int bsum = sum / 2;
        return find(bsum, j-1);
    }

}

int main() {
    while(scanf("%d %d",&a, &b) != EOF) {
        int cnt = 0;
        for(int i = a; i <= b; i++) {
            if(isA(i)) {
                cnt++;
            }
        }
        printf("%d
",cnt);
    }
    return 0;
}