Problem Solving►UVa

UVa 129 - Krypton Factor

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

給可使用的字母和字串順序，求出要求的 hard 字串。
p.s. 每4個字元一組，每16組一列。

Solution

要注意 n 不是長度是順序。
ex.

3 2
ABA

4 2
B

5 2
BA

6 2
BAB

至於比較的部分，則是從新增的字元開始依序向前增長比較。
從長度為 1 的後綴到長度為 目前長度/2 的字串一一比較其相鄰子字串，都不相同才為 hard。

max = idx >> 1
for (int len = 1; len <= max; len++)
{
    hard = false;
    for (j = 0; j < len; j++)
        if (ans[idx - j] != ans[idx - len - j])
        {
            hard = true;
            break;
        }

    if (!hard)
        break;
}

Code

UVa 129UVa 129 - Krypton Factor
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

#include<cstdio>

int count, n;
bool backtracking(int L, int idx);
int main()
{
    int l;
    while (scanf("%d%d", &n, &l) && n&&l)
    {
        count = 0;
        backtracking(l, 0);
    }

    return 0;
}
bool backtracking(int L, int idx)
{
    static int ans[81];

    if (count == n)
    {
        int f = 0, g = 0;
        for (int i = 1; i <= idx; i++, f++)
        {
            if (f == 4)
            {
                g++;
                if (g == 16)
                {
                    putchar('\n');
                    g = 0;
                }
                else
                    putchar(' ');
                f = 0;
            }

            putchar('A' + ans[i]);
        }

        printf("\n%d\n", idx);
        return true;
    }

    idx++;
    int max = idx >> 1, j;
    for (int i = 0; i < L; i++)
    {
        bool hard = true;
        ans[idx] = i;
        
        for (int len = 1; len <= max; len++)
        {
            hard = false;
            for (j = 0; j < len; j++)
                if (ans[idx - j] != ans[idx - len - j])
                {
                hard = true;
                break;
                }

            if (!hard)
                break;
        }

        if (hard)
        {
            count++;
            if (backtracking(L, idx))
                return true;
        }
    }

    return false;
}