Задача 76256
|
|
 |
Условие
Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел:a: array [1..n] of array [1..m] of integer;
a[1][1]≤...≤a[1][m], ..., a[n][1]≤...≤a[n][m].
Известно, что существует число, входящее во все массивы
a[i] (существует такое x, что для всякого i из
1..n найдётся j из 1..m, для которого
a[i][j] = x). Найти одно из таких чисел х.
Решение
Введём массив b[1]...b[n], отмечающий начало "остающейся части" массивов a[1],...,a[n]. for k:=1 to n do begin
| b[k]:=1;
end;
eq := true;
for k := 2 to n do begin
| eq := eq and (a[1][b[1]] = a[k][b[k]]);
end;
{инвариант: оставшиеся части пересекаются, т.е. существует
такое х, что для всякого i из [1..n] найдётся j из [1..m],
не меньшее b[i], для которого a[i][j] = х; eq <=> первые
элементы оставшихся частей равны}
while not eq do begin
| s := 1; k := 1;
| {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]}
| while k <> n do begin
| | k := k + 1;
| | if a[k][b[k]] < a[s][b[s]] then begin
| | | s := k;
| | end;
| end;
| {a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]}
| b [s] := b [s] + 1;
| for k := 2 to n do begin
| | eq := eq and (a[1][b[1]] = a[k][b[k]]);
| end;
end;
writeln (a[1][b[1]]);
