ЗВЕЗДА

Национална олимпиада по информатика,

Финален (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