นับตัวเลขที่ลดเหลือศูนย์หรือติดลบได้ในเกมด้วย C++

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

ตัวอย่าง

Input

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

Output

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

Explanation

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.

Input

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

Output

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

Explanation

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 สองตัว
• ฟังก์ชัน reduced_zero(int arr[], int size, int A, int B) คืนค่าจำนวนที่ลดเหลือ 0 หรือติดลบได้
• กำหนดจำนวนนับเริ่มต้นเป็น 0
• ตัวแปรชั่วคราว temp_1 และ temp_2 สำหรับนับชั่วคราว
• ถ้า A > B คืนค่า size (ความยาวอาร์เรย์)
• วนลูปอาร์เรย์ สำหรับแต่ละ arr[i] ถ้า arr[i] + B < A เพิ่ม temp_1
• สำหรับแต่ละ arr[i] <= A เพิ่ม temp_2
• หลังลูปจบ count = temp_1 + (temp_2 + 1)/2 ตามสูตร
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

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