Pentru prima parte era nevoie de observatia ca, discriminarea pe o ulita este fie $0$, fie $1$. $0$ era in cazul in care ulita avea un numar par de case (alegeam din prima casa un barbat, apoi o femeie, etc.) si, repsectiv, $1$, cand pe ulita erau un numar impar de case.
Partea a doua necesita o analiza mai atenta. Prima solutie se bazeaza pe teoria grafurilor. Vom construi un graf bipartit, unde nodurie din partea stanga sunt reprezentate de dreptele paralele cu $OX$, iar nodurile din partea dreapta sunt reprezentate de dreptele paralele cu $OY$. Intre un nod din stanga si un nod din dreapta va exista muchie doar daca la intersectia celor doua drepte se afla o casa. Se porneste dintr-un nod cu grad impar, marcand alternativ muchiile (casele) cu $0$ sau $1$ si eliminandu-le. Raman, astfel, numai noduri cu grad par, care vor forma cicluri, dar care se pot rezolva folosind, din nou, algoritmul de mai sus.
Partea a doua necesita o analiza mai atenta.
Prima solutie se bazeaza pe teoria grafurilor. Vom construi un graf bipartit, unde nodurie din partea stanga sunt reprezentate de dreptele paralele cu $OX$, iar nodurile din partea dreapta sunt reprezentate de dreptele paralele cu $OY$. Intre un nod din stanga si un nod din dreapta va exista muchie doar daca la intersectia celor doua drepte se afla o casa. Se porneste dintr-un nod cu grad impar, marcand alternativ muchiile (casele) cu $0$ sau $1$ si eliminandu-le. Raman, astfel, numai noduri cu grad par, care vor forma cicluri, dar care se pot rezolva folosind, din nou, algoritmul de mai sus.
O alta rezolvare pentru partea a doua, este urmatoarea:
Se pleaca dintr-un punct nemarcat si se marcheaza cu $0$; se merge, pe dreapta, paralel cu $OX$, in urmatorul punct nemarcat, care se marcheaza cu $1$; se merge, apoi, pe dreapta, paralel cu $OY$, in urmatorul punct nemarcat si se marcheaza cu $0$, etc. Pentru o complexitate eficienta, punctele se pot tine ca niste liste, ale caror campuri retin urmatorul punct nemarcat pe $OX$, si urmatorul punct nemarcat pe $OY$. Daca unii utilizatori _InfoArena_, nu sunt obisnuiti cu implementarea listelor, pot tine niste vectori $NextOX{~i~}$ si $NextOY{~i~}$ in care sa retina indicii urmatoarelor puncte nemarcate pe $OX$, respectiv pe $OY$.
Se pleaca dintr-un punct nemarcat si se marcheaza cu $0$; se merge, pe dreapta, paralel cu $OX$, in urmatorul punct nemarcat, care se marcheaza cu $1$; se merge, apoi, pe dreapta, paralel cu $OY$, in urmatorul punct nemarcat si se marcheaza cu $0$, etc. Pentru o complexitate eficienta, punctele se pot tine ca niste liste, ale caror campuri retin urmatorul punct nemarcat pe $OX$ si, respectiv, urmatorul punct nemarcat pe $OY$. Daca unii utilizatori _InfoArena_, nu sunt obisnuiti cu implementarea listelor, pot tine niste vectori ($NextOX{~i~}$ si $NextOY{~i~}$) in care sa retina indicii urmatoarelor puncte nemarcate.
h2. 'Jetoane2':problema/jetoane2 (probelma medie)
