解題區/解題區 - UVa

UVa 1594 - Ducci Sequence

contents

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

Problem

將序列根據步驟轉換，是否會產生迴圈或者是回歸到 0。

Sample Input

1
2
3
4
5
6
7
8
9
4 
4 
8 11 2 7 
5 
4 2 0 2 0 
7 
0 0 0 0 0 0 0 
6 
1 2 3 1 2 3

Sample Output

1
2
3
4
ZERO 
LOOP 
ZERO 
LOOP

Solution

用 hash (RS hashing) 來壓縮一下儲存的方式，碰撞的機率應該是挺低的。

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <map>
#include <algorithm>
using namespace std;
int nextSeq(int A[], int n) {
    int B[32];
    A[n] = A[0];
    for (int i = 0; i < n; i++)
        B[i] = abs(A[i] - A[i+1]);
    for (int i = 0; i < n; i++)
        A[i] = B[i];
    return 1;
}
int main() {
    int testcase, n, A[32];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        map<int, int> R;
        do {
            int ok = 1, hash = 0;
            int a = 63689, b = 378551;
            for (int i = 0; i < n; i++) {
                hash = hash * a + A[i], a = a * b;
                ok &= A[i] == 0;
            }
            if (ok) {
                puts("ZERO");
                break;
            }
            int &f = R[hash];
            if (f) {
                puts("LOOP");
                break;
            }
            f = 1;
        } while (nextSeq(A, n));
    }
    return 0;
}
/*
 4
 4
 8 11 2 7
 5
 4 2 0 2 0
 7
 0 0 0 0 0 0 0
 6
 1 2 3 1 2 3
 */