776 Kprime

[•wefgef]

Aici puteti discuta despre problema Kprime.

[•drag0s93]

pb asta e corecta? deci rasp ar fi 3 (perechile (1,2),(1,3),(2,3))   .....sau    explikti mi si mie careva .....

[•Mishu91]

1 nu este prim, iar pentru exemplul

Cod:

5 2
1 2 4 3 8

secventele sunt

Cod:

1 2 4 3 8
1 2 4 3
2 4 3 8
2 4 3

Numerele trebuie sa fie pe pozitii consecutive

[•drag0s93]

aa srry ....da am crezut ca doar nr prime sa fie srry  ms 

[•drag0s93]

mai da ti mi si mie un exemplu am facut pb dar nuj imi da killed by signal.....

[•marcelcodrea]

Pentru soluţia problemei Kprime : http://infoarena.ro/algoritmiada-2009/runda-1/solutii#kprime
Pentru mesajele pe care le primeşti de la evaluator : http://infoarena.ro/documentatie/evaluator

[•gabitzish1]

mai da ti mi si mie un exemplu am facut pb dar nuj imi da killed by signal.....

Poti sa faci tu niste teste si sa le postezi aici, sa vezi care e raspunsul celor care au luat 100.

[•wefgef]

Primesti "killed by signal 11" din cauza ca declari o matrice de 10.000 * 10.000 de long long.

[•funkydvd]

Pentru cei interesaţi, problema aceasta se poate rezolva şi în complexitate O(n), cu ajutorul unui vector de frecvenţă.

[•toni2007]

Sunt curios cum . Ai n log n de la ciur oricum.

[•Mishu91]

Ciurul se rezolva in O(N log log N), si in plus numerele sunt mai mici decat 1000, deci complexitatea finala iese O(N)

[•recviem]

Doar o idee: "Elementele sirului vor cuprinse intre 1 si 1000" se poate folosi un sir de constante pentru ciur.

[•siminescu]

nu ma dragos uita.te la comentariul care e inaintea ta
perechile sunt:
1 2 4 3 8
1 2 4 3
2 4 3 8
2 4 3...
nu conteaza cat de lung este sirul ci conteaza sa aiba 2 nr prime

[•Alexa_ioana_14]

Pt sirul: d=(1 2 4 3 am folosit vect v=(0 1 1 2 2), unde v[ i ] reprezinta cate nr prime am pana pe poz i inclusiv si vectorul p=(1 2 2), unde p[ i ] numara cati i am in vectorul v[ i ].
apoi de la 1 la n caut binar x=caut(v[ i ]+m) (daca d[ i ]!=prim) sau x=(v[ i ]+m-1) (daca d[ i ]==prim), iar nr+=p[ v [ x ] ];

pe testele date de mine da bine, dar pe site iau 0pct. Imi poate spune cineva unde gresesc, pls? [ si un contra-exemplu e bun ]

[•Florian]

O solutie simpla este sa retinem intr-un tablou p[] toate pozitile numerelor prime din sirul initial, in ordine crescatoare. Apoi, facem o simpla interatie cu i de la 1 la nr_p (nr_p = numarul elementelor lui p[]) si adaugam la solutie (p[ i ] - p[ i-1 ]) * ( p[j+1] - p[ j ]), unde j = i+K-1, iar p[0] = 0 si p[nr_p+1] = N+1.   

[•cr1st18]

nu inteleg cum se poate folosi cautarea binara aici....?

[•Florian]

Te ajuta http://infoarena.ro/algoritmiada-2009/runda-1/solutii#kprime .

[•shnako]

Ce inseamna "Killed by signal 6(SIGABRT)." ?
Mentionez ca pe MinGW merge perfect.

[•ctlin04]

ma ajuta cineva la problema asta, iau WA pe testele grupate si nu inteleg de ce, am facut programul dupa ideea mentionata mai sus de Florian Marcu pentru ca nu ma prea pricep inca la cautare binara, pentru exemplele mele merge bine, dar totusi ""incorect""

[•ctlin04]

LE: s-a rezolvat doar trebuia sa maresc limitile

[•avram_florin]

imi poate spune si mie cineva ce e gresit in abordarea aceasta ca nu ma prind...

Cod:

for(  int i = 1 ; i <= N ; ++i )
{
scanf("%d" , &A[i] );
if( A[i] & 1 )
if( !ciur[A[i]] )
S[i] = S[i-1]+1;
else
S[i] = S[i-1];
else
if( A[i] == 2 )
S[i] = S[i-1]+1;
else
S[i] = S[i-1];
}
int j1,j2,i,Sol;
j1 = j2 = 1;
Sol = 0;
for( i = 1 ; i <= N ; ++i )
if( S[i] >= K )
{
while( S[j2] + K <= S[i] )
++j2;
while( S[j1] + K < S[i] )
++j1;
Sol += (j2-j1+1);
}

Editat de moderator: Folositi tag-ul code cand postati cod sursa.

[•klamathix]

Niste sfaturi: Daca te referi la ideea de rezolvare, atunci nu posta cod, ci expune-o in cuvinte. Daca te referi la implementare, sa faci debug pe codul altcuiva este foarte greu si pana la urma mult mai putin folositor decat daca persoana in cauza l-ar face singur.