RAID (Redundant Array of Inexpensive Disks) is a technique which uses multiple disks to store data. By storing the data on more than one disk, RAID is more fault tolerant than storing data on a single disk. If there is a problem with one of the disks, the system can still recover the original data provided that the remaining disks do not have corresponding problems.
One approach to RAID breaks data into blocks and stores these blocks on all but one of the disks. The remaining disk is used to store the parity information for the data blocks. This scheme uses vertical parity in which bits in a given position in data blocks are exclusive ORed to form the corresponding parity bit. The parity block moves between the disks, starting at the first disk, and moving to the next one in order. For instance, if there were five disks and 28 data blocks were stored on them, they would be arranged as follows:
With this arrangement of disks, a block size of two bits and even parity, the hexadecimal sample data 6C7A79EDFC (01101100 01111010 01111001 11101101 11111100 in binary) would be stored as:
If a block becomes unavailable, its information can still be retrieved using the information on the other disks. For example, if the first bit of the first block of disk 3 becomes unavailable, it can be reconstructed using the corresponding parity and data bits from the other four disks. We know that our sample system uses even parity:
0 ⊕ 0⊕? ⊕ 1 ⊕ 0 = 0
So the missing bit must be 1.
An arrangement of disks is invalid if a parity error is detected, or if any data block cannot be reconstructed because two or more disks are unavailable for that block.
Write a program to report errors and recover information from RAID disks.
Input
The input consists of several disk sets.
Each disk set has 3 parts. The first part of the disk set contains three integers on one line: the first integer d, 2 ≤ d ≤ 6, is the number of disks, the second integer s, 1 ≤ s ≤ 64, is the size of each block in bits, and the third integer b, 1 ≤ b ≤ 100, is the total number of data and parity blocks on each disk. The second part of the disk set is a single letter on a line, either ‘E’ signifying even parity or ‘O’ signifying odd parity. The third part of the disk set contains d lines, one for each disk, each holding s × b characters representing the bits on the disk, with the most significant bits first. Each bit will be specified as ‘0’ or ‘1’ if it holds valid data, or ‘x’ if that bit is unavailable. The end of input will be a disk set with d = 0. There will be no other data for this set which should not be processed.
Output
For each disk set in the input, display the number of the set and whether the set is valid or invalid. If the set is valid, display the recovered data bits in hexadecimal. If necessary, add extra ‘0’ bits at the end of the recovered data so the number of bits is always a multiple of 4. All output shall be appropriately labeled.
Sample Input
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
Disk set 1 is valid, contents are: 6C7A79EDFC
Disk set 2 is invalid.
Disk set 3 is valid, contents are: FFC
题目类型：简单字符处理
算法分析：判断数据没损坏时校验对是否合法和数据损坏时是否最多只有一个数据损坏
|
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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 |
/************************************************** filename :e.cpp author :maksyuki created time :2017/12/27 20:59:10 last modified :2017/12/27 22:15:38 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; char aa[166][166][166]; char ans[166*166*166]; int d, s, b, id = 1; char par; //1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 //1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 void print_ans() { memset(ans, 0, sizeof(ans)); bool is_first = true; for(int i = 1; i <= b; i++) { for(int j = 1; j <= d; j++) { if(i % d == 0 && j == d) continue; if(i % d != 0 && (j == i % d)) continue; if(is_first) { is_first = false; strcpy(ans, aa[i][j]); } else strcat(ans, aa[i][j]); } } int len = strlen(ans); int alen = len; if(len % 4) alen = (len / 4) * 4 + 4; for(int i = len; i <= alen; i++) ans[i] = '0'; ans[alen] = 0; for(int i = 0; i < alen; i += 4) { int val = 0; for(int j = i, cnt = 1; cnt <= 4; j++, cnt++) val = val * 2 + (ans[j] - '0'); if(val < 10) printf("%c", val + '0'); else printf("%c", val - 10 + 'A'); } puts(""); } int main() { #ifdef LOCAL CFF; //CFO; #endif while(scanf("%d", &d) != EOF) { if(!d) break; scanf(" %d %d", &s, &b); scanf(" %c", &par); char tmp[166*166]; for(int i = 1; i <= d; i++) { scanf(" %s", tmp); for(int j = 1, len = 0; j <= b; j++, len += s) { strncpy(aa[j][i], tmp + len, s); aa[j][i][s] = 0; } } int org_par; if(par == 'E') org_par = 0; else org_par = 1; bool is_valid = true; for(int i = 1; i <= b; i++) { for(int j = 0; j < s; j++) { int cnt = 0, tmpv = -1, cnt_pos = -1; bool is_first = true; for(int k = 1; k <= d; k++) { if(aa[i][k][j] != 'x') { if(is_first) { is_first = false; tmpv = aa[i][k][j] - '0'; } else tmpv ^= (aa[i][k][j] - '0'); } else { cnt++; cnt_pos = k; } } if(cnt >= 2 || (cnt == 0 && tmpv != org_par)) { is_valid = false; break; } if(cnt == 1) aa[i][cnt_pos][j] = char ('0' + (tmpv ^ org_par)); } if(!is_valid) break; } printf("Disk set %d is ", id++); if(!is_valid) printf("invalid.\n"); else { printf("valid, contents are: "); print_ans(); } } return 0; } |