ЗВЕЗДА
Национална олимпиада по информатика,
Финален (4-ти, подборен) кръг, 1999 г.
УСЛОВИЕ НА ЗАДАЧАТА:
Една дъска съдържа 48 триъгълни клетки. Във всяка клетка е записана цифра от 0 до 9. Всяка клетка принадлежи на две или три линии, които са маркирани с буквите от A до L. Едно възможно разположение е показано на Фиг. 1. В този пример, клетката съдържаща 9, принадлежи на линии D,G и I,а клетката съдържаща 7-на B и I.
За всяка линия A,B,C,....,L е известна най-голямата цифра, която лежи на нея. В дадения пример най-голямата цифра на линия A е 5, на линия B - 7, на линия E - 6, на линия H - 0, на линия J - 8 и т.н.
Съставете програма, която по дадени най-големи цифри във всяка от дванадесетте линии намира най-малката и най-голямата сума от цифри на всички клетки от дъската.
ВХОД
Първият ред на текстовия файл STAR.IN съдържа 12 цифри - най-голямата цифра в линия A, най-голямата цифра в линия B, …., най-голямата цифра в линия L. Всеки две съседни цифри са разделени точно с един интервал.
Пример:
5 7 8 9 6 1 9 0 9 8 4 6
ИЗХОД
В изходния файл STAR.OUT запишете на един ред две цели числа: най-малката и най-голямата възможна сума от цифри във всички клетки на дъската. Стойностите трябва да бъдат разделени с точно един интервал.
Ако не съществува разположение на цифрите в клетките, за да се изпълнят дадените условия, трябва да запишете "NO SOLUTION" на единствения ред от изходния файл.
Пример:
40 172
ОПИСАНИЕ НА АЛГОРИТЪМА:
Алгоритмите за намиране на най-малката и най-голямата възможни суми
нямат почти нищо общо един с друг и поради това ще ги разгледам
поотделно. Но преди това ще започна с някои уточнения.
Това беше най-нестандартната задача от двата дни на олимпиадата.
Решаването и се свеждаше основно до три подпроблема: първо - да се
разбере условието; второ - да се изберат подходящи структури за
представяне на дъската; трето - да се измисли какво да се прави
по-нататък. На първия "проблем" няма да се спирам. Що се отнася до
втория, номерирал съм клетките от 1 до 48 отгоре надолу и отляво
надясно. Някои линии се състоят от 11 клетки, други от 9. В масива
Lines се пази информация за всяка линия кои номера клетки влизат в нея.
Въвеждането на тези данни на ръка отнема около 10 минути.
Намирането на най-голямата възможна сума определено е по-лесната
половина от задачата. В тази програма го правя по доста праволинеен
начин - пазя си един масив Cells от 1 до 48 в който за всяка клетка
отбелязвам каква цифра съдържа. Запълването на този масив става по
следния начин: За всяка линия (от A до L) се опитвам да запиша в
принадлежащите й клетки съответната за линията най-голяма цифра.
Записването в дадена клетка не се осъществява, ако там вече е била
записана по-малка стойност. Ако трябва да се запише по-малка стойност
от намиращата се в клетката в момента, това се прави. Ако за дадена
линия не сме променили стойността на нито една клетка, значи не
съществува решение. Разбира се, първоначално инициализираме всички
клетки с 10. Сложността на този алгоритъм е O(12*11).
Стигнахме до най-малката възможна сума. За намирането й ми се наложи
да използвам един спомагателен масив CellLines (48*3), който за всяка
клетка указва кои 2 или 3 линии минават през нея. Можем да минем и без
този масив, но това ще увеличи сложността на алгоритъма. Следва
описанието на самия алгоритъм.
На най-малката възможна сума съответства дадена конфигурация на
дъската. Очевидно, трябва в почти всички клетки да има нули, а в
максимум 12 добре подбрани клетки да бъдат записани някои от 12-те
максимални за дадена линия цифри. Също така е очевидно, че ако дадена
цифра се среща между 12-те максимални, то тя трябва да присъства и на
дъската. Обратно, ако дадена цифра не се среща между 12-те максимални,
няма смисъл тя да бъде поставяна на дъската. Ще илюстрирам с пример
начина, по който ще се опитваме да минимизираме най-малката възможна
сума: нека три от "максималните" цифри са 6. Проверяваме дали е
възможно да поставим някъде по дъската една 6-ца така че тя да е обща и
за трите съответни линии и максимална за всяка от тях. Ако не е
възможно, очевидно на дъската ще трябва да има поне две 6-ци. Ето и
по-детайлно описание на алгоритъма: За всяка линия помним дали тя е
"удовлетворена", т. е. дали вече в някоя от клетките й е била поставена
съответната за линията максимална цифра. Правим един repeat-until цикъл
докато всяка линия бъде "удовлетворена". Вътре в цикъла избираме някоя
все още "неудовлетворена" линия и поставяме съответната й максимална
цифра в някоя от клетките й, така че да бъдат "удовлетворени"
максимален брой други линии. Все пак, внимаваме да не поставим в дадена
линия цифра, по-голяма от максималната за нея. Ако в края на крайщата
не успеем да "удовлетворим" всички линии, значи няма решение.
Сложността на алгоритъма е O(12*11*3), където тройката идва от това, че
през всяка клетка минават максимум три линии.
ПРОГРАМА (STAR.PAS):
{ Това са входните данни:
5 7 8 9 6 1 9 0 9 8 4 6
}
program Star;
{$A+,B-,D+,E+,F-,G+,I-,L+,N-,O-,P-,Q-,R-,S-,T-,V-,X+}
{$M 16384,0,655360}
const
Lines : array['A'..'L',1..11] of Byte =
(( 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15), {A}
( 0, 16, 17, 18, 19, 20, 21, 22, 23, 24, 0), {B}
( 0, 25, 26, 27, 28, 29, 30, 31, 32, 33, 0), {C}
( 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44), {D}
( 34, 35, 25, 26, 17, 18, 8, 9, 2, 3, 1), {E}
( 0, 36, 37, 27, 28, 19, 20, 10, 11, 4, 0), {F}
( 0, 45, 38, 39, 29, 30, 21, 22, 12, 13, 0), {G}
( 48, 46, 47, 40, 41, 31, 32, 23, 24, 14, 15), {H}
( 48, 46, 45, 38, 37, 27, 26, 17, 16, 6, 5), {I}
( 0, 47, 40, 39, 29, 28, 19, 18, 8, 7, 0), {J}
( 0, 42, 41, 31, 30, 21, 20, 10, 9, 2, 0), {K}
( 44, 43, 33, 32, 23, 22, 12, 11, 4, 3, 1)); {L}
var
F : Text;
Flag,NoSolution : Boolean;
Ch : Char;
I,J,K,L,MaxLines,MaxCell,MaxNum,ReadyCnt,Minimum,Maximum : Integer;
MaxDigits : array['A'..'L'] of Integer;
Ready : array['A'..'L'] of Boolean;
Cells : array[1..48] of Byte;
CellLines : array[1..48,1..3] of Char;
BEGIN
{ Read input file: }
Assign(F,'STAR.PAS'); FileMode:=0; Reset(F); ReadLn(F);
for Ch:='A' to 'L' do Read(F,MaxDigits[Ch]);
Close(F);
{ Find maximum: }
NoSolution:=False;
FillChar(Cells,SizeOf(Cells),10);
for Ch:='A' to 'L' do
begin
Flag:=False;
for I:=1 to 11 do
if (Lines[Ch,I]>0) and (MaxDigits[Ch]<=Cells[Lines[Ch,I]]) then
begin Cells[Lines[Ch,I]]:=MaxDigits[Ch]; Flag:=True; end;
if not Flag then NoSolution:=True;
end;
Maximum:=0;
for I:=1 to 48 do Inc(Maximum,Cells[I]);
{ Build CellLines: }
FillChar(CellLines,SizeOf(CellLines),#0);
for Ch:='A' to 'L' do for I:=1 to 11 do
if CellLines[Lines[Ch,I],1]=#0 then CellLines[Lines[Ch,I],1]:=Ch
else if CellLines[Lines[Ch,I],2]=#0 then CellLines[Lines[Ch,I],2]:=Ch
else CellLines[Lines[Ch,I],3]:=Ch;
{ Find minimum: }
Minimum:=0; ReadyCnt:=0;
FillChar(Cells,SizeOf(Cells),0);
FillChar(Ready,SizeOf(Ready),False);
for Ch:='A' to 'L' do if MaxDigits[Ch]=0 then
begin Ready[Ch]:=True; Inc(ReadyCnt); end;
repeat
{ Find a cell which will satisfy maximum lines: }
MaxLines:=0;
for Ch:='A' to 'L' do if not Ready[Ch] then Break;
if Ready[Ch] then Break;
for I:=1 to 11 do
begin
K:=Lines[Ch,I]; if (K=0) or (Cells[K]<>0) then Continue;
Flag:=False; L:=0;
for J:=1 to 3 do if CellLines[K,J]<>#0 then
begin
if MaxDigits[CellLines[K,J]]<MaxDigits[Ch] then
begin Flag:=True; Break; end;
if (not Ready[CellLines[K,J]]) and
(MaxDigits[CellLines[K,J]]=MaxDigits[Ch]) then
Inc(L);
end;
if Flag then Continue;
if L>MaxLines then
begin MaxLines:=L; MaxCell:=K; MaxNum:=MaxDigits[Ch]; end;
end;
if MaxLines=0 then Break;
Cells[MaxCell]:=MaxNum;
for J:=1 to 3 do if CellLines[MaxCell,J]<>#0 then
if MaxDigits[CellLines[MaxCell,J]]=MaxNum then
Ready[CellLines[MaxCell,J]]:=True;
Inc(ReadyCnt,MaxLines);
Inc(Minimum,MaxNum);
until ReadyCnt>=12;
if ReadyCnt<12 then NoSolution:=True;
{ Write output file: }
Assign(F,''); FileMode:=2; Rewrite(F);
if NoSolution then
WriteLn(F,'NO SOLUTION')
else
WriteLn(F,Minimum,' ',Maximum);
Close(F);
END.
Автор на решението:
Петър Иванов Петров,Факултет по Математика и Информатика (ФМИ),
1 курс, спец. Информатика
е-mail: piettropro@fmi. uni-sofia. bg