027 Loto

[•Mishu91]

Evaluatorul este oprit momentan

[•venom4u31]

Sper ca nu pentru mult

[•Alin1771]

rezolvarea mea este urmatoarea:

Cod:

var
s,p:longint;
k,j,i,n:integer;
x,l:array[1..100] of integer;
f,g:text;
begin
assign(f,'loto.in');reset(f);
assign(g,'loto.out');rewrite(g);
read(f,n,s);   readln(f);
for k:=1 to n do read(f,l[k]);
for k:=1 to 6 do x[k]:=l[1];
k:=0;
j:=6;
p:=x[k]*6;
while (p<>s) and (j>0) do begin
p:=0;
inc(k);
x[j]:=l[k];
   for i:=1 to 6 do p:=p+x[i];
if k=n then begin k:=1;j:=j-1;end;
end;
if p<>s then write(g,-1) else write(g,x[1],' ',x[2],' ',x[3],' ',x[4],' ',x[5],' ',x[6]);
close(f);
close(g);
end.

imi poate spune si mie cineva de ce primesc zero puncte pe ea?

[edit] Foloseste tag-ul "code" cand postezi cod.

[•sima_cotizo]

Sursa ta imi pare destul de greu de inteles (nu are nici macar niste comentarii). Daca ne-ai spune cum ai gandit tu rezolvarea te-am putea ajuta mult mai usor!

[•Alin1771]

Cod:

....
for k:=1 to n do read(f,l[k]); {introduc in vectorul L numerele date de Loteria Nationala}
for k:=1 to 6 do x[k]:=l[1];{introduc in vectorul x pe toate pozitiile primul numar dat de loteria nationala}
k:=0;
j:=6;
p:=x[k]*6; {echivalent cu for k:=1 to 6 do p:=p+x[k],dar toate elementele din vector sunt egale}

{aici e un fel de backtracking}
while (p<>s) and (j>0) do begin {cat timp p > s sau < s si avem element precedent in vectorul x DO; valoarea lui j indica pozitia in vectorul x pe care sunt facute urmatoarele modificari:}
p:=0;
inc(k);
x[j]:=l[k];
for i:=1 to 6 do p:=p+x[i];{verificam pe pozitia j din vectorul x toate numerele date de loteria nationala pana cand p=s (avem deja numerele castigatoare) sau k=n (am verificat toate numerele date de loteria nationala). p este suma numerelor alese pentru biletul lui Gigel}
if k=n then begin k:=1;j:=j-1;end; {cand am terminat verificarea tuturor numerelor date de loteria nationala pe pozitia j din vectorul x coboram un nivel in vector si atribui la k valoarea 1 intrucat zero nu are sens, x[j] are deja valoarea l[k+1] data la inceput; (k+1 intrucat avem inc(k) inaintea egalarii)}
end; {Daca nu se poate obtine un bilet castigator structura repetitiva se va opri cand j=0 altfel, se va opri cand p=s}
if p<>s then write(g,-1) else write(g,x[1],' ',x[2],' ',x[3],' ',x[4],' ',x[5],' ',x[6]); {aici nu mai e cazul sa explic}
....

sper ca se intelege acum ce am facut, nu ma pricep prea bine sa exprim in cuvinte modul in care gandesc
[editat de moderator] foloseste tagul code cand vrei sa postezi cod sursa.

[•sima_cotizo]

Pai o observatie:

Cod:

k:=0;
p:=x[k]*6; {echivalent cu for k:=1 to 6 do p:=p+x[k],dar toate elementele din vector sunt egale}

x[ 0 ] nu exista de fapt (uita-te la cum ai declarat). Ar trebui sa ai ori k:=1 ori p:=x[ 1 ]*6.

In rest backtrackingul tau mi se pare gresit, desi e foarte probabil sa nu-l fi inteles eu. Eu unul as folosi o procedura recursiva (o poti scrie tu iterativ daca doresti; mentionez ca nu ma simt in largul meu in pascal):

Cod:

procedure back( nivel:integer );
begin
	if ( nivel==7 ) 
		if ( sol==suma_de_la_1_la_6_in_x ) then afisez_solutia;
	else
	for i:=1 to n do 
		if ( Utilizat[i]=0 ) then begin
			x[nivel]:=l[i]
			Utilizat[i]:=1;
			back( nivel+1 );
			Utilizat[i] := 0;
		end;
end;

Vectorul Utilizat[] imi zice daca un numar l-am mai folosit sau nu. "afisez_solutia" si "suma_de_la..." le implementezi tu mai pe larg

Totusi, nu cred ca un back e solutia buna mai citeste si pe topicul problemei poate prinzi si alte idei de rezolvare

[•ooctav]

iau WA pe testele 7,11,13,14,15,16,18 ... imi poate da un hint cineva care cunoaste testele ?

[•c_e_manu]

descrie putin metoda ta de rezolvare

[•ooctav]

stie cineva testul 7 ?

[•devilkind]

Testele nu sunt publice.

[•lsorin_94]

ce tip de fis e CPP-ul??

[•madlex]

check comments

[•ucc_5]

Ce chestie quicksortul meu e de 10 ori mai incet decat sortul din stl. M-am chinuit 2 ore cu sorturi si m-am lasat pagubas, l-am lasat pe cel din stl. Voi ce algoritm de sortare ati folosit ?

[•Pepelea_Flaviu]

Merge foarte bine cu heapsort 

[•zloteanu.adrian]

Nu inteleg unde se blocheaza.. nu poate fi decat de la sortare:

Cod:

#include<fstream>
#include<algorithm>
using namespace std;
...
int cmp(int a,int b)
{return a<b;}
int main()
...
sort(v2+1,v2+f+1,cmp);
...
return 0;}

http://infoarena.ro/job_detail/346850
Any ideas?

[•xtreme]

In cazul in care elementele din vectorul v2 incep de pe pozitia 1 si se termina pe pozitia f si vrei sa sortezi crescator nimic nu e gresit, iar v2 trebuie sa fie de tipul int.S-ar putea ca algoritmul tau sa nu fie optim sau sa fie optim si sa se blocheze in alta parte a codului.
Daca vrei sa te lamuresti mai bine http://www.cplusplus.com/reference/algorithm/sort/.

[•benny]

Stie cineva ce am gresit in sursa urm. de imi da 0 pct.? Am verificat prg. si la mn ruleaza corect si totusi imi da 0 pct.

Cod:

program loto;
uses crt;
var n,i:byte;
    sp:longint;
    g:boolean;
    v,sol:array[1..100]of longint;
procedure ext(i:byte;s:longint);
var x,l:byte;
begin
     if (s=sp)or(i=7)then
        begin
             if (s=sp)and(i=7) then
                g:=true;
        end
     else
          for x:=1 to n do
           if not g then
            if s+v[x]<=sp then
               begin
                    sol[i]:=v[x];
                    ext(i+1,s+v[x]);
               end;
end;
begin
     readln(n);
     readln(sp);
     for i:=1 to n do
         readln(v[i]);
     g:=false;
      ext(1,0);
     if g then
        for i:=1 to 6 do
            write(sol[i],' ')
        else
            writeln(-1);
     readln;
end.

[•toni2007]

Foloseste tag-ul [ code ] (fara spatii) cand postezi surse.

La problema aceasta poti vedea sursele trimise de ceilalti, ia o sursa de 100 de puncte si incearca la tine pe calculator pe un test sa vezi cat ar trebui sa dea.

[•benny]

Cum as putea sa verific timpul in care se ruleaza un prg.?

[•toni2007]

Daca ai linux folosesti functia time din bash. Pt windows folosesti time.h si clock_t. Parca era ceva de genul :

Cod:

#include <stdio.h>
#include <time.h>
int main () {
    clock_t start, finish;
    start = clock();
    ...
    finish = clock();
    printf("%.3lf\n", (finish - start) / CLOCKS_PER_SEC);
}

[•benny]

Ms teodor

[•vladtarniceru]

eu am facut in (n^3)*2+(n^2)+2_sorturi_din_STL,unul_care_sorteaza_n_elem, altul_care_sorteaza_n^3 si am luat 100, dar se poate face mai rapid de atat ? 

ps: cred ca este mai rapid totusi cu operatii pe biti si sume partiale

multumesc

[•sima_cotizo]

Din cate tin minte, mai jos de O(n³) nu se poate (sortare cu radix?), insa o solutie ok este si O(n³log n³)...

Acum sa mi se ierte postul in eventualitatea in care e gresit

PS: My bad am mancat o putere

[•blasterz]

eu am facut in (n^3)*2+(n^2)+2_sorturi_din_STL,unul_care_sorteaza_n_elem, altul_care_sorteaza_n^3 si am luat 100, dar se poate face mai rapid de atat ?  

ps: cred ca este mai rapid totusi cu operatii pe biti si sume partiale

multumesc

Tu ai O(n^3 log (n^3))

Se poate optim in O(n^3) cu hashing

[•vladtarniceru]

multumesc mult, dar pana la urma, solutia cu hashing se face la fel, doar ca in loc de cautare binara faci "Search" (cu hashing)?