Cod sursa(job #789249)

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

var p,r,prim:ak47;s,min,pr,i,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 i:=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
                        if p^.leg<>nil then  begin
                        while (r^.raport>p^.leg^.raport) and (p^.leg<>nil) do p:=p^.leg;
                        while (r^.nr<p^.leg^.nr) and (r^.raport=p^.leg^.raport) and (p^.leg<>nil) do p:=p^.leg;
                        end;
                        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; p:=p^.leg;
                        while p<>nil do  begin
                                if p^.nr>=x-s then
                                        if min<p^.pret then min:=p^.pret;
                                p:=p^.leg;
                        end;
                        pr:=pr+min;  writeln(min);
                end;
        end;

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


        p:=prim;
while p<>nil do begin
writeln(p^.nr, ' ', p^.pret, ' ' , p^.raport:0:3);
p:=p^.leg;
end;
end.