Chúng tôi được cung cấp một mảng nhị phân có thể lưu trữ các chữ số 1 và 0 ở bất kỳ kích thước nhất định nào và một biến số nguyên, giả sử là cơ số. Nhiệm vụ là tính toán giá trị 1 tối thiểu có thể cung cấp sức mạnh cho các phần tử khác của mảng nhị phân để toàn bộ mảng trở nên mạnh mẽ. Một phần tử có thể cho phần tử lân cận của nó thêm sức mạnh hoặc bất kỳ phần tử nào khác trong khoảng cách nhỏ hơn cơ sở.
Hãy cho chúng tôi xem các tình huống đầu ra đầu vào khác nhau cho việc này -
Trong - int arr [] ={1, 1, 0, 1, 1, 0, 1}, int base =7
Hết - Số 1 tối thiểu để tăng sức mạnh để làm cho toàn bộ mảng trở nên mạnh mẽ là:1
Giải thích - chúng ta được cung cấp một mảng nhị phân có kích thước là 7 và giá trị của cơ số là 7, có nghĩa là chữ số 1 gặp đầu tiên có thể tăng sức mạnh cho toàn bộ mảng. Do đó, chữ số 1 tại arr [1] có thể tăng sức mạnh cho tất cả các phần tử khác của mảng.
Trong - int arr [] ={1, 1, 0, 1, 1, 0, 1}, int base =3
Hết - Số 1 tối thiểu để tăng sức mạnh để làm cho toàn bộ mảng trở nên mạnh mẽ là:2
Giải thích - chúng ta được cung cấp một mảng nhị phân có kích thước là 7 và giá trị của cơ số là 2 có nghĩa là chữ số 1 gặp đầu tiên có thể cho hai phần tử tiếp theo của một mảng. Do đó, chữ số 1 tại arr [2] có thể tăng sức mạnh cho hai phần tử tiếp theo của một mảng và một chữ số khác tại arr [5] có thể tăng sức mạnh cho hai phần tử tiếp theo của một mảng, điều này làm cho toàn bộ mảng trở nên mạnh mẽ.
Trong - int arr [] ={1, 1, 0, 1, 1, 0, 1}, int base =1
Hết - Không thể làm cho toàn bộ mảng trở nên mạnh mẽ
Giải thích - chúng ta được cung cấp một mảng nhị phân có kích thước là 7 và giá trị của cơ số là 1, có nghĩa là chữ số 1 gặp đầu tiên có thể tăng sức mạnh cho phần tử đơn tiếp theo của một mảng. Do đó, không thể làm cho toàn bộ mảng trở nên mạnh mẽ.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
-
Nhập một mảng nhị phân có kích thước nhất định bất kỳ và một biến số nguyên, giả sử là cơ số
-
Tính kích thước của một mảng và khai báo một biến, giả sử, val của kiểu số nguyên
-
Đặt val với lệnh gọi thành một hàm sẽ trả về số 1 tối thiểu được yêu cầu để tạo một mảng mạnh và nếu không thể, nó sẽ trả về -1. Điều này sẽ tiếp tục hiển thị thông báo lỗi.
-
Bên trong hàm Lend_Power (int arr [], int size, int base)
-
Khai báo một mảng các giá trị kiểu số nguyên với kích thước của một mảng nhị phân.
-
Khai báo một biến tạm thời dưới dạng tạm thời và đặt nó thành -1 và đếm và đặt nó thành 0.
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến hết kích thước của một mảng. Bên trong vòng lặp, Kiểm tra IF arr [i] bằng 1, sau đó đặt nhiệt độ là i và đặt arr_2 [i] là nhiệt độ
-
Bắt đầu vòng lặp FOR từ 0 cho đến khi kích thước của một mảng và đặt reset_base là i + base - 1 và reset_size là size - 1. Đặt một biến được đặt là arr_2 [min (reset_base, reset_size)].
-
Kiểm tra IF set =-1 OR set + base <=i rồi trả về -1
-
Đặt biến ‘i’ dưới dạng set + base.
-
-
Số lần trả lại.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
int Lend_Power(int arr[], int size, int base)
{
int arr_2[size];
int temp = -1;
int count = 0;
for(int i = 0; i < size; i++)
{
if(arr[i] == 1)
{
temp = i;
}
arr_2[i] = temp;
}
for(int i = 0; i < size;)
{
int reset_base = i + base - 1;
int reset_size = size - 1;
int set = arr_2[min(reset_base, reset_size)];
if(set == -1 || set + base <= i)
{
return -1;
}
i = set + base;
count++;
}
return count;
}
int main()
{
int arr[] = {1, 1, 0, 1, 1, 0, 1};
int base = 2;
int size = sizeof(arr) / sizeof(arr[0]);
int val = Lend_Power(arr, size, base);
if(val == -1)
{
cout<<"Impossible to make entire array powerful";
}
else
{
cout<<"Minimum 1s to lend power to make whole array powerful are: "<<val;
}
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra các lỗi sau
Minimum 1s to lend power to make whole array powerful are: 3