INFOMAN брой 1
{ ЗАДАЧА ЗА ЧАСОВНИЦИТЕ ОТ МЕЖДУНАРОДНАТА ОЛИМПИАДА В ШВЕЦИЯ
Условието беше: Имаме 9 часовника, които са подредени в три групи по три,
имат само по 1 стрелка и могат да показват само 12, 3, 6 и 9 часа, което
ще отбелязваме съответно с цифрите 0,1,2 и 3.Целта е всичките стрелки да
се докарат да показват 12 часа, като се използва само поредица от следни-
те правила:
þþù þþþ ùþþ þùù ùþù ùùþ ùùù ùùù ùùù
1 þþù 2 ùùù 3 ùþþ 4 þùù 5 þþþ 6 ùùþ 7 þþù 8 ùùù 9 ùþþ
ùùù ùùù ùùù þùù ùþù ùùþ þþù þþþ ùþþ
където с `þ` са означени часовниците,чиито стрелки се завъртат на 90ø, а
с `ù` - часовниците, чиито стрелки не променят положението си. Да се нап-
рави програма,която намира решението с минимален брой ходове и отпечатва
последователност от правила, прилагането на които решева задачата.
I начин:
Много важно е да забележим: 1. Редът на прилагане на правилата
е без никакво значение; 2. Прилагането на кое да е правило от деветте го-
реописани K пъти (K>3) е еквивалентно на прилагането му K mod 4 пъти, ко-
ето означава,че никое правило не трябва да се прилага повече от три пъти.
Следователно имаме 9 правила,всяко от които може да се прилага най-много
3 пъти, а това означава,че всичките възможни последователности от ходове,
които водят до различен резултат съвпадат с броя на комбинациите с повто-
рения на 4 елемента от 9 възможни, които са точно 4^9 = 262144 последова-
телности от ходове, които могат да се генерират и проверят безпроблемно.
Като вземем предвид,че всяка една конфигурация от 9 часовника може да се
получи по един единствен начин, то първото намерено решение е оптимално.
Алгоритъма се реализира от процедурата Try.
II начин:
Същият алгоритъм може да се реализира и чрез търсене в ширина. Така
първо ще се проверяват едноходовите последователности от ходеве, след то-
ва - двуходовите, триходовите и т.н. Това гарантира, че първото намерено
решение е минимално и спестява малко време. Понеже има само едно решение,
горният алгоритъм също е верен и е по-лесен за реализация.
III начин:
Да номерираме по последователно по редове часовниците с числата [1..9].
Забелязваме, че само операции 1,2 и 4 променят състоянието на часовник 1,
операции 1,2,3 и 5 променят състоянието на часовник 2 и т.н. Въз основа
на тези разсъждения стигаме до извода, че състоянието на часовниците (S1,
S2,...S9) е:
S1 = ( S1' + t1 + t2 + t4 ) mod 4
S2 = ( S2' + t1 + t2 + t3 + t5 ) mod 4
S3 = ( S3' + t2 + t3 + t6 ) mod 4
S4 = ( S4' + t1 + t4 + t5 + t7 ) mod 4
S5 = ( S5' + t1 + t3 + t5 + t7 + t9 ) mod 4
S6 = ( S6' + t3 + t5 + t6 + t9 ) mod 4
S7 = ( S7' + t4 + t7 + t8 ) mod 4
S8 = ( S8' + t5 + t7 + t8 + t9 ) mod 4
S9 = ( S9' + t6 + t8 + t9 ) mod 4
където S1',S2',....,S9' са съответно началните състоянията на деветте ча-
совника, а t1,t2,...,t9 са съответно броя прилагания на правила с номер
от 1 до 9. Понеже крайната позиция е (S1=0,S2=0,...,S9=0), задачата може
да се сведе до решаване на система от 9 линейни уравнения по модул 4. За
това си има много алгоритми (които не са ми много ясни). Понеже при коре-
ктни входни данни горната система има едно единствено решение, то то е и
най-доброто. Реализация на тази идея е процедурата SolveEquation.
IV начин:
Този начин използва всичко описано във втория метод, но не решава сис-
темата от уравнения в момента, а я използва готова решена. Процедурата за
решаване на задачата по този метод само изчислава по един числов израз съ-
ответно за t1,t2,...,t9 , който е предварително изведен. (вж. SolveShort)
}
{$A+,B-,D+,E+,F-,G+,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 16384,0,655360}
TYPE Clocks= array[1..3,1..3] of byte;
CONST N = 9; {брой часовници и брой операции}
Cl: Clocks = (
(2,1,3),
(1,3,2),
(3,2,1));
VAR Hodove: array[1..N] of integer;
Procedure PrintSolution;
Var I,J: byte;
Begin
for I:= 1 to 9 do
for J:= 1 to Hodove[I] do
Write(I,' ');
WriteLn;
End;
{-------------------------------- I начин ----------------------------------}
Procedure Try(Br:byte); {Прилага операция номер Br от 0 до 3 пъти}
Procedure Rot(x,B:byte);
Begin Cl[x,B]:=(Cl[x,B]+1) mod 4; End;
Var OldCl: Clocks;
I: byte;
Begin
if Br > 9 then
begin
if (Cl[1,1]=0) and (Cl[1,2]=0) and (Cl[1,3]=0) and
(Cl[2,1]=0) and (Cl[2,2]=0) and (Cl[2,3]=0) and
(Cl[3,1]=0) and (Cl[3,2]=0) and (Cl[3,3]=0) then
PrintSolution; {Намерено е решение - всички часовници са на 0}
Exit;
end;
OldCl:=Cl; {Запазваме старата позиция на всички часовници}
for I:= 0 to 3 do
begin
Hodove[Br]:=I;
if I>0 then
case Br of
1: begin Rot(1,1); Rot(1,2); Rot(2,1); Rot(2,2); end;
2: begin Rot(1,1); Rot(2,1); Rot(3,1); end;
3: begin Rot(3,1); Rot(3,2); Rot(2,1); Rot(2,2); end;
4: begin Rot(1,1); Rot(1,2); Rot(1,3); end;
5: begin Rot(2,1); Rot(2,2); Rot(2,3); Rot(1,2); Rot(3,2); end;
6: begin Rot(3,1); Rot(3,2); Rot(3,3); end;
7: begin Rot(1,3); Rot(1,2); Rot(2,3); Rot(2,2); end;
8: begin Rot(1,3); Rot(2,3); Rot(3,3); end;
9: begin Rot(3,3); Rot(3,2); Rot(2,3); Rot(2,2); end;
end;
Try(Br+1);
end;
Cl:=OldCl; {Възстановяваме старата позиция на всички часовници}
End;
{-------------------------------- III начин --------------------------------}
Procedure SolveEquation;
Const N = 9;
Const A: array[1..N,1..N] of integer =( {Коефициенти пред t1,t2,...,t9}
( 1,1,0,1,0,0,0,0,0 ),
( 1,1,1,0,1,0,0,0,0 ),
( 0,1,1,0,0,1,0,0,0 ),
( 1,0,0,1,1,0,1,0,0 ),
( 1,0,1,0,1,0,1,0,1 ),
( 0,0,1,0,1,1,0,0,1 ),
( 0,0,0,1,0,0,1,1,0 ),
( 0,0,0,0,1,0,1,1,1 ),
( 0,0,0,0,0,1,0,1,1 ));
Var B: array[1..N] of integer absolute Hodove;
I,J,k,h: integer;
Begin
for I:= 1 to 3 do
for J:= 1 to 3 do
B[I+(J-1)*3]:= 4-Cl[I,J];
{Решаване на системата от уравнения по модул 4 в цели числа}
{ transform A into the unit matrix and b into a solution vector }
for i := 1 to 9 do begin { process column i }
{ find pivot by bounded linear search for first 1 or 3 in column i }
k := i ; h := 10 ;
while k <> h do
if A[k, i] in [1, 3] then h := k else inc(k) ;
if k = 10 then begin
writeln('Pivot not found in step ', i:1) ;
halt
end { if } ;
{ swap rows i and k }
for j := i to 9 do begin
h := A[i, j] ; A[i, j] := A[k, j] ; A[k, j] := h
end { for j } ;
h := b[i] ; b[i] := b[k] ; b[k] := h ;
{ normalize row i, yielding A[i, i] = 1 }
h := A[i, i] ; { h * A[i, i] = 1 (mod 4) }
for j := i to 9 do
A[i, j] := (h * A[i, j]) mod 4 ;
b[i] := (h * b[i]) mod 4 ;
{ sweep column i to zeroes in rows other than i }
for k := 1 to 9 do begin { take care of row k }
if k <> i then begin
h := 3*A[k, i] ;
for j := i to 9 do
A[k, j] := (A[k, j] + h*A[i, j]) mod 4 ;
b[k] := (b[k] + h*b[i]) mod 4
end { if }
end { for j } ;
end; { for i }
PrintSolution;
End;
{--------------------------------- IV начин --------------------------------}
Procedure SolveShort;
Var T: array[1..N] of integer absolute Hodove;
S: array[1..N] of integer;
I,J: integer;
Begin
for I:= 1 to 3 do
for J:= 1 to 3 do
S[I+(J-1)*3]:= Cl[I,J];
T[1] := (8+ S[1]+2*S[2]+ S[3]+2*S[4]+2*S[5] -S[6]+ S[7] -S[8] ) mod 4;
T[2] := ( S[1]+ S[2]+ S[3]+ S[4]+ S[5]+ S[6]+2*S[7]+ 2*S[9]) mod 4;
T[3] := (8+ S[1]+2*S[2]+ S[3] -S[4]+2*S[5]+2*S[6] -S[8]+ S[9]) mod 4;
T[4] := ( S[1]+ S[2]+2*S[3]+ S[4]+ S[5]+ S[7]+ S[8]+2*S[9]) mod 4;
T[5] := (4+ S[1]+2*S[2]+ S[3]+2*S[4] -S[5]+2*S[6]+ S[7]+2*S[8]+ S[9]) mod 4;
T[6] := ( 2*S[1]+ S[2]+ S[3]+ S[5]+ S[6]+2*S[7]+ S[8]+ S[9]) mod 4;
T[7] := (8+ S[1] -S[2]+ 2*S[4]+2*S[5] -S[6]+ S[7]+2*S[8]+ S[9]) mod 4;
T[8] := ( 2*S[1]+ 2*S[3]+ S[4]+ S[5]+ S[6]+ S[7]+ S[8]+ S[9]) mod 4;
T[9] := (8 -S[2]+ S[3] -S[4]+2*S[5]+2*S[6]+ S[7]+2*S[8]+ S[9]) mod 4;
PrintSolution;
End;
BEGIN
WriteLn;
Try(1); {I начин}
SolveEquation; {III начин}
SolveShort; {IV начин}
END.