Đếm số có thể giảm về 0 hoặc âm trong trò chơi trong C++

Cho một mảng các số dương và hai số nguyên A và B. Hai người chơi đang chơi một trò chơi trong đó họ sẽ giảm các số trong mảng. Người chơi 1 có thể giảm bất kỳ phần tử nào của mảng đi A và người chơi 2 có thể tăng bất kỳ phần tử nào của mảng lên B. Mục tiêu là tìm số lượng số có thể giảm xuống 0 hoặc nhỏ hơn bởi người chơi 1. Người chơi 1 đi nước đi đầu tiên. Số một khi giảm xuống 0 hoặc nhỏ hơn thì không thể được xem xét bởi người chơi 2.

Ví dụ

Đầu vào

arr[] = { 1,4,5,2 } A=2, B=3

Đầu ra

Số lượng số có thể giảm về 0 hoặc âm trong trò chơi là: 1

Giải thích

Chỉ số 1 có thể bị giảm bởi người chơi 1 vì ở nước đi đầu tiên nó sẽ giảm thành -1. Tất cả các số còn lại sẽ lớn hơn A sau khi người chơi 2 tăng giá trị của chúng.

Đầu vào

arr[] = { 1,4,5,2 } A=4, B=4

Đầu ra

Số lượng số có thể giảm về 0 hoặc âm trong trò chơi là: 2

Giải thích

Nước đi đầu tiên người chơi 1 giảm 4 thành 0. arr[]=[1,0,5,2]. Người chơi 2 sẽ tăng 1 thành 4. arr[]=[5,0,5,2]. Người chơi 1 sẽ giảm 2 thành -2. Arr[]=[5,0,5,-2]. Từ bây giờ tất cả các số đều lớn hơn A nên không thể bị giảm bởi người chơi 1 xuống 0 hoặc âm vì người chơi 2 cũng đang tăng chúng đồng thời.

Phương pháp sử dụng

Trong phương pháp này, đầu tiên kiểm tra nếu A > B. Nếu đúng thì sau N nước đi, A sẽ giảm tất cả N phần tử của arr[] xuống 0 hoặc nhỏ hơn. Nếu A <= B thì chúng ta sẽ kiểm tra:

Tất cả các số mà không trở nên lớn hơn A ngay cả sau khi người chơi 2 cộng B vào chúng. Gọi số lượng này là C1.
Tất cả các số nhỏ hơn A và trở nên lớn hơn A sau khi người chơi 2 cộng B vào chúng. Gọi số lượng này là C2.

Tổng số lượng sẽ là C = C1 + (C2+1)/2. Vì trong trường hợp 2, chỉ một nửa trong số đó sẽ giảm xuống 0 hoặc nhỏ hơn vì cả hai người chơi cùng tăng/giảm đồng thời. Và người chơi 2 chỉ có thể tăng một nửa chúng lên lớn hơn A. Trong khi đó, người chơi 1 sẽ giảm nửa kia xuống <=0.

Nhận mảng nguyên chứa các số dương.
Nhận hai biến A và B.
Hàm reduced_zero(int arr[], int size, int A, int B) sẽ trả về số lượng số có thể giảm về 0 hoặc nhỏ hơn trong trò chơi.
Khởi tạo biến đếm ban đầu là 0.
Lấy hai biến temp_1 và temp_2 làm biến đếm tạm.
Nếu A > B thì trả về độ dài mảng là size.
Bây giờ duyệt mảng bằng vòng lặp for, cho mỗi arr[i] nếu tổng phần tử và B < A thì tăng temp_1.
Đối với mỗi phần tử arr[i] <= A, tăng temp_2.
Bây giờ sau khi kết thúc vòng lặp for, lấy count = temp_1 + (temp_2+1)/2. Theo công thức cho trước.
Trả về biến đếm làm kết quả.

Ví dụ mã

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

int reduced_zero(int arr[], int size, int A, int B) {
    int count = 0;
    int temp_1 = 0, temp_2 = 0;
    
    if (A > B) {
        return size;
    }
    
    for(int i = 0; i < size; i++) {
        if (A >= arr[i] + B) {
            temp_1++;
        } else if (A >= arr[i]) {
            temp_2++;
        }
    }
    
    int temp = (temp_2 + 1) / 2;
    count = temp + temp_1;
    return count;
}

int main() {
    int arr[] = { 3, 3, 1, 2, 4, 7, 1 };
    int A = 4, B = 1;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Số lượng số có thể giảm về 0 hoặc âm trong trò chơi là: " << reduced_zero(arr, size, A, B);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số lượng số có thể giảm về 0 hoặc âm trong trò chơi là: 7