{$A+,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S-,T-,U-,V+,W-,X+,Y+,Z1}
{$MINSTACKSIZE $00004000}
{$MAXSTACKSIZE $00100000}
{$IMAGEBASE $00400000}
{$APPTYPE CONSOLE}
PROGRAM fazekasr;
CONST
ch = '8';
inputFile = 'FAZEKAS'+ch+'.BE';
outputFile = 'FAZEKAS'+ch+'.KIX';
maxn = 10000;
VAR
N, K: INTEGER;
{az egetesi idok listaja:}
list: ARRAY [1..maxn] OF RECORD
E: BYTE;
END;
cache: ARRAY [1..maxn+1] OF INTEGER;
choice: ARRAY [1..maxn] OF BYTE;
PROCEDURE Load;
VAR
T: Text;
i: INTEGER;
BEGIN
Assign(T, inputFile);
Reset(T);
ReadLn(T, N, K);
FOR i:= 1 TO N DO
BEGIN
ReadLn(T, list[i].e);
END;
Close(T);
END; {Load}
{megadja az elso_targy, ..., N indexu targy-sorozat legjobb egetesi idejet}
FUNCTION Best(elso_targy: INTEGER): INTEGER;
VAR
i: INTEGER;
max: INTEGER; {az aktualisan berakott targyak e. ideje}
ido: INTEGER; {max + a maradek targyak e. ideje}
tmp: INTEGER;
BEGIN
IF elso_targy > N THEN cache[elso_targy]:= 0;
IF cache[elso_targy] = -1 THEN
BEGIN
{ha meg nincs tarolt ertek}
max:= 0;
{tmp a legnagyobb indexu targy, amit meg az elso_targy-al berakhatunk a kemencebe:}
tmp:= elso_targy+K-1;
IF tmp > N THEN tmp:= N;
{vegigprobalgatjuk, hogy mennyi lesz az egetesi ido, ha
1, 2, ..., i-elso_targy+1 targyat teszunk a kemencebe}
FOR i:= elso_targy TO tmp DO
BEGIN
{a bekerulo targyak egetesi ideje, az egyedi egetesi idok maximuma...:}
IF list[i].e > max THEN max:= list[i].e;
{a teljes egetesi ido ennyi berakott targy eseten}
ido:= max + Best(i+1);
{ha jobb idot talaltunk a legutobbinal, vagy nem volt legutobbi:}
IF (cache[elso_targy] = -1) OR (ido < cache[elso_targy]) THEN
BEGIN
cache[elso_targy]:= ido;
choice[elso_targy]:= i-elso_targy+1;
END;
END;
END;
Best:= cache[elso_targy];
END; {Best}
PROCEDURE Process;
VAR
T: Text;
i: INTEGER;
BEGIN
Assign(T, outputFile);
Rewrite(T);
FOR i:= 1 TO N DO cache[i]:= -1;
WriteLn(T, Best(1));
{eloallitjuk az optimalis targy-sorozatot:}
i:= 1;
WHILE i <= N DO
BEGIN
WriteLn(T, i, ' ', i+choice[i]-1);
i:= i+choice[i];
END;
Close(T);
END; {Process}
BEGIN
Load;
Process;
END.
2004-2016 BDG algoritmus szakkör