낙 곡 P1118 [USACO06FEB] 디지털 삼각형 뒤로 Digit Su...

제목 설명 FJ 와 그의 소 는 정신 게임 을 즐 길 수 있 습 니 다. 그들 은 특정 순서 로 1 에서 N (1 < = N < = 10) 까지 숫자 를 적 고, 그 다음 에 인접 한 숫자 를 합 쳐 서 하나의 숫자 만 남 을 때 까지 이 를 반복 합 니 다. 예 를 들 어, 게임 의 한 인 스 턴 스 (N = 4) 는 다음 과 같 을 수 있 습 니 다.

3   1   2   4
  4   3   6
    7   9
     16

Behind FJ’s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately,game is a bit above FJ 's mental arithmetic capabilities. Write a program to help FJ play the game and keep up with the cows. 1 ~ N 의 배열 a [i] 를 쓰 고 매번 인접 한 두 개의 수 를 더 해 새로운 서열 을 구성 한 다음 에 새로운 서열 을 이렇게 조작 합 니 다.분명히 매번 구 성 된 서열 은 지난번 의 서열 보다 길이 가 1 이 적 고 숫자 위치 만 남 을 때 까지 적 었 다.다음은 하나의 예 다. 3, 1, 2, 4, 3, 6, 7, 9, 16. 마지막 으로 16 이라는 숫자 를 얻 었 다.지금 은 거꾸로 게임 을 하고 싶 습 니 다. N 을 알 고 마지막 으로 얻 은 숫자의 크기 sum 을 알 고 있다 면 최초의 서열 a [i] 를 구 해 1 ～ N 의 배열 을 구 해 주세요.답 이 여러 가지 가능 하 다 면 사전 순서 가 가장 작은 것 을 출력 합 니 다.[color = red] 관리자 주석: 이 문제 의 설명 이 잘못 되 었 습 니 다. 여기 사전 순 서 는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 가 아니 라 1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9 [/ color] 입 출력 형식 입력 형식 입 니 다. 두 개의 정수 n, sum.출력 형식: 출력 은 사전 순서 가 가장 작은 줄 을 포함 합 니 다.풀 리 지 않 을 때 는 아무것도 출력 하지 마 세 요.(신기 하 다), 입 출력 사례 입력 사례 \ # 1: 4 16 출력 사례 \ # 1: 3 1 2 4 설명 40% 의 데이터, n ≤ 7;80% 의 데이터 에 대해 n ≤ 10;100% 의 데이터 에 대해 n ≤ 12, sum ≤ 12345.

/*
           a,b,c,d.,,,,,,
  n 4，  sum 1a+3b+3c+1d
  n 5，  sum 1a+4b+6c+4d+1e
  n 6，  sum 1a+5b+10c+10d+5e+1f 
       
                
*/
#include
#include
#include
#include

using namespace std;
int n, Sum ,C[20][20],a[14];
bool used[14];

void DFS(int step,int s){
    if(s > Sum) return;
    if(step == n + 1){
        if(s == Sum){
            for(int i=1; i<=n; ++i) printf("%d ",a[i]);
            exit(0);
        }
        return ;
    }
    for(int i=1; i<=n; ++i)
        if(!used[i]){
            a[step] = i;
            s += C[n][step] * i;
            used[i] = true;
            DFS(step + 1,s) ;
            used[i] = false;
            s -= C[n][step] * i;
        }
}

int main(int argc,char *argv[]){
    scanf("%d%d", &n ,&Sum);
    C[1][1] = 1;
    for(int i=2; i<=n; ++i)
        for(int j=1; j<=i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];

    DFS(1,0);
    return 0;
}