Informatika gyűjtemény

Egy szinttel feljebb fg_fazekasr.dpr

2004050607080910

<<  2. óra  >>

<<  Fazekas  >>

NézetNyomtat

fg_fazekasr.dpr (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 2 KB
{$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.
(Vissza)