解題區►解題區 - UVa

UVa 10571 - Products

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

  • 所有使用的數字不可重複
  • 每一行、每一列恰好使用兩個數字
  • 每行、每列的非零數字相乘恰好符合需求

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
2 12
3 8
3
5 8 18
2 30 12
5
54 6 12 20 88
18 9 132 32 10
10
2 12 30 56 90 132 182 240 306 380
19 36 51 64 75 84 91 96 99 200
0

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1   3
2   4
1   2   0
5   0   6
0   4   3
6   3   0   0   0
9   0   1   0   0
0   0  12   0  11
0   0   0   4   8
0   2   0   5   0
1   0   0   0   0   0   0   0   0  19
2   0   0   0   0   0   0   0  18   0
0   3   0   0   0   0   0   0  17   0
0   4   0   0   0   0   0  16   0   0
0   0   5   0   0   0   0  15   0   0
0   0   6   0   0   0  14   0   0   0
0   0   0   7   0   0  13   0   0   0
0   0   0   8   0  12   0   0   0   0
0   0   0   0   9  11   0   0   0   0
0   0   0   0  10   0   0   0   0  20

Solution

直接每一行每一行搜索，過程中預處理所有因數分解，並且同時剪枝不合法的列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h> 
#include <vector>
#include <assert.h>
using namespace std;
int N, X[16] = {}, Y[16] = {};
int g[16][16] = {};
vector<int> row[16];
vector<int> f[1024];
int used[1024] = {};
int dfs(int idx) {
	if (idx == N) {
		for (int i = 0; i < N; i++, puts("")) {
			for (int j = 0; j < N; j++) {
				if (j) putchar(' ');
				printf("%3d", g[j][i]);
			}
		}
		return 1;
	}
	for (int p = 0; p < N; p++) {
		for (int q = p + 1; q < N; q++) {
			if (row[p].size() == 2 || row[q].size() == 2)
				continue;
			for (int i = 0; i < f[X[idx]].size(); i++) {
				int a, b, ok = 1;
				a = f[X[idx]][i];
				b = X[idx]/a;
				if (used[a] || used[b] || a == b) 
					continue;
				g[idx][p] = a, g[idx][q] = b;
				used[a] = used[b] = 1;
				row[p].push_back(a);
				row[q].push_back(b);
				if (row[p].size() == 2 && row[p][0] * row[p][1] != Y[p]) 
					ok = 0;
				if (row[q].size() == 2 && row[q][0] * row[q][1] != Y[q]) 
					ok = 0;
				if (Y[p]%a || Y[q]%b)	
					ok = 0;
				if (ok) {
					if (dfs(idx + 1)) {
						g[idx][p] = 0, g[idx][q] = 0;
						row[p].pop_back();
						row[q].pop_back();
						used[a] = used[b] = 0;
						return 1;
					}
				}
				g[idx][p] = 0, g[idx][q] = 0;
				used[a] = used[b] = 0;
				row[p].pop_back();
				row[q].pop_back();
			}	
		}
	}
	return 0;
}
int main() {
	for (int i = 1; i < 1024; i++) {
		for (int j = 1; j <= i; j++) {
			if (i%j == 0)
				f[i].push_back(j);
		}
	}
	while (scanf("%d", &N) == 1 && N) {
		for (int i = 0; i < N; i++)
			scanf("%d", &X[i]);
		for (int i = 0; i < N; i++)
			scanf("%d", &Y[i]);
		assert(dfs(0) == 1);
		puts("");
	}
	return 0;
}
/*
2
2 12
3 8
3
5 8 18
2 30 12
5
54 6 12 20 88
18 9 132 32 10
10
2 12 30 56 90 132 182 240 306 380
19 36 51 64 75 84 91 96 99 200
0
*/