IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Доставка на дом
сообщение
Сообщение #1


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Привет всем.

Задачка с окончившейся олимпиады (в аттаче, под литерой F). Я, наверное, изначально пошел неправильным путем, решив сделать рекурсией, при таких входных данных любая рекурсия вылетит.. но другого алгоритма придумать не смог. Точнее, примерно-то смог - надо разворачивать коробку, чтобы могла вперед катиться безгранично, и ехать в пункт назначения, но ничего конкретного. Вот решение: (отработало на 32 тестах из 35, баллов не дали sad.gif ). Да и переделывать уже нервов не было, после 2х дней написания первого варианта))

Небольшое пояснение, если кто-то захочет разобраться в этом кошмаре)
"Запретная" сторона определяется двумя координатами, по воображаемым осям (ноу-хау, блин_)), одна - справа налево, против часовой стрелки (редактировал, было ПО часовой) (обходит грани), вторая - от наблюдателя вперед. За точку отсчета берется сторона на земле (т.е. имеет координаты (1;1)). Если при движении коробки положение запретной стороны изменяется, то изменяется и соответствующая переменная.

{$APPTYPE CONSOLE}

type posn = record
kubx,kuby,tx,ty:integer; //kubx(y)-координата куба, tx(y) координаты стороны, которая сейчас на земле
end;

type TDvig = record
let:char;
dx,dy:integer;
end;

var kub:posn;
dvig:array[1..4] of TDvig;
l:char;
n,m,b,c,d,i,j,max,sc,lo,nlo:integer;
res:string='';
left:byte; //1-left; 2-no-left; 3-inaccessible

function canstep(x,y,id:integer):boolean;
var b1,b2,bl1,bl2:integer;
begin
bl1:=lo-dvig[id].dy;bl2:=nlo-dvig[id].dx;
if left=1 then begin
if (bl1>4) or (bl1=1) then begin
result:=false;exit;
end;
end;

if left=2 then begin
if (bl2>4) or (bl2=1) then begin
result:=false;exit;
end;
end;

b1:=kub.tx+dvig[id].dx;
b2:=kub.ty+dvig[id].dy;

if b1>4 then b1:=b1-4;
if b2>4 then b2:=b2-4;

if b1=0 then b1:=4;
if b2=0 then b2:=4;

if (x<=n) and (y<=m) and (x>0) and (y>0) then result:=true else result:=false;
end;

Procedure step(x,y,id:integer);
begin
kub.tx:=kub.tx+dvig[id].dx;
kub.ty:=kub.ty+dvig[id].dy;

if kub.tx>4 then kub.tx:=kub.tx-4;
if kub.ty>4 then kub.ty:=kub.ty-4;
if kub.tx=0 then kub.tx:=4;
if kub.ty=0 then kub.ty:=4;

kub.kubx:=x;kub.kuby:=y;

if left=3 then begin
if dvig[id].dy<>0 then begin
left:=1;
lo:=lo-dvig[id].dy;
end else begin
left:=2;
nlo:=nlo-dvig[id].dx;
end;
end
else if left=2 then begin
nlo:=nlo-dvig[id].dx;
if nlo=3 then left:=3;
end else begin
lo:=lo-dvig[id].dy;
if lo=3 then left:=3;
end;
end;

Procedure rec(backx,backy,x,y:integer);
var i,bx,by:integer;
begin
if (kub.kubx=c) and (kub.kuby=d) then begin
write(res);
halt(0);
end else begin

for i:=1 to 4 do begin

bx:=kub.kubx+dvig[i].dx;
by:=kub.kuby+dvig[i].dy;

if ((bx<>backx) or (by<>backy)) and canstep(bx,by,i) then begin
res:=res+dvig[i].let;
step(bx,by,i);
inc(sc);
if sc<=max then rec(x,y,bx,by);
step(bx-dvig[i].dx,by-dvig[i].dy,i);
delete(res,length(res),1);
dec(sc);
end;
end;
end;
end;

Procedure setdvig(ind:byte;l:char;d1,d2:integer);
begin
with dvig[ind] do begin
let:=l;
dx:=d1;
dy:=d2;
end;
end;

begin
assign(input,'delivery.in');
assign(output,'delivery.out');
read(n,m,b,c,d);readln;
read(l);
max:=4*(m+n);sc:=0;

nlo:=2;lo:=2;
case l of
'L':begin
lo:=4;
left:=1;
end;
'R':begin
lo:=2;
left:=1;
end;
'F':begin
nlo:=2;
left:=2;
end;
'T':begin
nlo:=3;
lo:=3;
left:=3;
end;
'B':begin
nlo:=4;
left:=2;
end;
end;

kub.kubx:=1;kub.kuby:=b;
kub.tx:=1;kub.ty:=1;

setdvig(1,'F',1,0);
setdvig(2,'R',0,1);
setdvig(3,'B',-1,0);
setdvig(4,'L',0,-1);

rec(0,0,1,b);
write('IMPOSSIBLE');
end.



Сообщение отредактировано: Unconnected -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 17:11
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name