Problema Rufe – OJI 2019, Clasa a 11-a

Problema Rufe – OJI 2019, Clasa a 11-a

Rezumat

Se dă o matrice cu mm linii și nn coloane. Alex pune la uscat o șosetă și kk tricouri. Începe prin a pune la uscat șoseta în poziția (a,b)(a, b) Apoi, pune pe rând fiecare dintre cele kk tricouri într-o poziție liberă, cât mai îndepărtată de șosetă. Pentru măsurători se folosește distanța Manhattan, ceea ce înseamnă că distanța dintre două celule (x1,y1)(x_1, y_1) și (x2,y2)(x_2, y_2) se consideră x1x2+y1y2|x_1 - x_2| + |y_1 - y_2| Să se determine distanța dintre poziția șosetei și poziția unde a fost atârnat al kklea tricou.

Exemplu Rufe

În exemplul de mai sus, a=b=3a = b = 3 iar distanța dintre al patrulea tricou și șosetă este 44 Ordinea în care sunt așezate tricourile nu este unică. Însă ordinea distanțelor dintre tricouri și șosetă este unică: 5,5,4,45, 5, 4, 4

Soluție

Se observă ușor că putem căuta binar rezultatul: Cu cât distanța maximă dd dintre o celulă nevizitată și (a,b)(a, b) este mai mică, cu atât am vizitat mai multe celule. Noi vrem să găsim distanța dd maximă pentru care am vizitat strict mai puțin decât kk celule. Aceea va fi distanța la care va fi plasat al kklea tricou. Deci, dacă putem calcula eficient (preferabil în O(1)O(1) numărul de celule aflate la distanța maximă dd de șosetă, putem răspunde în timp logaritmic printr-un algoritm de genul:

int64_t lo = 0, hi = m + n;
while (hi - lo > 1) {
int64_t md = (lo + hi) / 2;
if (m * n - getArea(md) < k)
hi = md;
else
lo = md;
}
fout << hi << '\n';

Rămâne să vedem cum calculăm acel număr de celule. În primul rând, este bine de știut că mulțimea celulelor aflate la distanță Manhattan mai mică sau egală cu dd de o anumită celulă (a,b)(a, b) formează un romb de diagonală 2d+12d + 1 Iată rombul pentru d=6d = 6 și (a,b)=(2,3)(a, b) = (2, 3)

Distanța Manhattan

Problema este că rombul poate ieși din matrice, așa că trebuie să avem grijă cum eliminăm celulele din romb care se află în afara matricei. Cum fiecare dintre cele patru colțuri ale rombului poate ieși sau nu din matrice, avem de tratat șaisprezece cazuri. Iar la fiecare este destul de mult de scris și de gândit, motiv pentru care la OJI am rămas cu o sursă nefinalizată, care nici nu știu cum de a reușit să scoată patru puncte.

Aria rombului

Dacă privim problema dintr-o altă perspectivă, inspirată din principiul includerii și excluderii, vom realiza că putem trata intersecțiile independent, obținând opt cazuri mult mai simple. Algoritmul sună cam așa:

  • Inițializăm aria rombului ca și cum acesta nu ar ieși deloc din matrice.
  • Dacă vârful de sus al rombului iese din matrice, scădem aria triunghiului rezultat.
  • Dacă vârful de jos al rombului iese din matrice, scădem aria triunghiului rezultat.
  • Dacă vârful din stânga al rombului iese din matrice, scădem aria triunghiului rezultat.
  • Dacă vârful din dreapta al rombului iese din matrice, scădem aria triunghiului rezultat.
  • Dacă atât vârful de sus cât și cel din stânga ies din matrice, adunăm aria triunghiului rezultat.
  • Dacă atât vârful de sus cât și cel din dreapta ies din matrice, adunăm aria triunghiului rezultat.
  • Dacă atât vârful de jos cât și cel din stânga ies din matrice, adunăm aria triunghiului rezultat.
  • Dacă atât vârful de jos cât și cel din dreapta ies din matrice, adunăm aria triunghiului rezultat.

Să notăm cu f(n)f(n) suma primelor nn numere naturale, iar cu g(n)g(n) suma primelor numere naturale impare mai mici sau egale cu nn (care va fi mereu impar). Aceste funcții se calculează după formulele de mai jos, și ne vor ajuta să calculăm ariile triunghiurilor:

f(n)=1+2+3++n=n(n+1)2g(n)=1+3+5++n=f(n+1)2f(n+12)\begin{align*} f(n) &= 1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}\\ g(n) &= 1 + 3 + 5 + \cdots + n = f(n + 1) - 2f \left( \frac{n + 1}{2} \right) \end{align*}

Suma inițială se calculează ușor – împărțim rombul în două triunghiuri plus linia pe care se află centrul. Obținem 2g(2d1)+2d+12g(2d - 1) + 2d + 1

Colțul de sus al rombului iese din matrice dacă ad<1a - d \lt 1 În acest caz, aria triunghiului rezultat este g(2d+12a)g(2d + 1 - 2a) Analog pentru următoarele trei cazuri.

Aria 1

Atât colțul de sus cât și cel din stânga ies din matrice dacă da+bd \ge a + b În acest caz, aria triunghiului rezultat este f(d(a+b)+1)f(d - (a + b) + 1) Analog pentru următoarele trei cazuri.

Aria 2

Sursă C++

Problema Rufe
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rufe.in");
ofstream fout("rufe.out");
int64_t sumAll(int64_t n) {
return n * (n + 1) / 2;
}
int64_t sumOdd(int64_t n) {
return sumAll(n + 1) - 2 * sumAll((n + 1) / 2);
}
int main() {
int64_t m, n, a, b, k;
fin >> m >> n >> a >> b >> k;
auto getArea = [&](int64_t len) {
int64_t area = 2 * sumOdd(2 * len - 1) + 2 * len + 1;
if (a - len < 1) area -= sumOdd(2 * len + 1 - 2 * a);
if (a + len > m) area -= sumOdd(2 * len + 1 - 2 * (m - a + 1));
if (b - len < 1) area -= sumOdd(2 * len + 1 - 2 * b);
if (b + len > n) area -= sumOdd(2 * len + 1 - 2 * (n - b + 1));
if (len >= a + b) area += sumAll(len - (a + b) + 1);
if (len >= a + n - b + 1) area += sumAll(len - (a + n - b + 1) + 1);
if (len >= m - a + 1 + b) area += sumAll(len - (m - a + 1 + b) + 1);
if (len >= m - a + 1 + n - b + 1) area += sumAll(len - (m - a + 1 + n - b + 1) + 1);
return area;
};
int64_t lo = 0, hi = m + n;
while (hi - lo > 1) {
int64_t md = (lo + hi) / 2;
if (m * n - getArea(md) < k)
hi = md;
else
lo = md;
}
fout << hi << '\n';
return 0;
}

Dacă ai vreo nedumerire cu privire la problema Rufe, lasă un comentariu și te voi ajuta

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii