Contar los números que se pueden reducir a cero o menos en un juego

Dados dos enteros X e Y y un arreglo de N enteros. El jugador A puede disminuir cualquier elemento de la array en X y el jugador B puede aumentar cualquier elemento de la array en Y . La tarea es contar el número de elementos que A puede reducir a 0 o menos . Ambos juegan de manera óptima durante un tiempo infinito con A haciendo el primer movimiento. 
Nota: Una vez que un número se reduce a cero o menos, no se puede aumentar. 
Ejemplos: 
 

Entrada: a[] = {1, 2, 4, 2, 3}, X = 3, Y = 3 
Salida: 2 
A reduce 2 a -1 
B aumenta 1 a 4 
A reduce 2 a -1 
B aumenta 4 a 7 y el juego continúa.
Entrada: a[] = {1, 2, 4, 2, 3}, X = 3, Y = 2 
Salida: 5 
 

Enfoque: dado que el juego dura un tiempo infinito, imprimimos N si X > Y . Ahora necesitamos resolver para X ≤ Y . Los números pueden ser de dos tipos: 
 

1. Los que no superan X al sumar Y dicen contar1 que puede ser reducido a ≤ 0 por A .
2. Los que son < X y superan X al sumar Y dicen contar2 solo la mitad de los cuales A puede reducir a ≤ 0 ya que están jugando de forma óptima y B intentará aumentar cualquiera de esos números para que sea > X en cada uno de sus turnos.

Entonces, la respuesta será cuenta1 + ((cuenta2 + 1) / 2) .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of numbers
int countNumbers(int a[], int n, int x, int y)
{
 
    // Base case
    if (y < x)
        return n;
 
    // Count the numbers
    int count1 = 0, count2 = 0;
    for (int i = 0; i < n; i++) {
 
        if (a[i] + y <= x)
            count1++;
        else if (a[i] <= x)
            count2++;
    }
 
    int number = (count2 + 1) / 2 + count1;
 
    return number;
}
 
// Driver Code
int main()
{
    int a[] = { 1, 2, 4, 2, 3 };
    int n = sizeof(a) / sizeof(a[0]);
 
    int x = 3, y = 3;
    cout << countNumbers(a, n, x, y);
    return 0;
}

// Java implementation of the approach
 
class GFG
{
    // Function to return the count of numbers
    static int countNumbers(int a[], int n, int x, int y)
    {
     
        // Base case
        if (y < x)
            return n;
     
        // Count the numbers
        int count1 = 0, count2 = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] + y <= x)
                count1++;
            else if (a[i] <= x)
                count2++;
        }
        int number = (count2 + 1) / 2 + count1;
        return number;
    }
     
    // Driver Code
    public static void main(String []args)
    {
        int a[] = { 1, 2, 4, 2, 3 };
        int n = a.length;
        int x = 3, y = 3;
        System.out.println(countNumbers(a, n, x, y));   
    }
}
 
// This code is contributed by ihritik

# Python3 implementation of the approach
 
# Function to return the count of numbers
def countNumbers( a,  n, x, y):
 
 
    # Base case
    if (y < x):
        return n
 
    # Count the numbers
    count1 = 0
    count2 = 0
    for i in range ( 0, n):
 
        if (a[i] + y <= x):
            count1 = count1 + 1
        elif (a[i] <= x):
            count2 = count2 + 1
     
 
    number = (count2 + 1) // 2 + count1
 
    return number
 
 
# Driver Code
a = [ 1, 2, 4, 2, 3 ]
n = len(a)
 
x = 3
y = 3
print(countNumbers(a, n, x, y))
 
# This code is contributed by ihritik

// C# implementation of the approach
using System;
 
class GFG
{
    // Function to return the count of numbers
    static int countNumbers(int []a, int n, int x, int y)
    {
     
        // Base case
        if (y < x)
            return n;
     
        // Count the numbers
        int count1 = 0, count2 = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] + y <= x)
                count1++;
            else if (a[i] <= x)
                count2++;
        }
        int number = (count2 + 1) / 2 + count1;
        return number;
    }
     
    // Driver Code
    public static void Main()
    {
        int [] a = { 1, 2, 4, 2, 3 };
        int n = a.Length;
        int x = 3, y = 3;
        Console.WriteLine(countNumbers(a, n, x, y));
    }
}
 
// This code is contributed by ihritik

<?php
// PHP implementation of the approach
 
// Function to return the count of numbers
function countNumbers($a, $n, $x, $y)
{
 
    // Base case
    if ($y < $x)
        return $n;
 
    // Count the numbers
    $count1 = 0 ;
    $count2 = 0 ;
    for ($i = 0; $i < $n; $i++)
    {
 
        if ($a[$i] + $y <= $x)
            $count1++;
        else if ($a[$i] <= $x)
            $count2++;
    }
 
    $number = floor(($count2 + 1) / 2) + $count1;
 
    return $number;
}
 
// Driver Code
$a = array( 1, 2, 4, 2, 3 );
$n = sizeof($a);
 
$x = 3;
$y = 3;
 
echo countNumbers($a, $n, $x, $y);
 
// This code is contributed by Ryuga
?>

<script>
 
// javascript implementation of the approach
 
// Function to return the count of numbers
function countNumbers(a, n, x, y)
{
 
    // Base case
    if (y < x)
        return n;
     
    var i;
    // Count the numbers
    var count1 = 0, count2 = 0;
    for (i = 0; i < n; i++) {
 
        if (a[i] + y <= x)
            count1++;
        else if (a[i] <= x)
            count2++;
    }
 
    var number = (count2 + 1) / 2 + count1;
 
    return number;
}
 
// Driver Code
    var a = [1, 2, 4, 2, 3];
    var n = a.length;
 
    var x = 3, y = 3;
    document.write(parseInt(countNumbers(a, n, x, y)));
 
// This code is contributed by ipg2016107.
</script>

2

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es el número de elementos de la array.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.