Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
Дерево отрезков
|
|
Дерево отрезков - структура данных, которая позволяет реализовать с трудоемкостью O(log N) операции следующего типа:
Add(I, J, D) – изменение на величину D элементов массива в диапазоне индексов от I-го до J-го;
Update (I, J, V) – присвоение элементам массива в диапазоне индексов от I-го до J-го нового значения V;
Rsq(I, J) – нахождение суммы (Rmq – максимума) элементов массива в диапазоне индексов от I-го до J-го.
Обычно обеспечиваются совместно первая и третья либо вторая и третья функции. Объём дополнительно используемой памяти составляет O(N), или, если быть точным, не более 8N на каждую пару функций.
Распространенная аббревиатура Rsq расшифровывается как Range Sum Query, а Rmq как Range Maximum Query.
Обычный массив позволяет выполнить с минимальной трудоемкостью O(1) операцию изменения одного элемента, но указанные операции имеют трудоемкость O(N). Если они должны выполняться часто, то при большой размерности массива это оказывается недопустимым.
Рассмотрим сначала дерево отрезков для суммы. Пусть имеется массив A[1], A[2], …, A[N]. Построим бинарное дерево T следующим образом. Корень дерева будет храниться в элементе T[1] и содержать сумму элементов всего массива. Левый сын корня будет храниться в элементе T[2] и содержать сумму первой половины массива: A[1..N div2], а правый сын - в элементе T[3] и содержать сумму элементов A[N div 2+1..N]. В общем случае, если i-й элемент содержит сумму элементов с L-го по R-й, то его левым сыном будет элемент T[2*i] с суммой элементов A[L..(L+R) div 2], а правым – элемент T[2*i +1] с суммой A[(L+R) div 2+1..R]. Исключение, разумеется, составляют листья дерева - вершины, в которых L = R. Дерево состоит из 2N-1 вершин, строится с трудоемкостью O(N) и имеет высоту порядка O(log N).
Рассмотрим теперь операцию суммы на некотором отрезке индексов [L; R]. Мы встаем в корень дерева (i=1), и рекурсивно движемся вниз по этому дереву. Если в какой-то момент оказывается, что L и R совпадают с границами отрезка текущего элемента, то мы просто возвращаем значение текущего элемента T. Если же отрезок [L; R] целиком попадает в отрезок левого или правого сына текущего элемента, то мы рекурсивно вызываем себя из этого сына и найденное значение возвращаем. Наконец, если отрезок [L; R] частично принадлежит и отрезку левого сына, и отрезку правого сына, то делим его на два отрезка [L; M] и [M+1; R], где M = (L+R) div 2, и рекурсивно вызываем себя и для первого, и для второго отрезков, возвращая сумму найденных значений. В итоге вся операция суммирования работает за O (log N).
Теперь рассмотрим простейший вариант операции присвоения значения некоторому единственному элементу с индексомK. Будем спускаться по дереву от корня, ища тот лист, который содержит значение элемента A[K]. Когда мы найдём этот элемент, просто изменим соответствующее значение в массиве T и будем подниматься от текущего элемента обратно к корню, пересчитывая текущие значения T. Понятно, что таким образом мы изменим все значения в дереве, которые необходимо изменить. Общая трудоемкость составляет O(log N). Приведем реализацию описанных операций.
Procedure Build(i, L, R: longint);
{Построение дерева отрезков для суммы
i - номер вершины, L - нижняя граница в исходном массиве,
R - верхняя граница, первоначально 1 и N}
Var
m: longint;
Begin
if L=R then T[i]: =A[L]
else
begin
m: =(L+R) div 2;
Build(2*i, L, m);
Build(2*i+1, m+1, R);
T[i]: =T[2*i]+T[2*i+1];
end;
End;
Function Sum(L, R, i, Tl, Tr: longint): longint;
{L, R - интервал индексов в A для суммы - первоначально 1 и N,
Tl, Tr - границы поиска в массиве A, - первоначально 1 и N}
Var
m: longint;
Begin
if (L=Tl) and (R=Tr) then Sum: =T[i]
else
begin
m: =(Tl+Tr) div 2;
if R< =m then Sum: =Sum(L, R, 2*i, Tl, m)
else
if L> m then Sum: =Sum(L, R, 2*i+1, m+1, Tr)
else
Sum: =Sum(L, m, 2*i, Tl, m)+Sum(m+1, R, 2*i+1, m+1, Tr);
end;
End;
Procedure Update(Ind, NewVal, i, L, R: longint);
{одиночная модификация: в A[Ind] новое значение NewVal}
Var
m: longint;
Begin
if L=R then T[i]: =NewVal
else
begin
m: =(L+R) div 2;
if Ind< =m then Update(Ind, NewVal, 2*i, L, m)
else Update(Ind, NewVal, 2*i+1, m+1, R);
T[i]: =T[2*i]+T[2*i+1];
{пересчет значений при возврате из рекурсии}
end;
End;
Операция прибавления на отрезке реализуется сложнее одиночной модификации. Введем дополнительный массив Add размерности 2N – 1 и той же адресации, что и массив T. В i-м элементе будем хранить Add[i] - значение, которое нужно прибавить ко всем элементам этого отрезка. Если добавка распространяется не на все элементы, то это будет отражено в соответствующих вершинах поддерева с корнем I. Операция прибавления на отрезке [L; R] будет модифицировать эти значения, а операция суммирования на отрезке - просто добавлять к ответу все встретившиеся значения Add на пути от корня до вершин, которые представляют в совокупности отрезок [L; R].
Рекурсивная процедура Plus прибавления на отрезке имеет аргументы L, R, X, I, Tl, Tr. Здесь L и R описывают диапазон индексов исходного массива A, на котором к каждому элементу прибавляется значение X. Параметр Iопределяет индекс вершины в дереве T, содержащей диапазон индексов [Tl; Tr] исходного массива для поиска всех вершин дерева, которые описывают совместно отрезок [L; R]. Первоначально I = 1, что соответствует корню дерева. Значения Tl = 1 и Tr = N задают полный диапазон индексов исходного массива A. Значение X может быть как положительным, так и отрицательным. Порядок рекурсивных вызовов принципиально не меняется, что видно из текста процедуры Plus.
Procedure Plus(L, R, X, i, Tl, Tr: longint);
{в интервале индексов [L, R] к элементам A добавляется X}
Var
m: longint;
Begin
T[i]: =T[i]+X*(R-L+1);
if (L=Tl) and (R=Tr) then Add[i]: =Add[i]+X
else
begin
m: =(Tl+Tr) div 2;
if R< =m then Plus(L, R, X, 2*i, Tl, m)
else
if L> m then Plus(L, R, X, 2*i+1, m+1, Tr)
else
begin
Plus(L, m, X, 2*i, Tl, m);
Plus(m+1, R, X, 2*i+1, m+1, Tr);
end;
end;
End;
Рекурсивная функция суммирования имеет те же аргументы и строится по тому же принципу. Поскольку массив Addописывает изменение каждого элемента в диапазоне индексов [L; R], то общая добавка составляет сумму Add[i]*(R-L+1) по всем путям от корня дерева к вершинам, представляющим совместно весь диапазон [L; R].
Function Sum(L, R, i, Tl, Tr: longint): longint;
{L, R - интервал индексов для суммы,
Tl, Tr - границы поиска в дереве}
Var
m, h: longint;
Begin
if (L=Tl) and (R=Tr) then Sum: =T[i]
else
begin
m: =(Tl+Tr) div 2;
h: =Add[i]*(R-L+1);
if R< =m then Sum: =Sum(L, R, 2*i, Tl, m)+h
else
if L> m then Sum: =Sum(L, R, 2*i+1, m+1, Tr)+h
else
Sum: =Sum(L, m, 2*i, Tl, m)+Sum(m+1, R, 2*i+1, m+1, Tr)+h;
end;
End;
Трудоемкость обеих рассмотренных операций по-прежнему составляет O(log N).
Операция присвоения нового значения на диапазоне индексов реализуется с помощью дополнительного массива Val размерности 2N – 1 и той же адресации, что и массив T. Изначально массив Val заполняется некоторыми значениями, имеющими смысл ”неопределенность”. Если все элементы в текущем отрезке индексов массива T равны между собой, то соответствующий элемент массива Val примет это значение. При выполнении операции присвоения мы будем спускаться по дереву, как и ранее. Если в какой-то момент диапазон присваивания совпадет с границами текущего отрезка, то мы присвоим соответствующему элементу Val новое значение. При спуске необходимо отменять ранее определенные значения Val.
Операция суммирования тоже должна быть изменена. Если при спуске в какой-то момент встречается элемент Val, отличный от неопределенного, то спуск прекращается. Действительно, результат уже определен значением элемента Val. При продолжении спуска были бы получены неправильные, старые значения.
Приведем тексты программ для реализации описанных операций.
Procedure Update(L, R, NewVal, i, Tl, Tr: longint);
{в интервале индексов [L, R] в A[i] новое значение NewVal,
i-корень дерева отрезков}
Var
k, m: longint;
Begin
if (L=Tl) and (R=Tr) then
begin
Val[i]: =NewVal;
T[i]: =NewVal;
end
else
begin
k: =Val[i];
Val[i]: =-1;
if k< > -1 then
begin
Val[2*i]: =k; {спуск на уровень}
Val[2*i+1]: =k;
end;
m: =(Tl+Tr) div 2;
if R< =m then Update(L, R, NewVal, 2*i, Tl, m)
else
if L> m then Update(L, R, NewVal, 2*i+1, m+1, Tr)
else
begin
Update(L, m, NewVal, 2*i, Tl, m);
Update(m+1, R, NewVal, 2*i+1, m+1, Tr);
end;
T[i]: =T[2*i]+T[2*i+1];
{пересчет на обратном пути при выходе из рекурсии}
end;
End;
Function Sum(L, R, i, Tl, Tr: longint): longint;
{L, R - интервал индексов для суммы, i-корень дерева,
Tl, Tr - границы поиска в дереве}
Var
m: longint;
Begin
if (Val[i]< > -1) then Sum: =Val[i]*(R-L+1)
{все вершины дерева с корнем i имеют значение Val[i]}
else
if Tl=Tr then Sum: =T[i]
{дошли до листа без модификации значений}
else
begin
m: =(Tl+Tr) div 2;
if R< =m then Sum: =Sum(L, R, 2*i, Tl, m)
else
if L> m then Sum: =Sum(L, R, 2*i+1, m+1, Tr)
else
Sum: =Sum(L, m, 2*i, Tl, m)+Sum(m+1, R, 2*i+1, m+1, Tr);
end;
End;
Дерево отрезков для максимума (минимума) строится и используется аналогично. Тексты соответствующих процедур и функций будут приведены на примере решения следующей известной задачи, уже встречавшейся ранее.
Прямоугольники. На координатной плоскости задано N прямоугольников со сторонами, параллельными координатным осям. Найти площадь фигуры, получающейся в результате объединения прямоугольников.
Ввод из файла INPUT.TXT. В первой строке содержится значение N (1 ≤ N ≤ 100000). В каждой из следующих N строк – четыре целых числа Ai, Bi, Ci, Di через пробел, определяющие координаты левого верхнего и правого нижнего углов очередного прямоугольника (-109 ≤ Ai, Bi, Ci, Di ≤ 109).
Вывод в файл OUTPUT.TXT действительного числа с точностью до двух знаков после запятой – площади фигуры.
Пример
Ввод
5 15 25 5
0 10 20 0
Вывод
В [4] описано решение этой задачи для меньшей размерности. Нужно отсортировать координаты углов прямоугольников по возрастанию и использовать метод заметания. Будем продвигать вертикальную прямую слева направо, отмечая изменение длины сечения нашей фигуры по оси Y. При встрече точки, соответствующей левой стороне прямоугольника, длина сечения может увеличиться, а при встрече правой стороны прямоугольника уменьшиться. Очередная прибавка к площади составит произведение длины отрезка по оси X на длину сечения.
Длина сечения находится также методом заметания. Создадим еще один массив координат вершин прямоугольников, но уже в порядке возрастания координаты Y. Изменение длины сечения связано с добавлением или удалением отрезка по оси Y. Будем просматривать точки вершин уже в порядке возрастания по оси Y, поддерживая счетчик числа вложенных отрезков. При встрече левого конца отрезка к счетчику прибавляется единица, а на правом конце отрезка она вычитается. Если при некотором значении координаты Y счетчик оказался больше нуля, а при другом значении снова обратился в ноль, то разность значений должна добавиться в длину сечения.
Оценим трудоемкость этого метода. Быстрая сортировка координат по каждой оси имеет трудоемкость O(N log N). Для каждой новой точки по оси X потребуется перебрать точки сечения по оси Y. Общая трудоемкость метода составит O(N2). При заданной размерности описанный подход не годится.
На выручку приходит дерево отрезков. Создадим два массива, сортируя координаты углов прямоугольника по осям X и Y. В целях увеличения скорости вычислений свяжем оба массива ссылками, указав для каждого элемента одного массива соответствующий элемент другого массива.
Обозначим через Ymin и Ymax минимальное и максимальное значения координаты Y. Отрезок [Ymin; Ymax] окажется разделенным на N-1 отрезков S1, S2, …, SN-1. Каждая вертикальная сторона прямоугольника покрывает один или несколько таких отрезков.
Снова используем метод заметания, продвигая сканирующую прямую по оси X. Для каждого отрезка Si будем отмечать в счетчике Ai, сколько раз отрезок Si входит в сечение. Добавление и удаление стороны прямоугольника по оси Y, покрывающей отрезки Sk, Sk+1, …, Sm, вызовет увеличение или уменьшение на единицу счетчиков Ak, Ak+1, …, Am.
Организуем по массиву A1, A2, …, AN-1 дерево отрезков для минимума. Введем еще один дополнительный массив Lm размерности 2N – 1 и той же адресации, что и массив T. В i-м элементе будем хранить Lm[i] – суммарную длину отрезков в дереве с корнем i, на которых достигается минимум. Значения массива Lm модифицируются при изменении дерева. Если в корне всего дерева минимум равен нулю, то значение Lm[1] определяет суммарную длину отрезков Si, не входящих в сечение по оси Y. Тогда длину сечения составит величина Ymax - Ymin - Lm[1].
Поскольку каждое изменение элементов массива Ak, Ak+1, …, Am имеет трудоемкость O(log N), общая трудоемкость алгоритма оценивается величиной O(N log N). Ниже приводится полный текст программы.
Program Rectang;
Const
MM=420;
{максимальное количество прямоугольников -
почти предел для Turbo Pascal, в Delphi возможно и 200000}
Var
i, k, N, M: longint;
S: double; {площадь объединения прямоугольников}
X1, Y1: array[1..2*MM] of longint;
{X1, Y1 - координаты верхних левых и нижних правых углов,
отсортированных по X}
Ind: array [1..2*MM] of longint;
{Ind[i]-индекс в (X1, Y1) диагональной вершины прямоугольника}
X2, Y2: array[1..2*MM] of longint;
{координаты (X1, Y1), отсортированные по Y}
Ref1: array [1..2*MM] of longint;
{Ref1[i]-индекс в массиве (X2, Y2) элемента (X1[i], Y1[i])}
Ref2: array [1..2*MM] of longint;
{Ref2[i]-индекс в массиве (X1, Y1) элемента (X2[i], Y2[i])}
{Ref1, Ref2 для быстрой связи массивов (X1, Y1) и (X2, Y2)}
Q: array [1..8*MM] of longint; {дерево минимумов для A[i]}
Add: array [1..8*MM] of longint;
{Add[i] - модифицирующая добавка ко всем сыновьям вершины i}
Lm: array [1..8*MM] of longint;
{суммарные длины отрезков, где в дереве достигается MIN}
Ch: char;
c, d, L, R, V, W, XPred: longint;
Lx, Ly, Lmax: longint;
Fin, Fout: text;
Function Min(a, b: longint): longint;
Begin
if a< b then Min: =a
else Min: =b
End;
Function Max(a, b: longint): longint;
Begin
if a> b then Max: =a
else Max: =b
End;
Procedure Sort1(L, R: longint); {быстрая сортировка по X}
Var
i, j, k, x, y, w, a, b: longint;
Begin
i: =L; { нижний индекс }
j: =R; { верхний индекс }
k: =(L+R) div 2;
x: =X1[k]; y: =Y1[k];
Repeat
While (X1[i]< x) or
((X1[i]=x) and (Y1[i]< y)) do i: =i+1;
{для одного значения X выбор по возрастанию Y позволяет
рассмотреть закрывающую сторону прямоугольника раньше}
While (X1[j]> x) or
((X1[j]=x) and (Y1[j]> y)) do j: =j-1;
if i< =j then
begin
w: =X1[i]; X1[i]: =X1[j]; X1[j]: =w;
w: =Y1[i]; Y1[i]: =Y1[j]; Y1[j]: =w;
a: =Ind[i]; b: =Ind[j];
if (a< > j) or (b< > i) then {меняются местами не противоположные углы прямоугольника}
begin
Ind[i]: =b; Ind[j]: =a;
Ind[a]: =j; Ind[b]: =i;
end;
i: =i+1; j: =j-1
end
Until i> j;
if L< j then Sort1(L, j);
if i< R then Sort1(i, R);
End;
Procedure Sort2(L, R: longint); {быстрая сортировка по Y}
Var
i, j, y, w, a, b: longint;
Begin
i: =L; { нижний индекс }
j: =R; { верхний индекс }
y: =Y2[(L+R) div 2];
Repeat
While Y2[i]< y do i: =i+1;
While Y2[j]> y do j: =j-1;
if i< =j then
begin
w: =Y2[i]; Y2[i]: =Y2[j]; Y2[j]: =w;
w: =X2[i]; X2[i]: =X2[j]; X2[j]: =w;
a: =Ref2[i]; b: =Ref2[j];
w: =Ref2[i]; Ref2[i]: =Ref2[j]; Ref2[j]: =w;
Ref1[a]: =j; Ref1[b]: =i;
i: =i+1; j: =j-1
end
Until i> j;
if L< j then Sort2(L, j);
if i< R then Sort2(i, R);
End;
Procedure Build(i, L, R: longint);
{построение дерева минимумов по нулевому массиву}
{i - номер вершины, L - нижняя граница, R - верхняя граница
Lm[i]-сумма длин интервалов с MIN значением для i-й вершины}
Var
m: longint;
Begin
if L=R then Lm[i]: =Y2[L+1]-Y2[L]
else
begin
m: =(L+R) div 2;
Build(2*i, L, m);
Build(2*i+1, m+1, R);
Lm[i]: =0;
if Q[i]=Q[2*i] then {модифицирующих добавок сначала нет}
Lm[i]: =Lm[i]+Lm[2*i];
if Q[i]=Q[2*i+1] then
Lm[i]: =Lm[i]+Lm[2*i+1];
end;
End;
Function Minim(L, R, i, Tl, Tr: longint): longint;
{поиск минимума элементов массива по интервалу индексов}
{L, R - интервал индексов для минимума,
i – индекс корня для поиска в дереве, Tl, Tr - границы поиска}
Var
m: longint;
Begin
if (L=Tl) and (R=Tr) then Minim: =Q[i]
else
begin
m: =(Tl+Tr) div 2;
if R< =m then Minim: =Minim(L, R, 2*i, Tl, m)+Add[i]
else
if L> m then Minim: =Minim(L, R, 2*i+1, m+1, Tr)+Add[i]
else
Minim: =Min(Minim(L, m, 2*i, Tl, m), Minim(m+1, R, 2*i+1, m+1, Tr))+
Add[i];
end;
End;
Function Long(L, R, i, Tl, Tr: longint): longint;
{сумма нулевых отрезков, (L, R) - интервал индексов для поиска,
i – индекс корня для поиска в дереве, (Tl, Tr) - границы поиска}
Var
m: longint;
Begin
if (L=Tl) and (R=Tr) then
if Q[i]=0 then Long: =Lm[i] {если MIN=0}
else Long: =0
else
begin
m: =(Tl+Tr) div 2;
if R< =m then Long: =Long(L, R, 2*i, Tl, m)
else
if L> m then Long: =Long(L, R, 2*i+1, m+1, Tr)
else
Long: =Long(L, m, 2*i, Tl, m)+Long(m+1, R, 2*i+1, m+1, Tr);
end;
End;
Procedure Plus(L, R, X, i, Tl, Tr: longint);
{на отрезке (Y2[L], Y2[R]) добавление значения X в A[i] для Min,
модификация массива Lm - суммы длин отрезков с Min}
Var
m: longint;
Begin
if (L=Tl) and (R=Tr) then
begin
Q[i]: =Q[i]+X;
Add[i]: =Add[i]+X;
end
else
begin
m: =(Tl+Tr) div 2;
if R< =m then Plus(L, R, X, 2*i, Tl, m)
else
if L> m then Plus(L, R, X, 2*i+1, m+1, Tr)
else
begin
Plus(L, m, X, 2*i, Tl, m);
Plus(m+1, R, X, 2*i+1, m+1, Tr);
end;
Q[i]: =Min(Q[2*i], Q[2*i+1])+Add[i];
{Add[i]-добавка для каждого элемента в интервале
индексов вершины i, т.е. для всех потомков i}
Lm[i]: =0;
if Q[i]=Q[2*i]+Add[i] then
Lm[i]: =Lm[i]+Lm[2*i];
if Q[i]=Q[2*i+1]+Add[i] then
Lm[i]: =Lm[i]+Lm[2*i+1];
end;
End;
Begin
Assign(Fin, 'input.txt');
Reset(Fin);
ReadLn(Fin, M);
N: =2*M; {количество вершин прямоугольников}
For i: =1 to M do
begin
k: =2*(i-1)+1;
ReadLn(Fin, X1[k], Y1[k], X1[k+1], Y1[k+1]);
Ind[k]: =k+1; {связь противоположных вершин прямоугольников}
Ind[k+1]: =k;
end;
Close(Fin);
Sort1(1, N); {сортировка точек (X1, Y1) по координате X}
For k: =1 to N do
begin
X2[k]: =X1[k];
Y2[k]: =Y1[k];
Ref1[k]: =k; {Ref1[i]-индекс (X1[i], Y1[i]) в массиве (X2, Y2)}
Ref2[k]: =k; {Ref2[i]-индекс (X2[i], Y2[i]) в массиве (X1, Y1)}
end;
Sort2(1, N); {сортировка точек (X2, Y2) по координате Y}
For i: =1 to 4*N do {инициализация дерева минимумов}
begin
Q[i]: =0;
Add[i]: =0;
Lm[i]: =0;
end;
Build(1, 1, N-1); {построение массива Lm для нулевого дерева MIN}
XPred: =X1[1]; {предыдущая координата по х}
Ly: =0; {здесь будет длина сечения по y}
Lmax: =Y2[N]-Y2[1]; {диапазон значений по оси Y}
S: =0; {общая площадь объединения прямоугольников}
For i: =1 to N do
begin
Lx: =X1[i]-XPred; {длина очередного прямоугольника по x}
XPred: =X1[i];
V: =Y1[i]; {координаты концов нового отрезка}
W: =Y1[Ind[i]];
c: =Ref1[i];
d: =Ref1[Ind[i]]; {индексы нижней и верхней точек в (X2, Y2)}
L: =Min(c, d);
R: =Max(c, d);
if V> W then {X[i] - левая сторона прямоугольника}
Plus(L, R-1, 1, 1, 1, N-1) {добавили отрезок}
else {X[i] - правая сторона прямоугольника}
Plus(L, R-1, -1, 1, 1, N-1); {убрали отрезок}
{если углы прямоугольников задаются в другом порядке: левый
нижний, а затем правый верхний, то изменение на if V< W}
S: =S+Lx*Ly; {учли пройденную площадь}
Ly: =Lmax-Long(1, N-1, 1, 1, N-1);
{вычли сумму длин нулевых отрезков, Ly-длина сечения по y}
end;
Assign(Fout, 'output.txt');
Rewrite(Fout);
WriteLn(Fout, S: 0: 2);
{2 знака после запятой без ведущих пробелов}
Close(Fout);
End.
|
|