解題區/解題區 - 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
*/