Hiho 303週H国の身分証明書番号I

H国の身分証明書番号I

時間制限:10000 ms単点時間制限:1000 msメモリ制限:256 MB H国の身分証明書番号がNビットの正の整数であることを記述する(トップは0ではない).さらに、偽造防止の必要性により、Nビットの正の整数が正当な身分証明書番号であり、各ビット数がK以下である場合のみ、任意の隣接する2ビット数の積もK以下である.
例えばK=5の場合、101、211、210等はいずれも合法的な番号であり、106、123、421等はいずれも不法な番号である.
正の整数NおよびKを指定し、すべての合法的な番号を小さいから大きいまで出力します.
2つの整数NとKを入力します.
80%のデータに対して,1≦N≦6であった.
100%のデータに対して,1≦N≦9,1≦K≦5であった.
出力は、すべての合法的なNビット番号を小さい順に出力し、各番号が1行を占める.

サンプル入力

2 4

サンプル出力

10 11 12 13 14 20 21 22 30 31 40 41

考え方:

条件に合致するすべての条件を出力する必要があることは明らかであるため、dfsを利用して検索することができる.k≦5 kleq 5 k≦5であるため、選択されるたびに選択された数字はテーマの要求に合致する必要がある.p p pを利用して前の選択された数字を表し、xは現在選択された数字を表すと仮定すると、xはp

#include 
#include 
#include 

using namespace std;

int nums[10] = {0};


void dfs(int head, int pos, int len, int k, int pre)
{
	if (pos == len) {
		cout << head;
		for (int i = 1; i < len; ++i)
			cout << nums[i];
		cout << endl;
		return;
	}
	int n = (pre == 0? k : k/pre);
	for ( int j = 0; j <= n; ++j) {
		if (pre*j <= k) {
			nums[pos] = j;
			dfs(head, pos+1, len, k, j);
			nums[pos] = -1;
		}
	}

	return;
}

void solve()
{
	int n, k;
	cin >> n >> k;
	int flag = 0;
	for (int i = 1; i <= k; ++i) {
		for (int j = 0; j < 10; ++j)
			nums[j] = -1;
		dfs(i, 1, n, k, i);
		
	}

}

int main()
{

	solve();
	return 0;
}