Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения. Часть 1
Подождите немного. Документ загружается.
else
exit
end
end;
inc(index)
until c='E';
GetNextMonkey:=True {Если не было аварийных выходов,все в
порядке }
end;
{Функция, находящая план по всем маршрутам начиная с por.}
{Рекурсивно вызывает саму себя пока не использует все
маршруты }
{Если удалось построить план ,возвращает true}
Function GetMonkeys(por:integer):boolean;
var
t0,b0,l0,r0:integer;
D:TPoint;
p:PPlan;
OK:boolean;
Count:integer;
begin
if por>NOfM then
begin {Все маршруты согласованы }
GetMonkeys:=True; {Запоминаем ,что план построен}
new(p);
while not Empty do {Очищаем стек}
PopStack(p^,T0,B0,L0,R0);
exit
end;
Count:=1;
d.x:=0; d.y:=1;
repeat
Dir:=D;
Cur.x:=0; Cur.y:=0;
Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y;
PushStack(Plan,T,B,L,R); {Сохраняем настройки }
OK:=GetNextMonkey(por) and GetMonkeys(por+1); {Добавляем
маршрут}
if OK then break; {Если OK выходим}
PopStack(Plan,T,B,L,R); {иначе восстановим настройки }
if d.x=0 then {и повернем обезьянку }
begin
d.x:=d.y; d.y:=0
end
else
begin
d.y:=-d.x;d.x:=0
end;
inc(Count)
until (Count=5) or OK;
GetMonkeys:=OK
end;
{***********************************}
{Инициализация поля }
procedure Clear;
var
i,j:integer;
begin
For i:=-MaxN to MaxN do
For j:=-MaxM to MaxM do
if odd(abs(i)) and odd(abs(j)) then
Plan[i,j]:='+' else Plan[i,j]:='?';
Plan[0,0]:='*'
end;
{Вывод плана}
procedure ShowPlan;
var
i,j:integer;
begin
For i:=T downto T-2*M do
begin
For j:=L to L+2*N do
begin
if (i=T) or (i=T-2*M) then
if odd(j-L) then
write(output,'-')
else
write(output,'+')
else
if (j=L) or (j=L+2*N) then
if odd(T-i) then
write(output,'|')
else
write(output,'+')
else
write(output,Plan[j,i]);
end;
writeln(output);
end
end;
{Вывод сообщения об ошибке }
procedure ShowError;
begin
writeln(output,'NO')
end;
{Закрываем использованные файлы }
procedure CloseIO;
begin
close(input);close(output)
end;
begin {Основная программа}
InitIO;
Clear;
if GetMonkeys(1) then
ShowPlan
else
ShowError;
CloseIO
end.
Задача 4. «Прямоугольники»
Задача предлагалась в 1998 году на олимпиаде первокурсников
факультета ПММ ВГУ. Автор решения – одна из призеров
олимпиады , Лусине Азатовна Мхитарян , в настоящее время
студентка 5 курса факультета ПММ
1. Условие задачи
На плоскости задано N прямоугольников с координатами
вершин
(X1i,Y1i),(X2i,Y2i),(X3i,Y3i),(X4i,Y4i) , i=1,2,3,...,N. Известно, что
все стороны прямоугольников параллельны осям координат. Все
прямоугольники являются замкнутыми множествами, т.е . содержат
свою границу . Будем считать, что прямоугольники пересекаются,
если они имею хотя бы одну общую точку (в том числе и на
границе ).
Необходимо определить количество фигур образованных в
результате наложения прямоугольников.
Входные данные
В первой строке (1<=N<=100) - число прямоугольников.
В каждой последующей их координаты , заданные целыми числами
-1000<=X1i,Y1i,X2i,Y2i,X3i,Y3i,X4i,Y4i<=1000) i=1,2,3,...,N.
Выходные данные
Число фигур.
2. Алгоритм решения.
Задача решается с использованием элементов теории графов.
Строится матрица инцидентности M, где M[I,J]=1 если I-тый
прямоугольник пересекается с J-тым. Остается лишь определить
число компонент связности полученного графа.
3. Программная реализация
Program Rectangular; {Автор Мхитарян Л .А.}
Const MaxN=100;
Type TRec=Record
XA,YA,XB,YB:Integer
End;
Var PA:Array [1..MaxN] of TRec;
M:Array[1..MaxN,1..MaxN] of Boolean;
N,FC:Integer;
BA:Array[1..MaxN] of Boolean;
Function Min(A,B:Integer):Integer;
Begin
If A>B Then Min:=B
Else Min:=A
End;
Function Max(A,B:Integer):Integer;
Begin
If A<B Then Max:=B
Else Max:=A
End;
Procedure Init;
Var F:Text;I,X1,Y1,X2,Y2,X3,Y3,X4,Y4:integer;
Begin
Assign(F,'input.txt');ReSet(F);
ReadLn(F,N);
For I:=1 to N do
Begin
ReadLn(F,X1,Y1,X2,Y2,X3,Y3,X4,Y4);
PA[I].XA:=Min(Min(X1,X2),Min(X3,X4));
PA[I].YA:=Min(Min(Y1,Y2),Min(Y3,Y4));
PA[I].XB:=Max(Max(X1,X2),Max(X3,X4));
PA[I].YB:=Max(Max(Y1,Y2),Max(Y3,Y4));
End;
For I:=1 to N do
For X1:=1 to N do
M[I,X1]:=False;
For I:=1 to N do
BA[I]:=False;
Close(F)
End;
Function Check(I,J:Integer):Boolean;
{Проверка: пересекаются ли I-ый и J-ый прямоугольники }
Var R1,R2:TRec;
Begin
Check:=False;
If PA[I].XA<PA[J].XA Then Begin R1:=PA[I];R2:=PA[J] End
Else Begin R1:=PA[J];R2:=PA[I] End;
If R1.XB>=R2.XA Then Begin
If (R1.YB>=R2.YA) and (R1.YB<=R2.YB) Then Check:=True;
If (R2.YB>=R1.YA) and (R2.YB<=R1.YB) Then Check:=True
End
End;
Function GetPodGraph:Boolean;
{Выделение компоненты связности графа}
Var I,J,K,T:Integer;
Begin
T:=-1;
For I:=1 to N do
If not BA[I] Then Begin T:=I;Break End;
If T=-1 Then Begin GetPodgraph:=False;Exit End;
M[T,T]:=True;
For I:=1 to N do
For J:=1 to N do
For K:=1 to n Do
If M[J,J] Then
If M[J,K] Then M[K,K]:=True;
For I:=1 to N do
If not BA[I] and M[I,I] Then BA[I]:=True;
GetPodGraph:=True
End;
Procedure Run;
{Вычисление количества подграфов}
Var I,J:Integer;
Begin
FC:=0;
For I:=1 to N do
For J:=1 to N do
If I<>J Then M[I,J]:=Check(I,J);
While GetPodgraph do
Begin
Inc(FC);
For I:=1 to N do
If M[I,I] then M[I,I]:=False;
End;
End;
Procedure Done;
{Вывод результатов}
Var F:Text;
Begin
Assign(F,'output.txt');ReWrite(F);
WriteLn(F,FC);
Close(F);
End;
Begin
Init;
Run;
Done
End.
Задача 5. «Трубопровод»
В основу условия задачи положена задача, которая
предлагалась на четверть финале мирового первенства по
программированию 2000 года (г.Саратов). Автор программы –
член сборной ВГУ по программированию , в настоящее время
студент 5 курса факультета ПММ ВГУ Андрей Евгеньевич
Поляков.
1. Условие задачи .
Пусть имеется трубопровод , заданный прямой линией на
плоскости Ax+By+C=0 и два города с координатами (x1,y1),
(x2,y2). Необходимо соединить эти два города с трубопроводом ,
истратив при этом наименьшее число труб; указать суммарную
длину использованных труб и две точки где происходит
соединение трубопроводов.
Входные данные
Целые числа -100000<=A,B,C<=100000 - параметры трубопровода
-100000<=X1,Y1<=100000 - координаты первого города
-100000<=X2,Y2<=100000 - координаты второго города
Выходные данные
В первой строке суммарная длина использованных труб
Во второй и третьей соответственно координаты точек соединения
трубопроводов
2. Алгоритм решения
Рассмотрим две возможности
1). Точки лежат с разных сторон от прямой. Тогда для их
соединения достаточно опустить на прямую перпендикуляры из
этих точек. На выходе получим сумму длин этих перпендикуляров
и их точки пересечения с прямой.
2). Точки лежат по одну сторону от прямой. Здесь возможны 3
случая
а) Одна точка соединяется с другой, из которой затем опускается
перпендикуляр на прямую. На выходе: длина перпендикуляра плюс
расстояние между точками, координаты точки пересечения