[白俊]#1821秀たちの和

質問する

一番上の列には1からNまでの数字が書いてあります.そして、2行目からパスカルの三角形のように、上の2つを加算した値が格納されます.たとえば、Nが4で、一番上の行が3 1 2 4の場合、次の三角形が描画されます.

3 1 2 4
 4 3 6
  7 9
   16

Nと一番下の数字が与えられた場合、一番上の行の数字を求めるプログラムを作成してください.しかし、答えがいろいろある場合は、一番前のものを辞書順に印刷します.

入力

第1行は2つの整数N(1≦N≦10)とFを与える.Nは最上行数の個数を表し、Fは最下行数100000以下である.

しゅつりょく

最初の行では、三角形の一番上のN個の数字をスペースで区切って出力します.答えが存在しなければ入力できません.

入力例1

4 16

サンプル出力1

3 1 2 4

に答える

この問題はnext置換アルゴリズムを用いてすべての数の配列を求め,dfs(深さ優先探索)アルゴリズムを用いて最下位数を求め,入力と比較して答えを求める.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int[] arr;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int F = Integer.parseInt(input[1]);

        arr = new int[N];
        for(int i=1; i<=N; i++)
            arr[i-1] = i;

        if(F==sol(arr)) {
            for(int i=0; i<arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
            return ;
        }

        while(next_permutation()) {
            if(F==sol(arr)) {     //마지막 수가 일치하는 경우 수 배열 출력
                for(int i=0; i<arr.length; i++) {
                    System.out.print(arr[i]+" ");
                }
                return ;
            }
        }
    }

    public static int sol(int[] temp) {
        if(temp.length==2) {        //마지막 수 리턴
            return temp[0]+temp[1];
        }

        if(temp.length==1)  //입력이 1 1 인 경우
            return 1;

        int[] next = new int[temp.length-1];
        int i = 0;
        int j = 1;

        while(j<temp.length) {
            next[i] = temp[i]+temp[j];
            i++;
            j++;
        }

        return sol(next);
    }

    public static boolean next_permutation() {
        int i = arr.length-1;

        while(i>0 && arr[i]<=arr[i-1]) {
            i--;
        }

        if(i<=0) return false;

        int j = arr.length-1;

        while(arr[i-1]>=arr[j])
            j--;

        int temp = arr[j];
        arr[j] = arr[i-1];
        arr[i-1] = temp;

        j = arr.length-1;

        while(i<j) {
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i++;
            j--;
        }

        return true;
    }
}