386 Dezastru

[•DITzoneC]

Aici puteţi discuta despre problema Dezastru.

[•raduzer]

ce optimizari as putea face daca am facut un back in care am luat toate combinarile de k numere astfel incat ele sa fie luate crescator(un grup sa fie luat o singura data) ? ca iau 70 de puncte si 3 TLE

[•ctes]

probabil fara back.... 

[•CezarMocan]

Nu, si solutia oficiala e cu back...

[•skyel]

poi si atunci cum...k io cu back iau 4 tle..si nu folosesc in functia de back mai deloc memorie...
LE: la sol oficiala nu precizeaza nimic de back, si nici nu spune ca ar obtine 100 cu combinari....

[•bogdan2412]

Se ia 100 cu Combinari de N luate cate K.. nu folosi long double cum am facut eu in concurs .
Vezi ca daca esti la pasul k in stiva poti limita superior valoarea care poti s-o pui ( cand faci combinari tii valorile ordonate crescator in stiva ).

[•CezarMocan]

Exact asta fac si eu...combinari de n luate cate k, in stiva pe pozitia i pun de la st[i-1]+1 pana la n si iau doar 60 cu TLE.
Trebuie facut back-ul iterativ??

[•skyel]

da ce rost are sa tii minte elementele combinarii?

[•domino]

Daca nu va intra in timp, puteti incerca oricand o solutie cu programare dinamica 

[•CezarMocan]

Mda...  . Totusi, am inceput cu back si vreau sa o duc la bun sfarsit asa... nu ma dau eu batut...

[•Bluedrop_demon]

Referitor la metoda back... se pot face niste optimizari pentru a vedea pe fiecare nivel intre ce valori poti considera elementul din permutare. De asemenea poti face vectorul lista simplu inlantuita iar restul variabilelor alocate dinamic. Preluandu-ti ideea am facut asa si zic eu ca mai rapid e imposibil...

Cu o astfel de solutie obtii maxim 70p, deci cred ca intr-adevar trebuie programare dinamica!

[•Florian]

Cod:

 Problema se poate rezolva si folosind prgramarea dinamica. 
Se construieste matricea Ai,j cu semnificatia suma tuturor produselor de j
 factori alesi din primele i numere. Recurenta se poate calcula usor Ai,j=Ai-1,j+Ai-1,j-1*Pi. 
Probabilitatea ceruta va fi An,k impartita la Cn,k (combinari de n luate cate k). 

Care ar trebui sa fie initializarea matricei A? Am initializat A[0,0] cu 1 si nu iese...

[ Gata! S-a rezolvat... ]

[•taloibogdan]

O mica problema -> cand nu inchid fisierul de intrare imi da 2 de non-zero exit status, cand inchid fisierul de intrare imi da 7 de non-zero exit status
  Care-i treaba?

[editat de moderator: cred ca in forma asta mesajul este mai lizibil]

[•devilkind]

vezi ca nu prea cred ca ai scris corect acolo. Incearca sa postezi din nou, de data asta mai clar ce se intampla.

[•taloibogdan]

       Lucrez in Pascal;
       Am facut programul dar am uitat sa dau close(f)->f=fisierul de intrare; l-am trimis si am primit 2*raspuns corect , 3*raspuns gresit , 2*non-zero exit status si 3*time limit exceeded
       Mi-am dat seama de greseala si am inchis fisierul, apoi am trimis problema si am primit 7*non-zero exit status si 3*time limit exceeded.

[•Florian]

Deci...poate folosesti memorie nedeclarata [vectori declarati prea mici], sau poate ai gresit numele fisierelor! 

[•taloibogdan]

  NUP!!

[•Darth_Niculus]

  Folosesti vre-un halt() prin program?   (sau nush cum era exit() in Pascal)

[•wefgef]

Daca ne spui ca iei non-zero exit status nu inseamna prea mult, si ne este greu sa ne dam seama care ar putea fi problema (eventual o ghicim). Incearca sa explici pe scurt ce faci.

[•DITzoneC]

Vezi ca non-zero exit status primesti si daca imparti la 0.

[•taloibogdan]

Nu folosesc exit,halt,break,etc.,etc.

Fac combinari de n luate cate k.Pentru fiecare combinare inmultesc rezultatele si le adun cum zice in problema.Formula nu are nimic.

Nu impart nimic la 0. Variabila cu care impart e minim 1

[•DITzoneC]

Vezi sa nu iti dea un overflow pe la calculul combinarilor, in urma caruia sa ajungi sa imparti la 0. 

[•astronomy]

De ce nu postezi undeva codul sursa, poate asa cineva isi da seama ce gresesti 

[•taloibogdan]

Uite programul.
Eu stiam ca nu e voie sa se posteze sursele.

Cod:

Program dezastru;
Var f:text;
    i,k,n,p,nn,nk,kk:longint;
    s,pp:real;
    c:array[1..8000] of byte;
    a:array[1..8000] of real;
Begin
  assign(f,'dezastru.in');
  reset(f);
  readln(f,n,k);
  nn:=1;
  for i:=1 to n do begin nn:=nn*i; read(f,a[i]); end;
  nk:=1;
  for i:=1 to n-k do nk:=nk*i;
  s:=0.0;
  pp:=1.0;
  kk:=1;
  for i:=1 to k do begin kk:=kk*i; c[i]:=i; pp:=pp*a[c[i]]; end;
  s:=s+(pp/(nn div nk))*kk;
  if k<>n then
  repeat
   c[k]:=c[k]+1;
   if c[k]=n+1 then
     begin
      p:=k-1;
      while (p>0) and (c[p]=n-k+p) do p:=p-1;
      c[p]:=c[p]+1;
      for i:=p+1 to k do c[i]:=c[i-1]+1;
     end;
    pp:=1.0;
    for i:=1 to k do pp:=pp*a[c[i]];
    s:=s+(pp/(nn div nk))*kk;
  until(c[1]=n-k+1);
  close(f);
  assign(f,'dezastru.out');
  rewrite(f);
  Writeln(f,s:0:6);
  close(f);
End.

[•pauldb]

Incearca sa folosesti extended in loc de real.
25! nu prea intra in longint.

Eu stiam ca nu e voie sa se posteze sursele.

Nu prea e voie, dar nu ajungeam niciunde. Si oricum sursa ta nu prea merge.

Si te rog nu mai folosi toate smileyurile pe care le ai la dispozitie pentru ca devii enervant.