Cho mảng nhị phân (0/1) và số base. Một '1' có thể "cho sức mạnh" các phần tử trong khoảng cách < base. Tìm số '1' tối thiểu cần kích hoạt để toàn mảng mạnh. Nếu không thể → "Impossible".
Ví dụ
Đầu vào: arr[] = {1,1,0,1,1,0,1}, base = 7
Đầu ra: 1 (1 đầu tiên phủ cả mảng).
Đầu vào: arr[] = {1,1,0,1,1,0,1}, base = 3
Đầu ra: 2 (1 tại chỉ số 2 phủ 2 phần tử tiếp, 1 tại chỉ số 5 phủ tiếp).
Đầu vào: arr[] = {1,1,0,1,1,0,1}, base = 1
Đầu ra: Impossible (base=1 chỉ phủ chính nó, không lan truyền).
Phương pháp: Greedy + Mảng vị trí 1 gần nhất bên trái
- Tạo mảng
leftOne[i]= chỉ số '1' gần nhất ≤ i (hoặc -1). - Duyệt i từ 0: tìm '1' xa nhất có thể phủ i (tại
min(i+base-1, n-1)). Nếu không có hoặc không phủ được i → Impossible. - Nhảy
i = pos + base, đếm++.
Ví dụ mã C++
#include <bits/stdc++.h>
using namespace std;
int minOnesToPower(int arr[], int n, int base) {
vector leftOne(n, -1);
int last = -1;
for (int i=0; i
Đầu ra chương trình
Minimum 1s to lend power to make whole array powerful are: 3