Trong một buổi tập bắn súng, có $N$ tấm bia được xếp thành một hàng dọc, đánh số từ $1$ tới $N$. Độ bền của các tấm bia được mô tả bởi dãy số $A$, tấm bia thứ $i$ có độ bền ban đầu là $A_i$. Một tấm bia được coi là bị phá hủy nếu độ bền của nó giảm xuống nhỏ hơn hoặc bằng $0$ (khi này coi độ bền của tấm bia là $0$).Xạ thủ được quyền chọn một loại đạn có sức công phá $X$ (với $X$ là số nguyên dương tùy ý) để sử dụng cho toàn bộ buổi tập. Mỗi lần bắn, xạ thủ bắn một viên đạn thẳng dọc theo hàng các tấm bia, viên đạn sẽ trúng tấm bia đầu tiên chưa bị phá hủy (tấm bia thứ $i$ có chỉ số nhỏ nhất và độ bền $A_i 0$). Do đạn có tính xuyên phá nên sẽ gây ảnh hưởng lên tấm bia thứ $i$ và các tấm bia thứ $j$ phía sau nó ($i \le j \le N$). Độ bền của tấm bia thứ $j$ bị giảm một lượng theo công thức: $max(0, X - (j - i)^2)$.InputDòng đầu chứa hai số nguyên dương $N, K$ ($N \le 2 \cdot 10^5; K \le 10^5$) tương ứng là số tấm bia và số lần bắn tối đa.Dòng tiếp theo chứa $N$ số nguyên dương mô tả dãy $A$ ($A_i \le 10^9; 1 \le i \le N$).OutputIn ra một số nguyên dương $X$ nhỏ nhất tìm được sao cho sau tối đa $K$ lần bắn, tất cả $N$ tấm bia đều bị phá hủy. trong mtt buổ ttập ấtn áng óó tếm baa đợc xếế thhn mtt ng dc đđđ nnn ccccc gggnr,bằng 0 (khi này coi độ bền của tấm bia là 0).,xa th đượ uênn chnnmmột lạiạạạ c ssáccng phhh tti nnnnnnnn tyy ggg oooo g ,ch s nhỏỏ nất và ộ bnn A; > D, oo ạạ có tínhxuynn hhá êê sggyyy hh hởng nn ttt -- ,Input,Dòng đầu chứa hai số nguyên dương N, KK(N 2 - 100; KK 110) tơnn nn l ố tấm bia v s lnn bnn tố đ..,• Dòng tiếp theo chứa N số nguyên dương mô tả dãy A (A; < 10*;1 < i < N).,Output,• In ra một số nguyên dương X nhỏ nhấtttìm được.,xample

Question

Trong một buổi tập bắn súng, có $N$ tấm bia được xếp thành một hàng dọc, đánh số từ $1$ tới $N$. Độ bền của các tấm bia được mô tả bởi dãy số $A$, tấm bia thứ $i$ có độ bền ban đầu là $A_i$. Một tấm bia được coi là bị phá hủy nếu độ bền của nó giảm xuống nhỏ hơn hoặc bằng $0$ (khi này coi độ bền của tấm bia là $0$).Xạ thủ được quyền chọn một loại đạn có sức công phá $X$ (với $X$ là số nguyên dương tùy ý) để sử dụng cho toàn bộ buổi tập. Mỗi lần bắn, xạ thủ bắn một viên đạn thẳng dọc theo hàng các tấm bia, viên đạn sẽ trúng tấm bia đầu tiên chưa bị phá hủy (tấm bia thứ $i$ có chỉ số nhỏ nhất và độ bền $A_i > 0$). Do đạn có tính xuyên phá nên sẽ gây ảnh hưởng lên tấm bia thứ $i$ và các tấm bia thứ $j$ phía sau nó ($i \le j \le N$). Độ bền của tấm bia thứ $j$ bị giảm một lượng theo công thức: $max(0, X - (j - i)^2)$.InputDòng đầu chứa hai số nguyên dương $N, K$ ($N \le 2 \cdot 10^5; K \le 10^5$) tương ứng là số tấm bia và số lần bắn tối đa.Dòng tiếp theo chứa $N$ số nguyên dương mô tả dãy $A$ ($A_i \le 10^9; 1 \le i \le N$).OutputIn ra một số nguyên dương $X$ nhỏ nhất tìm được sao cho sau tối đa $K$ lần bắn, tất cả $N$ tấm bia đều bị phá hủy. trong mtt buổ ttập ấtn  áng óó  tếm baa đợc xếế thhn  mtt  ng  dc đđđ                  nnn   ccccc                          gggnr,bằng 0 (khi này coi độ bền của tấm bia là 0).,xa th  đượ  uênn chnnmmột lạiạạạ c  ssáccng phhh   tti          nnnnnnnn  tyy        ggg   oooo                              g   ,ch  s nhỏỏ nất và  ộ bnn A; &gt; D, oo ạạ có  tínhxuynn hhá êê  sggyyy hh  hởng  nn ttt                                         --  ,Input,Dòng đầu chứa hai số nguyên dương N, KK(N   2 - 100; KK  110)  tơnn  nn  l  ố  tấm bia v  s  lnn bnn tố  đ..,• Dòng tiếp theo chứa N số nguyên dương mô tả dãy A (A; &lt; 10*;1 &lt; i &lt; N).,Output,• In ra một số nguyên dương X  nhỏ nhấtttìm được.,xample

cool boy · Accepted Answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = (ll)1e18;

int N;
ll K;
vector<ll> A;

bool check(ll X) {
vector<ll> da(N + 5), db(N + 5), dc(N + 5);

ll a = 0, b = 0, c = 0;
ll used = 0;

int R = sqrt((long double)(X - 1));

for (int i = 1; i <= N; i++) {
a += da[i];
b += db[i];
c += dc[i];

ll dmg = a * 1LL * i * i + b * i + c;

if (dmg < A[i]) {
ll need = A[i] - dmg;

ll t = (need + X - 1) / X;

used += t;

if (used > K) return false;

int l = i;
int r = min(N, i + R);

ll Acoef = -t;
ll Bcoef = 2LL * i * t;
ll Ccoef = t * (X - 1LL * i * i);

da[l] += Acoef;
da[r + 1] -= Acoef;

db[l] += Bcoef;
db[r + 1] -= Bcoef;

dc[l] += Ccoef;
dc[r + 1] -= Ccoef;

// cập nhật ngay vị trí i
a += Acoef;
b += Bcoef;
c += Ccoef;
}
}

return true;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> N >> K;

A.assign(N + 1, 0);

for (int i = 1; i <= N; i++)
cin >> A[i];

ll lo = 1, hi = 1e9;

while (lo < hi) {
ll mid = (lo + hi) / 2;

if (check(mid))
hi = mid;
else
lo = mid + 1;
}

cout << lo << ' ';
}

Timi · Answer

Để giải quyết bài toán này, chúng ta cần tìm giá trị nhỏ nhất của $ X $ sao cho sau tối đa $ K $ lần bắn, tất cả các tấm bia đều bị phá hủy. Bước 1: **Hiểu rõ cách bắn và tính toán độ bền còn lại của tấm bia**. Khi xạ thủ bắn vào tấm bia đầu tiên chưa bị phá hủy, sức công phá sẽ giảm dần theo công thức $ max(0, X - (j - i)^2) $. Điều này có nghĩa là, nếu viên đạn trúng tấm bia thứ $ i $, thì tấm bia thứ $ j $ (với $ j \geq i $) sẽ bị giảm độ bền theo khoảng cách từ $ i $. Bước 2: **Tính toán độ bền tối thiểu cho mỗi tấm bia**. Để đảm bảo tấm bia thứ $ i $ bị phá hủy, độ bền của nó $ A_i $ phải nhỏ hơn hoặc bằng tổng sức công phá mà nó nhận được từ $ K $ lần bắn. Bước 3: **Sử dụng thuật toán tìm kiếm nhị phân**. Chúng ta sẽ áp dụng tìm kiếm nhị phân trên giá trị của $ X $ để tìm ra giá trị nhỏ nhất có thể. Với mỗi giá trị $ X $ thử nghiệm, chúng ta sẽ kiểm tra xem có thể phá hủy tất cả các tấm bia trong tối đa $ K $ lần bắn hay không. Bước 4: **Kiểm tra khả năng phá hủy tất cả các tấm bia**. Để kiểm tra, chúng ta sẽ duyệt qua từng tấm bia và tính xem cần bao nhiêu lần bắn để phá hủy chúng. Nếu cần nhiều hơn $ K $ lần bắn cho một giá trị $ X $, thì giá trị đó là không khả thi. Dưới đây là một thuật toán chi tiết để thực hiện giải pháp: ```python def can_destroy_all(N, K, A, X): shots = 0 i = 0 while i < N: shots += 1 if shots > K: return False # Tính toán lượng công phá cho tấm bia i current_power = X j = i while j < N and current_power > 0: damage = max(0, current_power) A[j] -= damage if A[j] <= 0: j += 1 current_power -= 1 # giảm sức công phá theo khoảng cách return True def minimum_X(N, K, A): left, right = 1, max(A) result = right while left <= right: mid = (left + right) // 2 if can_destroy_all(N, K, A[:], mid): result = mid right = mid - 1 else: left = mid + 1 return result # Input N, K = map(int, input().split()) A = list(map(int, input().split())) # Output print(minimum_X(N, K, A)) ``` Chương trình trên sẽ tìm ra giá trị $ X $ nhỏ nhất cần thiết để phá hủy tất cả các tấm bia trong $ K $ lần bắn. Bằng cách sử dụng thuật toán tìm kiếm nhị phân, ta có thể tối ưu hóa việc tìm kiếm này và giảm thiểu số lần kiểm tra cần thiết.

Trong một buổi tập bắn súng, có $N$ tấm bia được xếp thành một hàng dọc, đánh số từ $1$ tới $N$. Độ bền của các tấm bia được mô tả bởi dãy số $A$, tấm bia thứ $i$ có độ bền ban đầu là $A_i$. Một tấm bi...