3 {$minstacksize 30000000}
\r
5 SysUtils, Math, testlib;
\r
8 PCOUNT = ord('Z') - ord('L') + 1;
\r
13 processes : array[1..100, 1..2] of integer;
\r
16 desc : array[1..100, 1..2] of integer;
\r
18 actualLength : integer;
\r
19 edge : array[0..PCOUNT - 1, 0..PCOUNT - 1] of boolean;
\r
21 function computeWaitingChain : integer;
\r
23 a : array[0..65536, 0..15] of integer;
\r
28 for i := 0 to (1 shl PCOUNT) - 1 do begin
\r
29 for j := 0 to PCOUNT - 1 do begin
\r
34 for i := 0 to PCOUNT - 1 do begin
\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
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
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
51 quit(_wa, 'System deadlocks while trying to work with resources' + s);
\r
53 a[i or (1 shl k)][k] := max(a[i][j] + 1, a[i or (1 shl k)][k]);
\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
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
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
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
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
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
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
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
105 for i := 1 to n do begin
\r
106 edge[desc[i][1]][desc[i][2]] := true;
\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
112 if (pa < ja) then begin
\r
113 quit(_fail, format('Participant has better answer: pa = %d, ja = %d', [pa, ja]));
\r
115 quit(_ok, format('%d processes, length of waiting chain = %d', [n, ja]));
\r