# PBinfo #4818 – Golf – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț Privit din satelit, Golful Biscayne (Florida) este format din n × m celule pătratice, fiecare celulă fiind umplută fie cu pământ, fie cu apă. Celulele umplute cu pământ sunt grupate în insule: două celule umplute cu pământ fac parte din aceeași insulă dacă și numai dacă se poate ajunge de la una la cealaltă prin deplasare (în sus, jos, stânga sau dreapta) doar pe pământ. Golful poate fi văzut, astfel, ca o matrice A cu n linii și m coloane (numerotate de la 1), unde A[i][j] = 1 dacă celula de pe linia i și coloana j este umplută cu pământ și A[i][j] = 0 dacă este umplută cu apă. Spunem că o insulă se află la stânga unei coloane c dacă și numai dacă toate celulele ce intră în alcătuirea insulei sunt strict la stânga coloanei c, adică sunt situate pe coloane strict mai mici decât c. Analog, stabilim dacă o insulă se află la dreapta unei coloane c, respectiv deasupra sau dedesubtul unei linii l. De exemplu, în desenul de mai sus, insulele A, B și C sunt la stânga coloanei 7, insula E este la dreapta coloanei 7, iar insula D nu este nici la stânga, nici la dreapta coloanei 7. De asemenea, insulele A și B sunt deasupra liniei 3, iar insulele C, D și E sunt dedesubtul liniei 4. Mai mult, insulele C, D și E nu sunt nici deasupra, nici dedesubtul liniei 5. Cerința Problema are trei cerințe, cerința de rezolvat fiind dată de T ∈ {1, 2, 3}. T = 1. Determinați numărul de celule din golf ce sunt umplute cu pământ. T = 2. Determinați numărul de insule din golf ce conțin un număr maxim de celule. Dacă nu există nicio insulă, atunci valoarea acestui număr este 0. T = 3. Se dau, în ordine, Q interogări, fiecare fiind descrisă printr-o literă și un număr natural nenul p. Determinați valoarea produsului a × b, știind că: Dacă litera este C, atunci a reprezintă numărul de celule din toate insulele ce se află la stânga coloanei p (1 ≤ p ≤ m) și b numărul de celule din toate insulele ce se află la dreapta coloanei p. Dacă litera este L, atunci a reprezintă numărul de celule din toate insulele ce se află deasupra liniei p (1 ≤ p ≤ n) și b numărul de celule din toate insulele ce se află dedesubtul liniei p. Date de intrare Fișierul de intrare golf.in conține pe prima linie, separate prin câte un spațiu, numerele T n m, unde T reprezintă numărul cerinței care trebuie rezolvată, iar N și m au semnificația din enunț. Pe următoarele n linii se află valorile matricei A; în cadrul unei linii a matricei, valorile nu sunt separate între ele prin spații. Dacă T = 3, următoarea linie conține numărul natural nenul Q, iar pe fiecare dintre următoarele Q linii se află câte o literă și un număr natural nenul, separate prin câte un spațiu, reprezentând descrierile celor Q interogări. Date de ieșire Conținutul fișierului de ieșire golf.out depinde de T . Dacă T ∈ {1, 2}, fișierul conține doar numărul determinat pentru cerința T. Dacă T = 3, fișierul conține Q numere, fiecare pe câte o linie, reprezentând, în ordine, valorile produselor determinate pentru interogările date. Restricții și precizări 1 ≤ n,m ≤ 1000 A[i][j] ∈ {0, 1}, pentru fiecare (i, j): 1 ≤ i ≤ n și 1 ≤ j ≤ m. Dacă T = 3, atunci 1 ≤ Q ≤ 600 000. O insulă poate fi formată dintr-o singură celulă. pentru 27 de puncte, T =1 pentru 7 puncte, T = 2 și există o singură insulă în golf pentru 15 puncte, T =2 pentru 14 puncte T = 3 și n, m, Q ≤ 200 pentru 9 puncte, T = 3 și Q ≤ 2 000 pentru 28 de puncte T = 3 datorită dimensiunilor mari ale fișierelor, nu au fost adăugate toate testele folosite în concurs Exemplul 1 golf.in 1 7 11 11110000000 01101100000 00000000000 00000000000 11100111011 01000100001 01000000000 golf.out 20 Explicație Exemplul corespunde cu desenul de mai sus. Golful Biscayne are 20 de celule umplute cu pământ. Exemplul 2 golf.in 2 7 11 11110000000 01101100000 00000000000 00000000000 11100111011 01000100001 01000000000 golf.out 20 Explicație Insula A conține 6 celule, iar toate celelalte insule conțin cel mult 5 celule, așadar răspunsul este 1. Exemplul 3 golf.in 3 7 11 11110000000 01101100000 00000000000 00000000000 11100111011 01000100001 01000000000 2 C 7 L 4 golf.out 39 96 Explicație Pentru prima interogare, insulele A, B și C, cu 13 celule (în total), sunt la stânga coloanei 7, iar insula E, cu 3 celule, este la dreapta coloanei 7. Deci, produsul cerut este 13 × 3 = 39. Pentru a doua interogare, insulele A și B, cu 8 celule, sunt deasupra liniei 4, iar insulele C, D și E, cu 12 celule, sunt dedesubtul liniei. Deci, produsul cerut este 8 × 12 = 96. ## Cod sursă C++ ```cpp /* Autor: Andrei Onut (Yale University) Problema: "Golf" (OJI 2025, clasa a X-a) */ #include #include #include #include #include int my_min(const int a, const int b) { return ((a < b) ? a : b); } int my_max(const int a, const int b) { return ((a > b) ? a : b); } struct island { int first_line, first_column; int last_line, last_column; int size; island(const int x, const int y) : first_line(x), first_column(y), last_line(x), last_column(y), size(1) {} void update(const int x, const int y) { first_line = my_min(first_line, x), first_column = my_min(first_column, y); last_line = my_max(last_line, x), last_column = my_max(last_column, y); ++size; return; } }; template std ::string T_to_string(T x) { if (x == (T)0) return "0"; std ::string answer; while (x) answer += ((char)((x % (T)10) + '0')), x /= (T)10; reverse(answer.begin(), answer.end()); return answer; } class golf_solver { const std ::string problem_name = "golf", dot = ".", input_format = "in", output_format = "out"; const int dx[4] = {(-1), 0, (+1), 0}, dy[4] = {0, (+1), 0, (-1)}; int T, n, m, q; std ::vector A; std ::vector> queries; std ::vector answer; std ::vector islands_arr; int answer_1, answer_2; island find_island(const int i, const int j, std ::vector> &used) { island answer(i, j); std ::queue> Q; used[i][j] = true, Q.push({i, j}); while (!Q.empty()) { for (int dir = 0; dir < 4; ++dir) { int x(Q.front().first + dx[dir]), y(Q.front().second + dy[dir]); if ((x < 0) || (x >= n) || (y < 0) || (y >= m)) continue; if (A[x][y] == '0') continue; if (used[x][y] == true) continue; used[x][y] = true, Q.push({x, y}); answer.update(x, y); } Q.pop(); } return answer; } void solve_T_1() { for (const island &it : islands_arr) answer_1 += it.size; return; } void solve_T_2() { if (islands_arr.empty()) return; int max_size(-1); for (const island &it : islands_arr) if (it.size > max_size) max_size = it.size, answer_2 = 1; else if (it.size == max_size) ++answer_2; return; } std ::vector, int>> extract_segments(const int axis) { std ::vector, int>> answer; for (const island &it : islands_arr) if (axis == 0) answer.push_back( {{it.first_column, it.last_column}, it.size}); else answer.push_back( {{it.first_line, it.last_line}, it.size}); return answer; } std ::pair, std ::vector> get_sums(const int axis, const int elements) { std ::vector prefix(elements, 0), suffix(elements, 0); std ::vector, int>> segments = extract_segments(axis); std ::vector end_num(elements, 0), start_num(elements, 0); for (const std ::pair, int> &it : segments) end_num[it.first.second] += it.second, start_num[it.first.first] += it.second; prefix[0] = end_num[0], suffix[(elements - 1)] = start_num[(elements - 1)]; for (int i = 1; i < elements; ++i) prefix[i] = (prefix[(i - 1)] + end_num[i]), suffix[(elements - 1 - i)] = (suffix[(elements - i)] + start_num[(elements - 1 - i)]); return {prefix, suffix}; } long long evaluate(const int q_idx, const int elements, const std ::pair, std ::vector> &V) { if ((q_idx == 1) || (q_idx == elements)) return 0LL; return (1LL * V.first[(q_idx - 2)] * V.second[q_idx]); } void solve_T_3() { std ::pair, std ::vector> columns = get_sums(0, m), lines = get_sums(1, n); int i = 0; for (const std ::pair &it : queries) answer[(i++)] = ((it.first == 'C') ? evaluate(it.second, m, columns) : evaluate(it.second, n, lines)); return; } public: golf_solver() : T(0), n(0), m(0), q(0), answer_1(0), answer_2(0) {} void read() { std ::ifstream f(problem_name + dot + input_format); f >> T >> n >> m; A = std ::vector(n, std ::string(m, ' ')); for (int i(0); i < n; ++i) f >> A[i]; if (T == 3) { f >> q; queries = std ::vector>(q), answer = std ::vector(q); for (int i(0); i < q; ++i) f >> queries[i].first >> queries[i].second; } f.close(); return; } void pre_compute() { std ::vector> used( n, std ::vector(m, false)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if ((A[i][j] == '1') && (used[i][j] == false)) islands_arr.push_back(find_island(i, j, used)); return; } void solve() { ((T == 1) ? solve_T_1() : ((T == 2) ? solve_T_2() : solve_T_3())); return; } void print() { std ::ofstream g(problem_name + dot + output_format); std ::vector output_lines( ((T <= 2) ? 1 : q)); if (T == 1) output_lines[0] = T_to_string(answer_1); else if (T == 2) output_lines[0] = T_to_string(answer_2); else for (int i = 0; i < q; ++i) output_lines[i] = T_to_string(answer[i]); for (const std ::string &line : output_lines) g << line << '\n'; g.close(); return; } }; int main() { golf_solver S; S.read(); S.pre_compute(); S.solve(); S.print(); return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4818) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4818/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4818/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)