Cod sursa(job #38277)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 25 martie 2007 16:56:09
Problema Dezastru Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.94 kb
{generarea permutarilor}
program backtracking;
type sir=array[1..1000] of integer;
var st:sir;
    f,g:text;
    p,q:array[1..1000] of real;
    n,k,k1,i:integer;
    asta,ev:boolean;
    s:real;
    nr:longint;
    sol:string;

procedure citire;
var i:integer;
begin
     assign(f,'dezastru.in');reset(f);
     readln(f,n,k1);
     for i:=1 to n do read(f,p[i]);
     close(f);
end;

procedure initializare(k:integer;var st:sir);
begin
     st[k]:=0;
end;

procedure succesor(var asta:boolean;var st:sir;k:integer);
begin
     if st[k]<n then
                    begin
                         st[k]:=st[k]+1;
                         asta:=true;
                    end
                 else asta:=false;
end;

procedure validare(var ev:boolean;st:sir;k:integer);
var i:integer;
begin
     ev:=true;
     for i:=1 to k-1 do
              if st[k]=st[i] then ev:=false;
end;

function solutie(k:integer):boolean;
begin
     solutie:=(k=n);
end;

procedure tiparire;
var i:integer;
begin
     inc(nr);
     q[nr]:=1;
     for i:=1 to k1 do q[nr]:=q[nr]*p[st[i]];
end;

BEGIN
     k:=1;
     citire;
     nr:=0;
     initializare(k,st);
     while k>0 do
           begin
                repeat
                      succesor(asta,st,k);
                      if asta then validare(ev,st,k);
                until (not asta) or (asta and ev);
                if asta then
                   if solutie(k) then tiparire
                                 else
                                     begin
                                          k:=k+1;
                                          initializare(k,st);
                                     end
                       else k:=k-1;
           end;
     s:=0;
     for i:=1 to nr do s:=s+q[i]/nr;
     assign(g,'dezastru.out');rewrite(g);
     str ( s , sol);
     writeln ( copy(sol,1,pos('.',sol)) , copy(sol,pos('.',sol)+1,5) );
     close(g);
END.