Cod sursa(job #789288)

Utilizator 7lymHidden 7lym Data 17 septembrie 2012 19:01:39
Problema Energii Scor 5
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.33 kb
type ak47=^element;
    element = record
    nr,pret:integer;
    raport:real;
    leg:ak47;
 end;

var p,r,prim:ak47;s,min,pr,n,x:integer;f,g:text;


begin
        assign(f,'energii.in');
        assign(g,'energii.out');

        reset(f);

        readln(f,n);readln(f,x);
        prim:=nil;

        for s:=1 to n do begin
                new(r);
                readln(f,r^.nr,r^.pret);
                r^.raport:=r^.pret/r^.nr;
                p:=prim;
                if prim=nil then  begin
                        r^.leg:=prim;
                        prim:=r;
                end
                else
                if ((r^.raport<p^.raport) or ((r^.raport=p^.raport) and (r^.nr>=p^.nr))) then begin
                        r^.leg:=p;
                        prim:=r;
                end
                else begin
                min:=0;
                        while (p^.leg<>nil) and (min=0) do
                                if (r^.raport>p^.leg^.raport) then p:=p^.leg
                                else min:=-1;
                        min:=0;
                        while (p^.leg<>nil) and (min=0) do
                        if (r^.nr<p^.leg^.nr) and (r^.raport=p^.leg^.raport)then p:=p^.leg
                                else min:=-1;
                        r^.leg:=p^.leg; p^.leg:=r;
                end;
        end;
        close(f);


        p:=prim;s:=0;pr:=0;
        while (s<x) and (p<>nil) do begin
                if p^.nr+s<=x then begin
                        s:=s+p^.nr;
                        pr:=pr+p^.pret;
                        p:=p^.leg;
                end
                else begin
                        min:=p^.pret; n:=p^.nr; p:=p^.leg;
                        while p<>nil do  begin
                                if p^.nr>=x-s then
                                        if min<p^.pret then begin
                                                min:=p^.pret;
                                                n:=p^.nr;
                                        end;
                                p:=p^.leg;
                        end;
                        pr:=pr+min;
                        s:=s+n;
                end;
        end;

        rewrite(g); write(s);
        if s>=x then write(g,pr)
        else write(g,'-1');
        close(g);
end.