Đếm số có thể giảm xuống 0 hoặc ít hơn trong gamein 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 xuống 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 các số có thể được giảm xuống 0 hoặc ít hơn bởi người chơi 1. Người chơi đầu tiên thực hiện bước đi đầu tiên. Người chơi 2 không thể xem xét con số sau khi giảm xuống 0 hoặc ít hơn.

Ví dụ

Đầu vào

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

Đầu ra

Count of numbers that can be reduced to zero or less in a game are: 1

Giải thích

The only number that can be reduced by player 1 is 1 as on first move it
will be reduced to −1. Rest all will become greater than A after player 2 increases their value.

Đầu vào

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

Đầu ra

Count of numbers that can be reduced to zero or less in a game are: 2

Giải thích

On first move player 1 reduces 4 to 0. arr[]= [ 1, 0, 5, 2 ]
Player 2 will increase 1 to 4. arr[]= [ 5, 0, 5, 2 ]
Player 1 will decrease 2 to −2. Arr[] = [ 5, 0, 5, −2 ].
From now onwards all numbers are greater than A so cannot be reduced by player 1 to 0 or less as player 2 is also increasing them simultaneously.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, đầu tiên hãy kiểm tra xem A> B. Nếu có thì trong N lần di chuyển, 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ố không lớn hơn A kể cả sau khi người chơi 2 thêm B vào chúng. Giả sử điều này được tính là C1.

• Tất cả các số nhỏ hơn A và lớn hơn A sau khi người chơi 2 thêm B vào chúng. Giả sử điều này được tính là C2.

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

• Lấy một mảng số nguyên chứa các số dương.

• Lấy hai biến A và B.

• Hàm Reduce_zero (int arr [], int size, int A, int B) sẽ trả về tổng số đếm các số có thể giảm xuống 0 hoặc ít hơn trong một trò chơi

• Lấy số lượng ban đầu là 0.

• Lấy hai biến temp_1 và temp_2 làm số đếm tạm thời.

• Nếu A> B thì trả về độ dài của mảng là kích thước.

• Bây giờ duyệt mảng bằng cách sử dụng vòng lặp for, với mỗi arr [i] nếu tổng của phần tử và B

• Đố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. Như đã cho trong công thức.

• Kết quả là số lượt trả lại.

#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<<"Count of numbers that can be reduced to zero or less in a game are:  "<<reduced_zero(arr, size, A, B);
   return 0;
}

Count of numbers that can be reduced to zero or less in a game are: 7