h2. 'Meneaito':problema/meneaito
Se observa ca pentru ca un timp sa reprezinte o solutie, atunci pentru fiecare coloana i, 1 < i < N, dansatorul de pe coloana i trebuie sa nu fie pe pozitia i. Astfel, putem marca timpii in care pe o anumita coloana i, pozitia i este ocupata. Mentionam ca nu ne intereseaza cazul in care i < A[i] sau i > B[i]. Pentru celelalte cazuri(unde A[i] <= i <= B[i]), consideram 2 posibilitati:

1) Dansatorul se afla pe pozitia i si se indreapta in jos;
2) Dansatorul se afla pe pozitia i si se indreapta in sus;

1) Dansatorul se afla pe pozitia i si se indreapta in jos
2) Dansatorul se afla pe pozitia i si se indreapta in sus

Observam ca pentru fiecare dintre aceste cazuri avem un timp(notat X1 pentru primul caz si X2 pentru al doilea caz) cand evenimentul se produce prima data. Deasemenea observam ca evenimentul(aparitia unui timp care nu poate fi solutie) se produce la un interval dat de timp, notat in continuare Y.
Se vede usor faptul ca:

X1 = i - A[i];
X2 = 2 * (B[i] - i) - (A[i] - i);
Y = 2 * (B[i] - A[i]);

X1 = i - A[i]
X2 = 2 * (B[i] - i) - (A[i] - i)
Y = 2 * (B[i] - A[i])

Vor aparea astfel ecuatii de forma: T = X1 + K * Y si T = X2 + K * Y, unde T reprezinta un timp ce nu poate constitui o solutie, iar K este un numar natural.
Vom marca aceste ecuatii cu ajutorul unui map care ne va ajuta sa nu avem ecuatii redundante. Astfel pentru fiecare Y, vom tine maxim Y ecuatii.

La fiecare pas la care descoperim o ecuatie noua, eliminam timpii care nu pot constitui o solutie utilizand un algoritm asemanator ciurului lui Eratostene. Pentru a gasi solutia parcurgem toti timpii de la 0 la 200000 si il gasim pe cel mai mic care a ramas nemarcat in urma ciurului.

La fiecare pas la care descoperim o ecuatie noua, eliminam timpii care nu pot constitui o solutie utilizand un algoritm asemanator ciurului lui Eratostene. Pentru a gasi solutia parcurgem toti timpii de la 0 la 200000 si il gasim pe cel mai mic care a ramas nemarcat in urma ciurului