Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения. Часть 1
Подождите немного. Документ загружается.
knc:=Temp;
End;
End;
Begin
Write('Введите число ');
ReadLn(N);
n:=abs(n); {Вычислим модуль n}
if n=0 then Writeln('0') else
Begin
while n mod 2 = 0 do n:=n div 2; {уменьшаем n до нечетного
числа }
c:=n div 2; {Разложим n на четное}
nc:=n-c; {и нечетное числа }
if c=0 then kc:=0 else kc:=1;
knc:=1;
while (c>2) or (nc>2) do
Begin
Correct; {поменяем c и nc, если нужно}
c:=c div 2; {получим новый аргумент}
kc:=kc+knc; {получим коэфф. при нем }
nc:=nc-c; {вычислим второй аргумент}
End;
WriteLn(Kc+knc); {Выведем результат}
ReadLn; {Подождем }
End;
End.
Задача 3. "Лабиринт"
Задача была предложена на общеуниверситетской олимпиаде по
программированию , посвященной дню рождения факультета
ПММ (март 2001). Ниже приведено решение победителя
олимпиады , в настоящее время студента 4 курса факультета
ПММ ВГУ Антона Александровича Клинских .
1. Условие задачи .
В результате рейда налоговой полиции города Обломова в фирму
Real в одном из небоскрёбов был обнаружен секретный уровень, на
который вела только одна лестница, а в некоторых местах были
аварийные выходы (в виде люков в полу ). Согласно агентурным
данным, уровень представляет собой прямоугольник из M*N
комнат одинакового размера (M комнат вдоль западной стены , N --
вдоль северной), причём между некоторыми парами соседних
комнат есть двери . Положение осложняется тем , что точные
координаты как входа, так и выходов неизвестны .
На разведку были отправлены обезьянки из местного зоопарка.
Каждая из них поднималась по лестнице и ходила по уровню, пока
не натыкалась на какой-нибудь выход . После этого она спускалась
по нему и сообщала свой маршрут начальству . При этом первая
обезьянка в начальной точке смотрела на север, а остальные -
неизвестно куда. Маршрут каждой обезьянки представлен в виде
последовательности символов, представляющих движения и
повороты :
F шаг вперёд
R поворот направо
L поворот налево
B разворот
W впереди стена, движения не было
E выход , конец маршрута (может идти только
непосредственно после F)
Задача состоит в том , чтобы построить план обследованной
части уровня, содержащий всю собранную информацию: стенки ,
проходы, выходы.
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Время тестирования: 20 сек/тест
Входные данные
В первой строке входного потока задаются числа M и N,
разделённые пробелами.
На следующей строке задаётся общее количество маршрутов.
Далее идут маршруты , представляющие собой последовательность
символов F, R, L, B, W, E, возможно, разделённых пробельными
символами. Каждый маршрут заканчивается символом E, после
которого начинается следующий маршрут.
Ограничения
Входные данные удовлетворяют следующим ограничениям : 1 <
M < 50, 1 < N < 50, общее количество маршрутов -- не более 100,
общее количество символов в записи маршрутов -- не более 255.
Результат
Программа должна напечатать карту уровня размера
(2M+1)*(2N+1), нарисованную символами:
(<<пробел>>) пустая комната или проход
+ угол комнаты
- северная/южная стенка
| западная/восточная стенка
* вход
# выход
? неизвестное состояние комнаты или стенки
Если существует несколько планов уровней, удовлетворяющих
условиям задачи , достаточно напечатать любой, если план
построить не удаётся, программа должна напечатать строку NO.
2. Алгоритм решения.
Для построения плана необходимо соотнести донесения всех
обезьянок так, чтобы они не противоречили друг другу .
Используется бэк-трэкинг, расшифровывающий маршрут
очередной обезьянки , и если это приводит к конфликту , последний
маршрут отменяется, и производится попытка согласовать
маршрут этой обезьянки , предположив, что в начальный момент
она смотрела в другую сторону и т.д. Если все четыре начальных
направления обезьянки приводят к конфликтам , считается, что
план для этой обезьянки построить не удается, что вызовет
изменение начального направления предыдущей обезьянки и т.д .
до первой. Откат реализуется с помощью рекурсии, а состояния
плана хранятся в стеке .
Если при какой-либо комбинации начальных состояний всех
обезьянок план построен, он и является ответом . Если такой
комбинации нет, плана не существует.
3. Программная реализация.
Program Labirint; {Автор-Клинских А.А.}
const
MaxN=50;
MaxM=50;
type
TPoint=record
x,y:integer
end;
PPlan=^TPlan;
TPlan=array[-2*MaxN..2*MaxN,-2*MaxM..2*MaxM] of char;
{План }
TStack=^TElem;
TElem=record
Plan:TPlan;
L,R,T,B:integer;
Next:TStack
end;
var
Stack:TStack; {Стек}
Input,Output:Text; {Файлы ввода/вывода}
M,N:integer; {Размеры поля }
NOfM:integer; {Число маршрутов}
L,R,T,B:integer; {Текущие границы поля }
Cur,Next,Dir:TPoint; {Текущая и следующая точки и направление,
куда смотрит обезьяна}
Plan:TPlan; {План }
Monkeys:array[1..10] of string; {Маршруты }
{****************************}
{Процедуры работы со стеком }
{Инициализация стека}
procedure InitStack;
begin
Stack:=nil
end;
{Добавление в стек}
procedure PushStack(var Plan:TPlan;T,B,L,R:integer);
var
p:TStack;
begin
p:=Stack;
new(Stack);
Stack^.Plan:=Plan;
Stack^.T:=T;
Stack^.L:=L;
Stack^.R:=R;
Stack^.B:=B;
Stack^.next:=p
end;
{Извлечение из стека}
procedure PopStack(var Plan:TPlan;var T,B,L,R:integer);
var
p:TStack;
begin
p:=Stack;
Stack:=Stack^.next;
T:=p^.T;
L:=p^.L;
R:=p^.R;
B:=p^.B;
Plan:=p^.Plan;
dispose(p)
end;
{Проверка стека на пустоту }
Function Empty:boolean;
begin
Empty:=Stack=nil
end;
{********************************}
{Процедура чтения}
procedure InitIO;
var
i:integer;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
read(input,M);
readln(input,N);
readln(input,NOfM);
For i:=1 to NofM do
readln(input,Monkeys[i])
end;
{*****************************************}
{----------------Алгоритм ------------------}
{Функция,"пытающаяся" расшифровать очередной маршрут}
{Если удалось построить план ,возвращает true}
Function GetNextMonkey(nom:integer):boolean;
var
index:byte;
c:char;
begin
GetNextMonkey:=False;
index:=1; {Номер очередного символа в маршруте }
repeat
c:=Monkeys[nom][index];
case c of
'F':begin {Если был шаг вперед}
if (Plan[Next.x,Next.y] in [' ','?']) then {Если впереди стенка,}
begin {шагать туда нельзя}
Cur:=Next;
Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y;
Plan[cur.x,cur.y]:=' ';
if Monkeys[nom][index+1]='E' then {Обезьянка здесь вышла }
begin
GetNextMonkey:=Plan[Next.x,Next.y] in ['?','#']; {если это
невозможно}
if [Plan[Next.x,Next.y]]*['?','#']=[] then exit; {запоминаем ошибку }
Plan[Next.x,Next.y]:='#' {иначе устанавливаем выход }
end;
if Plan[Next.x,Next.y] in ['?'] then
Plan[Next.x,Next.y]:=' ';
Cur:=Next;
Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y; {--------}
if cur.y>=T then T:=cur.y+1; {Изменяем местоположение
обезьянки }
if cur.y<=B then B:=cur.y-1; {и габариты плана(если нужно)}
if cur.x>=R then R:=cur.x+1;
if cur.x<=L then L:=cur.x-1; {-----------}
if ((T-B+1)>2*M+1) or ((R-L+1)>2*N+1) then
exit; {План слишком большой}
if Plan[cur.x,cur.y]='#' then
begin {Пришли на выход :проверим сообщение обезьянки }
GetNextMonkey:=Monkeys[nom][index+1]='E'; {и выйдем }
exit
end
end
else
exit
end;
'L':begin {Повернем обезьянку налево}
if dir.x=0 then
begin
dir.x:=-dir.y;
dir.y:=0
end
else
begin
dir.y:=dir.x;
dir.x:=0
end;
Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y
end;
'R':begin {Повернем обезьянку направо}
if dir.x=0 then
begin
dir.x:=dir.y;
dir.y:=0
end
else
begin
dir.y:=-dir.x;
dir.x:=0
end;
Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y
end;
'B':begin {Развернем обезьянку }
dir.x:=-dir.x;
dir.y:=-dir.y;
Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y
end;
'W':begin {Впереди стенка}
if Plan[Next.x,Next.y] in ['?','-','|'] then
begin
if dir.x=0
then Plan[Next.x,Next.y]:='-' {вертикальная или
горизонтальная}
else Plan[Next.x,Next.y]:='|';
if Next.y>T then T:=Next.y;
if Next.y<B then B:=Next.y;
if Next.x>R then R:=Next.x; {Изменяем габариты плана(если
нужно)}
if Next.x<L then L:=Next.x
end