P.6603宝くじ

11280 ワード
CodingTest テキストリンク

6603宝くじ


タイムアウトメモリ制限回答を提出した人の回答正解率1秒128 MB 390321761487754.653%

質問する


ドイツまたは{1,2,...,49}から6つの数字を選択します.
宝くじ番号を選択する最も有名な戦略は、49種類の数字の中からk(k>6)個の数字を選択し、集合Sを作成し、数字のみに基づいて番号を選択することである.
例えば、k=8、S={1、2、3、5、8、13、21、34}の場合、この集合Sで選択可能な総数は28種類である.([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
集合Sとkが与えられると,すべての選択数を求めるプログラムを作成する.

入力


入力は、複数のテスト・インスタンスから構成されます.各テストボックスは1行で構成されています.1番目の数はk(6入力した最後の行にはゼロが表示されます.

しゅつりょく


各テスト・インスタンスは、選択数のすべてのメソッドを出力します.このとき、辞書順に出力します.
各テストボックスの間に空の行が出力されます.

入力例1


7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

サンプル出力1


1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

コード#コード#

import java.io.*;
import java.util.Arrays;

public class P_6603 {

    static int              k;
    static int[]            perm;
    static int[]            lotto_num;
    static BufferedWriter   bw;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (true) {
            int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            k = info[0];
            if (k == 0) break;

            perm = Arrays.copyOfRange(info, 1, info.length);
            lotto_num = new int[6];

            find_lotto(0, 0);
            bw.newLine();
        }
        bw.flush();
    }

    public static void find_lotto(int pos, int idx) throws IOException {
        if (pos == 6) {
            for (int num : lotto_num) bw.write(num + " ");
            bw.newLine();
        }
        else {
            for (int i = idx; i < k; i++) {
                lotto_num[pos] = perm[i];
                find_lotto(pos + 1, i + 1);
            }
        }
    }
}

コードの説明


バックグラウンドトラッキングを利用しました.
find lotto関数の最初のパラメータは、lotto num配列で現在参照されている部分(ロット番号を付ける部分)を表し、2番目のパラメータidxは、与えられたlotto番号にどの番号を付けるべきかを表します.
posが6の場合、lotto numはすべて充填されるので、バッファに使用されます.
posが6でない場合、まだlotto numが埋め込まれていないのでfor文に入ります.文の最初の先頭はパラメータに渡されたidxから始まるからです.また、idxはfind lottoを呼び出すたびにi+1に更新され、同じ番号を繰り返してlotto numに入れないようにする.
for文ではlotto numの一部が埋め込まれた後,枝分かれ数を増やすように設計されている.
Google AnalyticsのGTAGを次へ加える方法.を使ったJS🎉
真剣に、APISでリストを使用停止