Lista de probleme 4

O tablă este formată din \(10^6\) rânduri și \(10^6\) coloane, numerotate de la \(1\) la \(10^6\). Pe tablă se află \(n\) ture. Tura \(i\) se află inițial în celula \((x_i,y_i)\).

Într-o mutare, o tură se poate deplasa în orice altă celulă de pe același rând sau aceeași coloană cu celula de pornire. Nu pot fi deplasate mai multe ture în aceeași mutare și în orice moment, mai multe ture se pot afla într-o singură celulă.

Turele vor să se întâlnească într-o celulă \((X,Y)\). Tu trebuie să alegi celula \((X,Y)\) în mod optim, astfel încât numărul total de mutări pe care trebuie să le facă turele pentru a se întâlni să fie minim.

Se consideră o curte de dimensiuni \(n \times m\). Curtea trebuie pavată cu dale identice de dimensiuni \(a \times b\), unde \(a\) și \(b\) sunt numere întregi. O dală costă \(\$1\), iar bugetul nostru este de \(\$B\). Câte perechi \((a,b)\) există, astfel încât putem pava curtea cu dale de dimensiuni \(a \times b\) și costul total al dalelor necesare nu depășește \(\$B\)?

Un șir format din numerele \(1,2,\dots,n\) scrise într-o anumită ordine se numește permutare. Se dă o permutare \(p\). Există două tipuri de operații pe care le putem face asupra permutării \(p\):

• Stânga: Alegem o valoare \(x\) (\(1 \le x \le n\)) și mutăm valoarea \(x\) la începutul permutării.
• Dreapta: Alegem o valoare \(x\) (\(1 \le x \le n\)) și mutăm valoarea \(x\) la finalul permutării.

Tu trebuie să determini numărul minim de operații necesare pentru a ordona crescător elementele permutării \(p\).

Se dă o matrice binară de dimensiuni \(n\times m\). Determinați numărul de cvadruplete \((r_1,r_2,c_1,c_2)\) care respectă următoarele condiții:

• \(1\le r_1 < r_2\le N\) și \(1\le c_1 < c_2\le M\).
• Celulele \((r_1,c_1)\) și \((r_1,c_2)\) conțin valoarea \(1\).
• Celulele \((r_2,c_1)\), \((r_2,c_1+1)\), …, \((r_2,c_2)\) conțin toate valoarea \(1\).