| blob | bbea85e8e4eed4ede80de45ae1f562e96f21a5b3 |
1 {$apptype console}\r
2 {$r+,o-,q-}\r
3 {$minstacksize 30000000}\r
4 uses\r
5 SysUtils, Math, testlib;\r
6 \r
7 const\r
8 PCOUNT = ord('Z') - ord('L') + 1;\r
9 \r
10 var\r
11 n : integer;\r
12 pa, ja : integer;\r
13 processes : array[1..100, 1..2] of integer;\r
14 i : integer;\r
15 r1, r2 : string;\r
16 desc : array[1..100, 1..2] of integer; \r
17 r1n, r2n : integer;\r
18 actualLength : integer;\r
19 edge : array[0..PCOUNT - 1, 0..PCOUNT - 1] of boolean;\r
20 \r
21 function computeWaitingChain : integer;\r
22 var\r
23 a : array[0..65536, 0..15] of integer;\r
24 i, j, k : integer;\r
25 s : string;\r
26 l : integer;\r
27 begin\r
28 for i := 0 to (1 shl PCOUNT) - 1 do begin\r
29 for j := 0 to PCOUNT - 1 do begin\r
30 a[i][j] := -1;\r
31 end;\r
32 end;\r
33 \r
34 for i := 0 to PCOUNT - 1 do begin\r
35 a[1 shl i][i] := 0;\r
36 end; \r
37 for i := 0 to (1 shl PCOUNT) - 1 do begin\r
38 for j := 0 to PCOUNT - 1 do begin\r
39 if (a[i][j] = -1) then begin\r
40 continue;\r
41 end;\r
42 for k := 0 to PCOUNT - 1 do begin\r
43 if (edge[j][k]) then begin\r
44 if ((i or (1 shl k)) = i) then begin\r
45 s := '';\r
46 for l := 0 to PCOUNT - 1 do begin\r
47 if ((i or (1 shl l)) = i) then begin\r
48 s := s + ' ' + chr(ord('L') + l);\r
49 end;\r
50 end; \r
51 quit(_wa, 'System deadlocks while trying to work with resources' + s);\r
52 end else begin\r
53 a[i or (1 shl k)][k] := max(a[i][j] + 1, a[i or (1 shl k)][k]);\r
54 end;\r
55 end;\r
56 end;\r
57 end;\r
58 end;\r
59 result := -1;\r
60 for i := 0 to (1 shl PCOUNT) - 1 do begin\r
61 for j := 0 to PCOUNT - 1 do begin\r
62 result := max(result, a[i][j]);\r
63 end;\r
64 end;\r
65 dec(result);\r
66 end;\r
67 \r
68 begin\r
69 n := inf.readInteger();\r
70 for i := 1 to n do begin\r
71 r1 := inf.readWord(BLANKS, BLANKS); \r
72 r2 := inf.readWord(BLANKS, BLANKS); \r
73 processes[i][1] := ord(r1[1]) - ord('L');\r
74 processes[i][2] := ord(r2[1]) - ord('L');\r
75 end; \r
76 ja := ans.readInteger();\r
77 pa := ouf.readInteger();\r
78 if (pa > ja) then begin\r
79 quit(_wa, format('Participant has longer waiting chain: jury has %d, participant has %d', [ja, pa]));\r
80 end;\r
81 for i := 1 to n do begin\r
82 r1 := ouf.readWord(BLANKS, BLANKS); \r
83 if (length(r1) > 1) then begin\r
84 quit(_wa, format('Invalid resource for process %d: %s', [i, r1]));\r
85 end;\r
86 if (r1[1] < 'L') or (r1[1] > 'Z') then begin\r
87 quit(_wa, format('Invalid resource for process %d: %s', [i, r1]));\r
88 end;\r
89 r2 := ouf.readWord(BLANKS, BLANKS); \r
90 if (length(r2) > 1) then begin\r
91 quit(_wa, format('Invalid resource for process %d: %s', [i, r1]));\r
92 end;\r
93 if (r2[1] < 'L') or (r2[1] > 'Z') then begin\r
94 quit(_wa, format('Invalid resource for process %d: %s', [i, r1]));\r
95 end;\r
96 r1n := ord(r1[1]) - ord('L');\r
97 r2n := ord(r2[1]) - ord('L');\r
98 if ((r1n = processes[i][1]) and (r2n <> processes[i][2])) or\r
99 ((r1n = processes[i][2]) and (r2n <> processes[i][1])) then begin\r
100 quit(_wa, format('Invalid set of resources for process %d: (%s, %s) instead of (%s, %s)', [i, r1, r2, '' + chr(ord('L') + processes[i][1]), '' + chr(ord('L') + processes[i][1])])); \r
101 end; \r
102 desc[i][1] := r1n;\r
103 desc[i][2] := r2n;\r
104 end;\r
105 for i := 1 to n do begin\r
106 edge[desc[i][1]][desc[i][2]] := true;\r
107 end;\r
108 actualLength := computeWaitingChain();\r
109 if (actualLength <> pa) then begin\r
110 quit(_wa, format('Participant reported wrong wainting chain length: %d, but actual is %d', [pa, actualLength]));\r
111 end;\r
112 if (pa < ja) then begin\r
113 quit(_fail, format('Participant has better answer: pa = %d, ja = %d', [pa, ja]));\r
114 end;\r
115 quit(_ok, format('%d processes, length of waiting chain = %d', [n, ja]));\r
116 end.\r