C++ में खेल में शून्य या उससे कम होने वाली संख्याओं की गिनती

समस्या विवरण

धनात्मक संख्याओं की एक सरणी और दो पूर्णांक A और B दिए गए हैं। दो खिलाड़ी एक खेल खेल रहे हैं जिसमें वे सरणी में संख्याओं को कम करेंगे। खिलाड़ी 1 सरणी के किसी भी तत्व को A से कम कर सकता है और खिलाड़ी 2 सरणी के किसी भी तत्व को B से बढ़ा सकता है। लक्ष्य उन संख्याओं की संख्या ज्ञात करना है जिन्हें खिलाड़ी 1 द्वारा 0 या उससे कम किया जा सकता है। पहला खिलाड़ी पहली चाल चलता है। एक बार 0 या उससे कम होने वाली संख्या पर खिलाड़ी 2 विचार नहीं कर सकता।

उदाहरण

इनपुट

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

आउटपुट

शून्य या कम होने वाली संख्याओं की गिनती: 1

व्याख्या

खिलाड़ी 1 द्वारा कम की जा सकने वाली एकमात्र संख्या 1 है क्योंकि पहली चाल में यह -1 हो जाएगी। बाकी सभी खिलाड़ी 2 द्वारा मान बढ़ाने के बाद A से अधिक हो जाएंगे।

इनपुट

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

आउटपुट

शून्य या कम होने वाली संख्याओं की गिनती: 2

व्याख्या

पहली चाल में खिलाड़ी 1, 4 को 0 करता है। arr[] = [1, 0, 5, 2]। खिलाड़ी 2, 1 को 4 बढ़ाता है। arr[] = [5, 0, 5, 2]। खिलाड़ी 1, 2 को -2 करता है। Arr[] = [5, 0, 5, -2]। अब से सभी संख्याएं A से अधिक हैं इसलिए खिलाड़ी 1 द्वारा 0 या कम नहीं की जा सकतीं क्योंकि खिलाड़ी 2 भी उन्हें साथ-साथ बढ़ा रहा है।

दृष्टिकोण

इस दृष्टिकोण में पहले जांचें कि A > B है या नहीं। यदि हां तो N चालों में A, arr[] के सभी N तत्वों को 0 या कम कर देगा। यदि A <= B तो हम जांचेंगे:

वे सभी संख्याएं जो खिलाड़ी 2 द्वारा B जोड़ने के बाद भी A से अधिक नहीं होतीं। मान लें यह गिनती C1 है।
वे सभी संख्याएं जो A से कम हैं लेकिन खिलाड़ी 2 द्वारा B जोड़ने के बाद A से अधिक हो जाती हैं। मान लें यह गिनती 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 लें।
दो चर temp_1 और temp_2 अस्थायी गिनती के रूप में लें।
यदि A > B तो सरणी की लंबाई size लौटाएं।
अब for लूप का उपयोग करके सरणी को पार करें, प्रत्येक arr[i] के लिए यदि तत्व और B का योग A से कम है तो temp_1 बढ़ाएं।
प्रत्येक तत्व arr[i] <= A के लिए temp_2 बढ़ाएं।
for लूप के अंत में, सूत्र के अनुसार count = temp_1 + (temp_2+1)/2 लें।
परिणाम के रूप में गिनती लौटाएं।

C++ कोड उदाहरण

#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 << "शून्य या कम होने वाली संख्याओं की गिनती: " << reduced_zero(arr, size, A, B);
    return 0;
}

आउटपुट

शून्य या कम होने वाली संख्याओं की गिनती: 7