解題區/解題區 - UVa

UVa 509 - RAID

contents

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

Problem

參照《算法競賽入門經典》一書

一種磁碟儲存的機制，磁碟除了資料儲存，同時也會賦予檢查碼，來修正錯誤的資訊，即便能力相當有限，最多修正一個錯誤位元。

現在要求的工作是進行錯誤位元的復原，並且輸出 16 進制下的資料，如果資料不足 4 bits，則剩餘位元接補上 0。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
5 2 5
E
0001011111
0110111011
1011011111
1110101100
0010010111
3 2 5
E
0001111111
0111111011
xx11011111
3 5 1
O
11111
11xxx
x1111
0

Sample Output

1
2
3
Disk set 1 is valid, contents are: 6C7A79EDFC
Disk set 2 is invalid.
Disk set 3 is valid, contents are: FFC

Solution

這題很簡單，但是一直沒注意到陣列開太小而炸掉，我的預設記憶體不夠大而 WA。剩下的細節則注意錯誤位元如果是檢查碼就可以無視，而同時檢查碼只支持修正一個位元，如果需要修正兩個以上則表示無法復原。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
using namespace std;
char mem[128][65536];
int main() {
    int cases = 0;
    int D, S, B;
    char kind[8];
    while (scanf("%d %d %d", &D, &S, &B) == 3 && D) {
        scanf("%s", kind);
        for (int i = 0; i < D; i++)
            scanf("%s", mem[i]);
        int n = S * B, kv = kind[0] == 'E' ? 0 : 1;
        int err = 0;
        for (int i = 0, j = 0; i < n; i += S, j++) {
            j %= D;
            for (int p = i; p < i + S; p++) {
                int broken = 0, brokenPos = 0, XOR = 0;
                for (int k = 0; k < D; k++) {
                    if (mem[k][p] == 'x')
                        broken++, brokenPos = k;
                    else
                        XOR ^= mem[k][p] - '0';
                }
                if (broken >= 2)
                    err = 1;
                else if (broken == 1) {
                    if (brokenPos == j) {
                    } else {
                        mem[brokenPos][p] = '0' + (kv^XOR);
                    }
                } else {
                    if (XOR != kv)  err = 1;
                }
            }
        }
        printf("Disk set %d is ", ++cases);
        if (err) {
            puts("invalid.");
        } else {
            char buff[65536];
            memset(buff, '0', sizeof(buff));
            int m = 0;
            for (int i = 0, j = 0; i < n; i += S, j++) {
                j %= D;
                for (int k = 0; k < D; k++) {
                    if (k == j) continue;
                    for (int p = i; p < i + S; p++) {
                        buff[m++] = mem[k][p];
                    }
                }
            }
            printf("valid, contents are: ");
            for (int i = 0; i < m; i += 4) {
                int val = 0;
                val |= (buff[i + 0] - '0') << 3;
                val |= (buff[i + 1] - '0') << 2;
                val |= (buff[i + 2] - '0') << 1;
                val |= (buff[i + 3] - '0') << 0;
                printf("%X", val);
            }
            puts("");
        }
    }
    return 0;
}
/*
 
 5 2 5
 E
 xx01011111
 0110111011
 1011011111
 1110101100
 0010010111
 5 2 5
 E
 0001011111
 0110111011
 1011011111
 1110101100
 0010010111
 3 2 5
 E
 0001111111
 0111111011
 xx11011111
 3 5 1
 O
 11111
 11xxx
 x1111
 0
*/