Not a triangle & Z-zidar

Molim za pomoc oko zadataka Not a triangle & Z-zidar! Koja je ideja? Kako da se odradi? Hvala unapred!

ja bi isto htio ideju za not a triangle

not a triangle:
pa za stranice trougla postoji nejednakost: a + b > c ...
ako se degenerisani trougao smatra trouglom onda je nejednakost: a + b >= c
e pa ako uzmes 2 stapica (ili sta su vec) koja recimo imaju duzine l1 i l2, onda treba da odaberes 3. stapic tako da vazi l1 + l2 < l3 !!!
znaci da treba za svaki par (i,j) da izracunas koliko ima stapica koji imaju duzinu vecu od duzina(i) + duzina(j) ...


z-zidar:
pa ovde primenis pitagorinu teoremu: c^2 = a^2 + b^2 (gde je c dijagonala pravouglog trougla, a a i b katete) ...
pa za svaka dva stapa vidis da li je koren(a^2 + b^2) prirodan broj i da li postoji stap sa tom duzinom ...

ako treba jos neka pomoc pitaj ...

Na tvoju ideju Z-zidar mi prodje samo 5/20 a na ostalima vraca TLE. Imas li kakvu ideju da ubrzam kod?

ja sam ti dao samo ideju, a ne citavo resenje ...
kao i u prvom zadatku ...
ako hoces za prvi zadatak citavo resenje napisacu ga ...

Dobro bi mi doslo! Ali bolje je da mi ipak,ako vec hoces,da napises resenje za drugi(Z-zidar),bolje bi mi doslo,ali svejedno,kako je tebi lakse!

z-zidar:

ideja: pa napravis niz sa boolean-ima gde postavis na true sve vrednosti koje imas za duzinu dasaka, tako da ces u O(1) znati da li postoji neka daska sa duzinom L ...
i sada za svake 2 daske (pazis da ti se ne ponavljaju daske) gledas da li je sqrt( sqr(L1) + sqr(L2) ) prirodan broj, ako jeste onda pogledas da li postoji daska duzine sqrt( sqr(L1) + sqr(L2) ) ...
odnosno ti gledas da li za neki par dasaka postoji daska koja moze da bude hipotenuza pravouglog trougla, gde su L1 i L2 katete ...

Removed

not a triangle:

ideja: pa vec sam objasnio ideju, ali nisam rekao kako da u O(1) dobijes koliko ima stapica vecih od L1 + L2 (L1 i L2 su duzine neka 2 stapica) ...
pa to ces uraditi sa nizom u kome ce s[L] znaciti koliko ima stapica koji su jednaki ili veci od duzine L ...
e sada kako ces napuniti taj niz ...
pa ako za svaki stapic koji ima duzinu L povecas s[L] za jedan, onda ce ti s[L] znaciti koliko je stapica sa duzinom L ...
ali kako bi dobio da s[L] drzi podatak koliko je stapica koji su >= L po duzini, onda ce biti s[L] = s[L] + s[L+1] + s[L+2] ... + S[L+MaxDuzina] ...
odnosno ako budes radio od nazad niz s mozes da napunis u O(MaxDuzina) jer ce ti s[L] = s[L] + s[L+1] ...

Removed

nadam se da sam pomogao ... :D

Hvala mnogo na pomoci!

Može pomoć oko Not a triangle?

evo tu je link: http://z-trening.com/submit.php?submit=7100150721&subm_code=1

@matteo123: pa tvoje resenje radi u O( N^2*logN ), sto je 2000*2000*11 = 44 000 000, sto je previse operacija za 0.5 sekundi, gore sam objasnio kako da izbacis ovo logN i onda ces dobiti slozenost O( N^2 ) sto ce proci ...

Jel možeš malo bolje objasniti ideju?

stvar je da ne radis binarnu pretragu...nego da skaldistis za svaki stapic kolko stapica ima vecih od tog sto moze pre pretrage da se uradi u O(n)

hvalal demjane mnogo za z-zidar

demjan0001

Ja sam koristio slicnu ideju kao sto si ti predlozio za resavanje zadatka not a triangle. Medjutim, dobijam WA na 4. testa, ne mogu da vidim gdje je greska pa bi mi pomoc dobro dosla..:)

http://z-trening.com/submit.php?submit=7100338455&subm_code=1

@k(i)nezizbosne: Testiraj se:
5
1 2 4 5 5
ili
1 3 5 5 7
ili
1 2 4 4 4

Mozes li mi dati jos neki primjer? Kada ispravim gresku koju pravi na ovom testu prodjem 4/10 a prije toga je bilo 6/10.
za 1 2 4 5 5 rezultat: 3

1 3 5 5 7 rez: 5

1 2 4 4 4 rez: 3

je li to u redu?

Da.

Pa to mi moj kod i daje. Negdje drugo je problem.
http://z-trening.com/submit.php?submit=7100338534&subm_code=1

U svakom slucaju hvala! :)

Testorao sam tvoj kod od pre (6/10). Mogu probati i poslednji.

evo linka: http://z-trening.com/submit.php?submit=7100338534&subm_code=1

2 3 7 7 9. res=3, ne 5

Rijesio sam :D.. Hvala..