Solutia la aceasta problema se foloseste de 'principiul includerii si excluderii':http://www.infoarena.ro/problema/pinex. Vom numara si aduna numarul de coduri care deschid seiful datorita apropierii de primul cod din cele $M$, de a al doilea cod, de al treilea cod.. apoi le vom scadea pe cele care sunt apropiate simultan de primul si al doilea, de primul si de al treilea, de al doilea si de al treilea.. etc.

Presupunand ca am fixat o configuratie de coduri si stim pentru fiecare i @nr[i] = numarul de celule care apartin intersectiei intervalelor corespunzatoare rotitei i@. Numarul de coduri 'apropiate' de fiecare din codurile din configuratie este data de @nr[1]*nr[2]*nr[3]*..nr[N]@.

Presupunand ca am fixat o configuratie de coduri si stim pe fiecare rotita i @nr[i] = numarul de celule care apartin intersectiei intervalelor corespunzatoare rotitei i@. Numarul de coduri 'apropiate' de fiecare din codurile din configuratie este data de @nr[1]*nr[2]*nr[3]*..nr[N]@.

Tot ce trebuie sa facem este construim intersectiile pentru fiecare configuratie, pe fiecare rotita, sa calculam rezultatul si sa il adunam sau scadem din solutie.
Lucrul care poate sa nu fie evident la prima vedere este ca desi intersectia a $X$ intervale pe o axa este un interval (sau multimea vida), pe un cerc, ea nu este interval. Ea poate consta si din $M$ intervale disjuncte. De exemplu:

Tot ce trebuie sa facem este construim intersectiile pentru fiecare configuratie, pe fiecare rotita, calculam rezultatul si il adunam sau scadem din solutie.
Lucrul care poate sa nu para evident la prima vedere este ca desi intersectia a $X$ intervale pe o axa este un interval (sau multimea vida), pe un cerc nu este interval. Ea poate consta si din $M$ intervale disjuncte. De exemplu:

----------- -----------
------- ---------------
---- ------------------

Cel mai sigur mod de a implementa functia de intersectie este de a ne inchipui ca suntem de fapt pe o axa necirculara. Astfel, intervalele (x,y) cu x > y le despartim in [x,k-1] si [0,y]. Acum, intersectia a X intervale disjuncte cu Y intervale disjuncte este reuniunea intersectiilor fiecare perechi de intervale (a,b) cu a din X si b din Y. Adica functia de intersectie o putem scrie asa:

Cel mai sigur mod de a implementa functia de intersectie este de a ne inchipui ca suntem de fapt pe o axa necirculara. Astfel, intervalele (x,y) cu x > y le despratim in [x,k-1] si [0,y]. Acum, intersectia a X intervale disjuncte cu Y intervale disjuncte este reuniunea intersectiilor fiecare perechi de intervale (a,b) cu a din X si b din Y. Adica functia de intersectie o putem scrie asa:

==code(cpp) |
void intersect (vector<pair<int,int> > X[], vector<pair<int,int> > Y[], vector<pair<int,int> > intersection[])

}
==

Noi vom intersecta mereu o multime de intervale cu un interval de forma (x-D,x+D) care se va transpune in 1 sau 2 intervale necirculare, adica Y[i].size() va fi mereu 1 sau 2. Complexitatea functiei de mai sus este astfel <tex>O(N*M)</tex>.

Noi vom intersecta mereu o multime de intervale cu un interval de forma (x-D,x+D) care se va transpune in 1 sau 2 intervale necirculare, adica Y[i].size() va fi mereu 1 sau 2. Complexitatea functie de mai sus este astfel <tex>O(N*M)</tex>.

Acum, modul in care vom parcurge intersectiile va dicta complexitatea finala. Daca pur si simplu iteram prin cele 2^M configuratii iar pentru fiecare configuratie construim intersectia intervalelor din configuratie de la 0, complexitatea va fi <tex>O(N*M^2^*2^M^)</tex>.