168 Numarare triunghiuri

[•gicurez]

WOW,  am invatat ceva azi.
Multumesc mult de tot ; chiar merge  multumesc frumos inca o data pentru ajutor, momentele astea in care ne ajutam unii pe altii sunt poate cele mai minunate din toata viata noastra, a fost incredibil ce am simtit azi si acum, iti multumesc mult inca o data. sa ai bafta in continuare la olimpiade si in viata. Sa iesi pe si sa ai grija de tine. Salut

[•ciprianf]

In solutiile oficiale scrie ca trebuie sa sortam vectorul nedescrescator.......a sorta nedescrescator  nu inseamna a sorta crescator, ci doar a sorta oarecum aleatoriu astfel incat sa nu fie descrescator(iar pe cautare binara merge decat cu crescator si descrescator).....nu am dreptate?

[•bogdan2412]

O functie e "crescatoare" daca oricare ar fi x < y, f(x) < f(y).
O functie e "nedescrescatoare" daca oricare ar fi x < y, f(x) <= f(y).

Asa e in engleza cel putin... Se intelege destul de clar ce se vrea...

[•catalin93]

Gata, am modificat.

si totusi vreau si eu sa te intreb de ce in exemplu e
4
2 3 7 4   2 (care e corect)
iar explicatia e ca variantele sunt
1, 2, 4
2, 3, 4
cand acestea sunt :
2 3 7
2 4 7

[•pauldb]

Singurele triunghiuri care se pot forma sunt alcatuite din urmatoarele betisoare (date prin numarul de ordine):
1, 2, 4
2, 3, 4

Citeste mai atent.

[•catalin93]

corect scuzele mele

[•DraStiK]

ma ajuta cineva si pe mine va rog cu un test mai urat sau daca binevoieste cineva sa vada sursa

http://infoarena.ro/job_detail/237622

iau doar 55, si fac ca toata lumea cu cautare binara

[•c_e_manu]

eu buseam la cautarea binara  ... trimite-mi sursa pe prv daca vrei

[•Bit_Master]

De unde vine betisorul de lungime 1?

A. Sunt pozitii. Ar trebui specificat. 

Editat de moderator: Nu mai posta succesiv. Editeaza-ti mesajele precedente!

[•pauldb]

E foarte clar specificat.

[•vlad_oltean]

cu o mica optimizare se pot scoate 100p si cu O(n^3). dar cautarea binara intra muuuult mai lejer in timp

[•Florian]

Ce optimizare?

[•vlad_oltean]

Ce optimizare?

in al 3lea for, nu parcurgi vectorul pana la capat, ci pana gasesti prima valoare care nu mai respecta conditia v[ i ]+v[ j ]<=v[ k ]. pentru ca ai sortat dinainte vectorul, conditia va fi falsa si pentru toate valorile de dupa acest k. in practica folosesti un mic break.

sper ca am fost clar

[L.E.] Cred ca ar putea fi modificate testele astfel incat sa descurajeze folosirea smecheriei asteia adica conditia de care ziceam sa devina falsa spre sfarsitul vectorului, astfel incat sa nu mai conteze foarte mult la timp break-ul ala.

[•gabor_oliviu1991]

Cat da pentru testul :

Cod:

20
7 10 5 2 8 9 14 6 5 3 5 12 17 4 3 1 9 3 4 16

Mie imi da 482. Scot doar 50 de puncte si nu imi dau seama ce are 

[•toni2007]

539

[•ucc_5]

Wait a sec, cum adica , conditia e ca a+b<=c ? pai daca a+b=c atunci inaltimea e 0 deci aria e 0 deci triunghiul nu exista. Prin urmare conditia nu ar trebui sa fie defap a+b<c ?

[•gabitzish1]

Exista si triunghiul cu inaltimea 0. Daca ai 3 puncte in plan, ele pot determina un triunghi; daca sunt coliniare, triunghiul format de ele are inaltimea 0.

[•ms-ninja]

se poate face problema fara cautare binara....

se sorteaza, eu am folosit quick-ul

cu 2 for-uri
nr=0;
   for(i=1;i<=n-2;++i)
      for(j=i+1;j<=n-1;++j)
         {
            int k=j+1;
            while(v+v[j]>=v[k] && k<=n)
               ++k;
            
         
            nr+=k-j-1;
            
         }

iei 100 pct pe asta pe cel mai mare timp am scos 64 ms, dublu fata de cautare binara:)

[•zeroblitz36]

Mie mia iesit in O(n^3) cu 100p. Sami explice si mie cineva cum poate fi folosita cautarea binara aicea  .
Deci din ce banuiesc eu.
Sortez descrescator.
for(i=0;i<n-2;i++)
for(j=i;j<n-1;j++)
si apoi caut cel mai mic si cel mare numar (prin cautare binara) care poate face trunghi cu celelate doua ?

[•dutzul]

apropo se poate cauta primul x<=val intrun hash? fara a sorta nimic?

[•maritim]

Nu, hash-urile nu tin niciun fel de ordine. Pentru ceea ce ceri tu ai nevoie, ori de alta structura de date, ori de o sortare si apoi sa cauti binar!

[•rarescostache]

FRATE!..... 

[•DorelBarbu]

In mod sigur nu gandesc bine, dar nu stiu de ce. Inegalitatea triunghiului afirma ca suma a doua laturi este mai mare ca cea de a treia. Dar de ce este suficient sa verificam daca:

if (a[k]<=a+a[j])

si nu trebuie sa luam in cnsiderare si celalate cazuri: a[j]<=a[k]+a si a[<=a[j]+a[k]. Imi scapa ceva... . Ar putea cineva sa ma lamureasca si pe mine? 


EDIT: Mi-am dat seama ))))

[•ionut98]

mie imi merge si fara cautare binara

[•theprdv]

se considera triunghiuri si cele care au un unghi de 180 de grade si celelalte doua de 0 grade (2 segmente coliniare se confunda cu al 3-lea)

dupa enunt se poate forma si triunghiul 2 3 4  (4 + 3 <= 7).. e gresit enuntul sau nu inteleg eu bine?