INFOMAN брой 7
{ This is the input data:
4
+ -7 + 4 * 2 * 5
ÄÄÄÄÄÄÄÄÄ
ПРЪСТЕН
ÄÄÄÄÄÄÄÄÄ
Задачата е от втория ден на международната олимпиада
по информатика в Португалия през 1998 година.
Дадени са N цели числа, които са подредени в пръстен както е показано на
фигурата. Между всеки две числа има поставен аритметичен знак - "+" или "*".
Числата са поставени за върхове на правилен N-ъгълник, като на всяка негова
страна е съпоставен аритметичен знак.
2
(-7)ÄÄÄÄÄ+ÄÄÄÄÄÄ(4)
Ó Ó
Ó Ó
N = 4 1 + * 3
Ó Ó
Ó Ó
(5)ÄÄÄÄÄ*ÄÄÄÄÄÄ(2)
4
Страните са номерирани по часовниковата с числата от 1 до N както на фигура-
та. Играе се следната игра: На първия ход се изтрива една от страните. Така
пръстенът се превръща в редица от числа (върхове), между всеки две от които
има аритметичен знак. Например ако премахнем страна 3, ще получим следната
редица: * + +
(2) (5) (-7) (4)
На всеки от следващите ходове се избира една страна Z и нека V1 и V2 са вър-
ховете, краища на тази страна. Z, V1 и V2 се заместват с нов връх, който е
резултатът от операцията Z, приложена върху V1 и V2. Това се прилага докато
не остане само един връх. Резултатът от играта е числото в този връх. Да се
напише програма,която при зададен пръстен намира най-големия възможен резул-
тата и определя страните, с изтриването на които при първия ход може да се
достигне до този резултат. Входния файл съдържа 2 реда. На първия е числото
N, а на втория има списък от знаци на страни и числа във вида:
знак1 число1 знак2 число2 ... знакN числоN
Забележете, че първият знак е знакът за страна 1, т.е. знака между връх N и
връх 1, а втория е между връх 1 и 2. За дадената фигура входния файл изглеж-
да така:
4
+ -7 + 4 * 2 * 5
Изходът трябва да се състои от 1 число - най-големия възможен резултат - и
списък на всички страни,с които играчът може да започне и да получи този ре-
зултат. N <= 50. При започване на играта и след всеки ход всички върхове ще
имат стойност [-32768..32767].
РЕШЕНИЕ: Ще решим задачата, като намерим максималните резултати след отстра-
няване на всяка от страните и от тези резултати изберем максималния. За цел-
та ще представяме пръстена като два масива - 1 от числа и 1 от знаци.Когато
премахваме една страна Z, ще преномерирваме върховете и страните,така че за
първи връх да вземаме върха Z+1. Така получаваме редица от числа, между кои-
то има знаци. Ясно е,че различни резултати се получават при различен ред на
прилагане на операциите между числата. Трябва да намерим този ред, в който
трябва да се изчисли получения числов израз (редицата с числа и знаци между
тях), при който резултатът ще е максимален. На практика имаме някакъв вари-
ант на задачата за поставяне на скоби, която както е добре известно се реша-
ва с методът "динамично оптимиране".За да решим задачата за намиране на мак-
сималния резултат от израза по този метод, трябва да имаме рекурентните фор-
мули, чрез които ще оптимираме. Нека F(v1,v2) е максималния резултат, който
може да се получи от изчисляването на подизраза,започващ от връх v1 и завър-
шващ във връх v2 и M(v1,v2) е минималният резултат за този подизраз. Тогава
търсеният резултат от целия израз е F(1,N), а рекурентните връзки, които ще
използваме за да изчислим F(1,N) са:
F(v,v) = R[v]
F(v1,v2) = ако Z[i] = '+'
max( F(v1,i)+F(i+1,v2) ) за i = v1...v2-1
ако Z[i] = '*'
max( F(v1,i)*F(i+1,v2),
M(v1,i)*M(i+1,v2) )
за i = v1...v2-1
M(v,v) = R[v]
M(v1,v2) = ако Z[i] = '+'
max( M(v1,i)+M(i+1,v2) ) за i = v1...v2-1
ако Z[i] = '*'
max( M(v1,i)*M(i+1,v2),
M(v1,i)*F(i+1,v2),
F(v1,i)*M(i+1,v2),
F(v1,i)*F(i+1,v2) )
за i = v1...v2-1
Тук с R[v] означихме стойността на връх v, а с Z[i] означихме аритметичния
знак между върховете i и i+1. За да изведем формулите използвахме, че v1>v2
и че F(v1,v2) >= M(v1,v2) за всеки два върха v1 и v2.Верността на формулите
е очевидна. Идеята, която използваме за оптимирането е, че ако имаме макси-
малната и минималната стойност за подредиците (v1...i) и (i+1...v2) и знака
Z[i], можем да изчислим минималната и максималната стойност на подредицата
(v1...v2). Понеже всички възможни редици са само N*(N+1)/2, ние можем да из-
числим максималните и минималните стойности за всяка една от тях със слож-
ност O(N*N*N). Идеята на оптимирането е да се разцепи на две редицата,която
се оптимира, да се изчислят стойностите за двете части и от тях да се изчис-
лят стойносите за цялата редица. Идеята е същата като при широкоизвестната
задача за умножение на матрици, но в нашия случай алгоритъма е малко по-сло-
жен. За да намерим максималната стойност на една редица, трябва да имаме не
само максималните стойности на съставящите я подредици, но и минималните.То-
ва е така,защото при умножение на две числа максимално число се получава не
само двете числа са максимални, но и ако те са минимални - в случай на отри-
цателни числа. Минимално число пък може да се получи и по 4-те начина и то-
ва е взето предвид при измисляне на рекурентните формули за оптимирането.
Общата сложност на алгоритъма е от порядъка на N*N*N*N.
}
CONST MaxN = 50;
InFileName = 'prusten.pas';
OutFileName = '';
NotDefined = MaxInt;
VAR R: array[1..MaxN] of integer; {vertices}
Z: array[1..MaxN] of char; {signs between the vertices}
Optimal: array[1..MaxN] of integer;
TableF,TableM: array[1..MaxN,1..MaxN] of integer;
N: byte;
Procedure ReadData; {Read the input data - N, Prusten[1..N], PrustenZ[1..N]}
Var F: Text;
Z1: char;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,N);
for N:= 1 to N do
begin
Read(F,Z[N]); if Z[N] = ' ' then Read(F,Z[N]);
Read(F,R[N]);
end;
Close(F);
Z1:=Z[1]; Move(Z[2],Z[1],N-1); Z[N]:=Z1;
End;
Function M(v1,v2:byte): integer; forward;
Function F(v1,v2:byte): integer; { Calculate maximal result for v1...v2 }
Var Max: integer;
i: byte;
Begin
if v1 = v2 then
begin F:=R[v1]; Exit; end;
if TableF[v1,v2] <> NotDefined then
begin F:=TableF[v1,v2]; Exit; end; {Already calculated}
Max:=-MaxInt;
for i:= v1 to v2-1 do
if Z[i] = '*' then
begin
if F(v1,i)*F(i+1,v2) > Max then
Max:= F(v1,i)*F(i+1,v2);
if M(v1,i)*M(i+1,v2) > Max then
Max:= M(v1,i)*M(i+1,v2);
end
else {if Z[i] = '+' then}
if F(v1,i)+F(i+1,v2) > Max then
Max:= F(v1,i)+F(i+1,v2);
TableF[v1,v2]:=Max; F:=Max;
End;
Function M(v1,v2:byte): integer; { Calculate minimal result for v1...v2 }
Var Min: integer;
i: byte;
Begin
if v1 = v2 then
begin M:=R[v1]; Exit; end;
if TableM[v1,v2] <> NotDefined then
begin M:=TableM[v1,v2]; Exit; end; {Already calculated}
Min:=MaxInt;
for i:= v1 to v2-1 do
if Z[i] = '*' then
begin
if M(v1,i)*M(i+1,v2) < Min then
Min:= M(v1,i)*M(i+1,v2);
if M(v1,i)*F(i+1,v2) < Min then
Min:= M(v1,i)*F(i+1,v2);
if F(v1,i)*M(i+1,v2) < Min then
Min:= F(v1,i)*M(i+1,v2);
if F(v1,i)*F(i+1,v2) < Min then
Min:= F(v1,i)*F(i+1,v2);
end
else {if Z[i] = '+' then}
if M(v1,i)+M(i+1,v2) < Min then
Min:= M(v1,i)+M(i+1,v2);
TableM[v1,v2]:=Min; M:=Min;
End;
Procedure CalculateOptimals; { Calculate Optimal[1..N] }
{ Optimal[i] = the maximal value when we remove the side i }
Var Side,i,j: integer;
Z1: char;
R1: integer;
Begin
for Side:= 1 to N do
begin
{ Calculate Optimal result if remove the side Side }
for i:= 1 to N do
for j:= 1 to N do
begin TableF[i,j]:=NotDefined; TableM[i,j]:=NotDefined; end;
Optimal[Side]:=F(1,N);
{ Rotate right R[1..N] and Z[1..N] }
Z1:=Z[1]; R1:=R[1];
Move(Z[2],Z[1],(N-1)*SizeOf(Z[1]));
Move(R[2],R[1],(N-1)*SizeOf(R[1]));
Z[N]:=Z1; R[N]:=R1;
end;
End;
Procedure Print; { Find and print the maximal result from Optimal[1..N] }
Var i,Max: integer;
OutF: Text;
Begin
Assign(OutF,OutFileName); Rewrite(OutF);
Max:=-MaxInt;
for i:= 1 to N do {Find maximal result}
if Optimal[i] > Max then
Max:= Optimal[i];
WriteLn(OutF,Max); {Print maximal result}
for i:= 1 to N do {Print the sides we can obtain this result from}
if Optimal[i] = Max then
Write(OutF,i,' ');
WriteLn(OutF); WriteLn(OutF);
Close(OutF);
End;
BEGIN
ReadData;
CalculateOptimals;
Print;
END.