359 Vecini

[•silviug]

Aici puteţi discuta despre problema Vecini.

[•peanutz]

E O(n) solutia? Ma gandesc la ceva recursiv, dar nu stiu daca merge.. Nu da cineva o idee?

[•astronomy]

Vezi pentru N mic ce da si poate vezi un mod de constructie 

[•peanutz]

Ok, multumesc mult!

[•Dastas]

Eu nu inteleg cum sta treaba cu acele conditii pentru ca un etaj sa fie liber sau ocupat...

daca anul trecut etajul curent si etajul de dedesubt au fost ocupate, atunci etajul va fi liber anul acesta
...

Anul trecut etajul curent nu exista... nu? Daca in fiecare an se adauga un etaj, in anul X-1, etajul X nu exista. Vrea sa spuna cumva "ultimul etaj" sau ce?

[•astronomy]

Deasemenea ultimul etaj, fiind nou, este tot timpul ocupat. Restul etajelor insa sunt ocupate sau libere dupa regulile ...

[•Dastas]

N-am citit cu atentie  cred ca mi-am dat seama acuma, mersi..

[•gabor_oliviu1991]

imi dati un exemplu pt N mai mare sa vad cum de imi cade exeplu? merci anticipat

[•tm_radu]

Pentru testele :

Cod:

22
29
31
37
44

ar trebui sa-ti dea:

Cod:

1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

sper ca nu le-am incurcat

[•gabipurcaru]

fractalul lui Sierpinski!
de asta imi place informatica

[•harababurel]

iau 30p daca generez triunghiul incepand cu linia L (unde L = cea mai mare putere a lui 2 mai mica sau egala cu n -> linia contine doar cifre de 1).
o idee de 100p? (banuiesc ca se poate genera linia n in timp liniar)

[•ctlin04]

Te sfatui sa generezi manual pe caiet primele 15-20 de stari ale sirului, apoi incearca sa construesti sirul curent recursiv, eu am facut asa si am luat suta, apropo daca nu gresesc recursiv este chiar mai repede decit liniar deoarece adincimea recursie nu este comparabila cu n, bafta 

[•Detrol2k]

Imi da si mie cineva un hint? 
Iau primele 3 teste, iar la restul primesc TLE.
Eu am un vector pe care il reconstruiesc conform regulilor, de n-2 ori. Banuiesc ca exista o metoda de rezolvare in O(N)?

[•danalex97]

Daca privesti modul in care se genereaza liniile vei observa ca este vorba de un truinghi care se genereaza recursiv. Problema este asemanatoare cu "qtri" de pe campion , daca nu cumva este vorba de acelasi triunghi. Pentru a intelege modul de rezolvare al problemei ar trebui sa te uiti si la triunghiul lui Sierpinsky. Succes !  

LE : Scuza-ma daca fac vreo confuzie si daca ceva vi se pare in neregula cu ce am zis sa ma corectati.

[•Detrol2k]

Daca privesti modul in care se genereaza liniile vei observa ca este vorba de un truinghi care se genereaza recursiv. Problema este asemanatoare cu "qtri" de pe campion , daca nu cumva este vorba de acelasi triunghi. Pentru a intelege modul de rezolvare al problemei ar trebui sa te uiti si la triunghiul lui Sierpinsky. Succes !  

LE : Scuza-ma daca fac vreo confuzie si daca ceva vi se pare in neregula cu ce am zis sa ma corectati.

Am vazut ca daca afisez toate liniile apar acele triunghiuri din triunghiul lui Sierpinsky, dar nu-mi dau seama cum ma ajuta asta, chiar nu vad solutia 
Ceva mai concret nu se poate? 

[•repp4radu]

Daca esti pe o linie X incearca sa vezi care este cel mai mare i pentru care X > (2 ^ i) dupa care uite-te la linia X - (2 ^ i) si ar trebui sa observi ceva.

Spor!