2015-06-24
1121
Элементами массива 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] (существует такое х, что для всякого 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]]);Задача №10
На пpямой своими концами заданы N отpезков и точка X. Опpеделить, пpинадлежит ли точка межотpезочному интеpвалу. Если да, то указать концевые точки этого интервала. Если нет, то найти,
А. Какому количеству отpезков пpинадлежит точка.
