ce prompt esti
pai cum fac?
Multumesc

Ce complexitate are cel mai bun algoritm de descompunere a unui numar in factori primi?
Multumesc

Eu inteleg asa:
O sa reduc numarul de accesari la disk cu m/2, unde m este numarul de linii cu cate doua elemente (o sa fac atatea accesari ale diskului cate linii am).
Eu ma intrabam daca pot citi intr-un buffer o data mai multe numere, chiar de pe linii diferite

Tinand cont ca elementele sunt cate unu si doua pe linie, cum parsez citirea (ce functie folosesc)?

In enunt zice ca:

Numerele reprezentand valoarea unui Euro in RON au toate exact patru cifre in partea zecimala si sunt distincte

Mai intai am trimis o sursa in care memorez datele ca long int inmultindu-le cu 10000. Iau 80 puncte.
Cand lucrez cu ele ca float iau 100.

Eu am plecat de la ideea prin care se verifica daca o secventa poate reprezenta gradele unui graf neorientat.
Unde gasesc solutia oficiala?

Eu fac asa:
Intai sortez dupa gradele exterioare, apoi, parcurg descrescator si distribui fiecare grad exterior la gradele interioare, si acestea sortate descrescator (sortarea descrescator a gradelor interioare o fac repetat, dupa fiecare distribuire a unui grad esterior).
Timpii de executie sunt foarte buni insa iau doar 55 puncte. Este gresita ideea ?

Are ceva special testul 1? E singurul pe care iau incorect

La Kcover fac asa:
- sortez dupa x.
- determin cele n-1 intervale si le sortez dupa lungime
- elimin cele mai mari k-1 valori din sir.

Iau decat un test, pe unul tle iar pe celelalte 2 incorect. Gresesc la algoritm?

Multumesc Bogdan,
Te-as ruga sa imi scrii si niste probleme care folosesc principiul cutiei ...

As dori si eu cateva probleme de pe site care folosesc strategii de castig pebtru jocuri si altele pentru principiul cutiei lui Dirichlet

Multumesc

La unele dintre problemele din arhiva educationala apare si sectiunea: probleme de pe infoarena care folosesc tehnica respectiva. Ma gandesc ca ar fi util ca la toate sa apara asta.
As dori si eu dinamici asemanatoare cu:
1 cel mai lung subsir comin a 2 siruri;
2 dinamica mixta (gen parantezari)
3 distanta minima de trecere intre doua cuvinte
4 alte clasice n2 sau n3

Mumtumesc

scuze ca postez aici ...
imi zice si mie cineva o problema din arhiva care implica dinamica de trecere dintr-un cuvant in altul cu numar minim de operatii ...

Multumesc

1 considerat e prim?

Un hint ... ?

Am mai incercat sa fac problema modificand solutia de la cezar. Am scris chiar si de la 0 codul. Obtin Killed by ...

devilkind : da-mi si mie o idee de o(n+m)

Da, mi-am dat seama, vectorul cu intrebari il puneam tot de 250000 ...

Am facut o parcurgere in adancime. Am incercat sa merg pe aceeasi idee ca la problema cerere (la care am luat 100p). Pentru fiecare nod tin o lista de cereri pentru stramosii lui (memorez in noduri stramosul cerut si pozitia in lista de cereri).
In parcurgerea in adancime, tin o stiva cu nivele si cand sunt la un nod, parcurg lista de cereri si caut in stiva de nivele.  Complexitate n+m
Iau 80 p, pe testul 9 WA iar pe 10 Killed by signal 11.
Ce gresesc ?

am modificat.
Pe exemplu merge. Nu stiu de unde sa dea killed ...

Problema asta cred ca este similara cu cezar(515 in arhiva, data la oji). Trimit aceeasi sursa cu dimensiunile modificate (cu k=0) si primesc Killed by signal 11(SIGSEGV). pe 9 teste iatr pe ultimul incorect. Ce gresesc ?

multumesc mult!

Eu lucrez cu 2 vectori in care retin: v[ i ] - nr minim de pasi de a fi ajuns la treapta i si p[ i ] - pretul minim de a fi ajuns la treapta i in v[ i ] pasi.
Parcurg i de la 1 la n si de pe scara i analizez cele 3 cazuri de a actualiza v si p pentru scarile de dupa i (beau apa, beau energizanta, urc normal). cand v[ j ]>v[ i ] (cu j dupa i) actualizez v[ j ]=v[ i ]+1 si p[ j ], iar cand v[ j ]=v[ i ]+1 actualizez p[ j ]. Plec cu v[1]=1 si p[1]=0 si afisez v[n] si p[n].
Unde gresesc ? (iau 35 p, in rest WA)...