Autor: Ștefan-Cosmin Dăscălescu
Soluția problemei pic (OJI 2016, clasa a IX-a)#
Cunoștințe necesare
Link problemă
Această problemă poate fi accesată aici.
Pentru a rezolva prima cerință, tot ce trebuie să facem este să parcurgem fiecare linie și să calculăm suma capacităților.
Pentru cea de-a doua cerință, o primă soluție la care ne putem gândi este să simulăm procesul de turnare al lichidului și să aflăm primul moment de timp în care se termină de turnat lichidul. Din păcate, această soluție este prea înceată, deoarece ne poate lua foarte mult timp să ajungem la acest obiectiv.
Totuși, putem observa faptul că pe măsură ce turnăm tot mai mult lichid, vom avea tot mai mult progres cu umplerea paharelor, ceea ce impune folosirea unei alte metode de a gândi turnarea apei în pahare.
Observație
Acum, ne putem gândi invers: Oare dacă turnăm toată apa la început?
Dacă turnăm toată apa la început, putem verifica în \(\mathcal{O}(n^2)\) dacă această cantitate de apă este îndeajuns pentru a realiza obiectivul propus. Astfel, ne putem gândi acum mai departe la o idee pe baza unei căutări binare pe răspuns, deoarece acum putem simula eficient dacă putem obține un răspuns, iar în caz afirmativ, vom putea încerca un răspuns mai mic.
Tot ce ne mai rămâne să facem este să aproximăm valoarea maximă a răspunsului, fapt ce se poate afla gândindu-ne la frecvența cu care ajung valorile mai mici să fie umplute. Pentru o valoare de pe linia \(i\), va fi atinsă aproximativ o dată la \(2^{i-1}\) pași, iar deoarece limita maximă este \(25\) pentru cantitatea unui pahar, înseamnă că vom avea nevoie de aproximativ \(2^{49} \cdot 25\) picături pentru a ajunge la răspunsul final. Astfel, putem pune un capăt dreapta egal cu \(2^{60}\) fără probleme, lucru făcut în soluția de mai jos.
Complexitatea va fi \(\mathcal{O}(60 \cdot n^2)\).
Mai jos puteți găsi o soluție neoficială care ia punctajul maxim.
#include <fstream>
#include <vector>
bool check(long long T, const std::vector<int>& C, int N, int M) {
std::vector<long long> inflow(M + 1, 0);
inflow[1] = T;
for (int l = 1; l <= N; ++l) {
int start = (l - 1) * l / 2 + 1;
int end = l * (l + 1) / 2;
for (int j = start; j <= end; ++j) {
if (j > M) {
break;
}
long long c = C[j - 1];
long long oj = std::max(0LL, inflow[j] - c);
if (l < N) {
int left = j + l;
int right = j + l + 1;
if (left <= M) {
inflow[left] += (oj + 1) / 2;
}
if (right <= M) {
inflow[right] += oj / 2;
}
}
}
}
for (int j = 1; j <= M; ++j) {
if (inflow[j] < C[j - 1]) {
return false;
}
}
return true;
}
int main() {
std::ifstream cin("pic.in");
std::ofstream cout("pic.out");
int V, N;
cin >> V >> N;
int M = N * (N + 1) / 2;
std::vector<int> C(M);
for (int i = 0; i < M; ++i) {
cin >> C[i];
}
if (V == 1) {
int max_sum = -1, best_level = 0;
for (int l = 1; l <= N; ++l) {
int start = (l - 1) * l / 2;
int sum = 0;
for (int i = start; i < start + l; ++i) {
sum += C[i];
}
if (sum > max_sum || (sum == max_sum && l < best_level)) {
max_sum = sum;
best_level = l;
}
}
cout << best_level << "\n";
}
else {
long long sum_C = 0;
for (int i = 0; i < C.size(); i++) {
sum_C += C[i];
}
long long low = sum_C, high = (1LL << 60), ans_T = high;
while (low <= high) {
long long mid = (low + high) / 2;
if (check(mid, C, N, M)) {
ans_T = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << ans_T << " " << ans_T - sum_C << "\n";
}
return 0;
}