9도 OJ 1358: 진박의 평균주의(반복, 귀속)

시간 제한: 1초
메모리 제한: 32메가바이트
특수 판제: 아니요
제출: 354
해결
제목 설명:
JOBDU 팀에서 진박은 평균주의를 가장 중시하는 사람이지만 양산 사나이처럼 돈도 있고 꽃도 있고 고기도 같이 먹을 수 있는 것은 아니다. 어쨌든 그는 집안의 지도자에 의해 관리되고 있다. 진박의 평균주의는 숫자에 대한 그의 취향에 나타난다.진박은 특히'평균수'를 좋아한다.'평균수'의 구체적인 정의는 다음과 같다.
한 숫자에 대해 10진법으로 표시할 때, 우리는 그 한 자리의 숫자를 두 무더기로 나눌 수 있으며, 두 무더기의 숫자의 합은 같다.
예를 들어 숫자 363은 이상적인 평균수이다. 왜냐하면 우리는 그것을 같은 두 무더기 {3, 3}, {6}로 나눌 수 있기 때문이다.
이제 진박은 너를 시험할 것이다. 네가 그의 평균주의를 장악했는지 아닌지를 보아라.만약 당신에게 정수 범위[A,B]를 준다면, 당신은 이 범위 내에 도대체 얼마의'평균수'가 있는지 찾아낼 수 있습니까?
입력:
각 테스트 파일은 여러 개의 테스트 사례를 포함하고 테스트 사례마다 한 줄씩, 한 줄마다 두 개의 정수 A, B를 포함한다. 그 중에서 [A, B]는 보기에 필요한 정수 범위이다.그중에서 우리는 1<=A<=B<=10을 보장할 수 있다
9, 그리고 0 <= B – A <= 10
오.
출력:
각 정수 범위 [A, B]에 대해 하나의 정수를 되돌려주면 이 정수 범위 내에 몇 개의 정수가 진박이 좋아하는'평균수'인지 나타낸다.
샘플 입력:

1 50
1 1000

샘플 출력:

4
135

생각:
이 범위 내의 각 수 X에 대해 다음과 같이 분석한다.
X의 각 수를 분할하여 각 비트의 및 S를 계산하고 S/2의 몇 개의 수를 찾을 수 있는지 깊이 있게 시도합니다.찾으면 평균 수입니다.
코드:

#include <stdio.h>
#include <stdlib.h>
 
#define N 64
 
int visited[N];
int n;
int a[N];
int sum;
int aver;
 
void parse(int i)
{
    n = 0;
    while(i)
    {
        a[n++] = i%10;
        i /= 10;
    }
}
 
void init()
{
    int i;
    for (i=0; i<n; i++)
        visited[i] = 0;
}
 
int cmp(const void *a, const void *b)
{
    return (*(int *)a < *(int *)b) * 2 - 1;
}
 
int choose(int cur, int n)
{
    if (cur == aver)
        return 1;
    if (cur > aver || n == 0)
        return 0;
    if (!visited[n-1])
    {
        visited[n-1] = 1;
        if (choose(cur+a[n-1], n-1) == 1)
            return 1;
        visited[n-1] = 0;
    }
    if (choose(cur, n-1) == 1)
        return 1;
    return 0;
}
 
int main()
{
    int i, j;
    int x, y;
    int count;
 
    while(scanf("%d%d", &x, &y) != EOF)
    {
        count = 0;
        for (i=x; i<=y; i++)
        {
            parse(i);
            qsort(a, n, sizeof(a[0]), cmp);
            sum = 0;
            for (j=0; j<n; j++)
                sum += a[j];
            if (sum%2 == 1)
                continue;
            init();
            aver = sum/2;
            if (choose(0, n) == 1)
                count ++;
        }
        printf("%d
", count);
    }
    return 0;
}
/**************************************************************
    Problem: 1358
    User: liangrx06
    Language: C
    Result: Accepted
    Time:260 ms
    Memory:912 kb
****************************************************************/