นับตัวเลขที่สามารถลดลงเป็นศูนย์หรือน้อยกว่าในเกมใน C++

กำหนดอาร์เรย์ของตัวเลขบวกและจำนวนเต็ม A และ B สองจำนวน ผู้เล่นสองคนกำลังเล่นเกมซึ่งพวกเขาจะลดตัวเลขในอาร์เรย์ ผู้เล่น 1 สามารถลดองค์ประกอบใด ๆ ของอาร์เรย์ด้วย A และผู้เล่น 2 สามารถเพิ่มองค์ประกอบใด ๆ ของอาร์เรย์โดย B เป้าหมายคือการหาจำนวนตัวเลขที่ผู้เล่น 1 สามารถลด 0 หรือน้อยกว่าได้ ผู้เล่นคนแรกทำให้ ย้ายครั้งแรก จำนวนที่ลดลงเหลือ 0 หรือน้อยกว่านั้นไม่สามารถนำมาพิจารณาโดยผู้เล่น 2 คน

ตัวอย่าง

อินพุต

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

ผลลัพธ์

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

คำอธิบาย

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.

อินพุต

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

ผลลัพธ์

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

คำอธิบาย

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.

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ ให้ตรวจสอบก่อนว่า A>B ถ้าใช่ ในการเคลื่อนที่ N A จะลดองค์ประกอบ N ทั้งหมดของ arr[] เป็น 0 หรือน้อยกว่า หาก A<=B เราจะตรวจสอบ

• ตัวเลขทั้งหมดที่ไม่มากกว่า A แม้ว่าผู้เล่น 2 จะเพิ่ม B ให้กับพวกเขา สมมุติว่าสิ่งนี้นับเป็น C1

• ตัวเลขทั้งหมดที่น้อยกว่า A และมากกว่า A หลังจากที่ผู้เล่น 2 เพิ่ม B ให้กับพวกเขา สมมุติว่าสิ่งนี้นับเป็น C2

จำนวนทั้งหมดจะเป็น C=C1+ (C2+1)/2 เช่นเดียวกับกรณีที่ 2 มีเพียงครึ่งหนึ่งเท่านั้นที่จะลดเหลือ 0 หรือน้อยกว่า เนื่องจากผู้เล่นทั้งสองเพิ่ม/ลดพร้อมกัน และผู้เล่นที่ 2 สามารถเพิ่มครึ่งหนึ่งให้มากกว่า A เท่านั้น ในระหว่างนี้ ผู้เล่นที่ 1 จะลดอีกครึ่งหนึ่งเป็น <=0

• ใช้อาร์เรย์จำนวนเต็มที่มีจำนวนบวก

• ใช้ตัวแปร A และ B สองตัว

• ฟังก์ชันreduce_zero(int arr[], int size, int A, int B) จะคืนค่าการนับจำนวนที่สามารถลดให้เหลือศูนย์หรือน้อยกว่าในเกม

• นับเริ่มต้นเป็น 0

• ใช้สองตัวแปร temp_1 และ temp_2 เป็นการนับชั่วคราว

• ถ้า A> B ให้คืนค่าความยาวของอาร์เรย์ที่มีขนาด

• ตอนนี้สำรวจอาร์เรย์โดยใช้ for loop สำหรับแต่ละ arr[i] ถ้าผลรวมขององค์ประกอบและ B

• สำหรับแต่ละองค์ประกอบ arr[i] <=A เพิ่ม temp_2.

• ตอนนี้หลังจากสิ้นสุดลูป for ให้ใช้ count=temp_1+ (temp_2+)/2 ตามสูตร

• ผลตอบแทนนับเป็นผลลัพธ์

#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