Minimizar el producto de dos puntajes como máximo con M reducciones

Dados dos números enteros R1, R2 denota carreras anotadas por dos jugadores, y B1, B2 denota bolas enfrentadas por ellos respectivamente, la tarea es encontrar el valor mínimo de R1 * R2 que se puede obtener de manera que R1 y R2 se puedan reducir en M corridas que satisfacen las condiciones R1 ≥ B1 y R2 ≥ B2 .

Ejemplos:

Entrada: R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3
Salida: 220
Explicación: El producto mínimo que se puede obtener es disminuir R1 en 1 y R2 en 2, es decir (21 – 1) x (13 – 2) = 220.

Entrada: R1 = 7, B1 = 6, R2 = 9, B1 = 9, M = 4
Salida: 54

Enfoque: El producto mínimo se puede obtener reduciendo los números completamente a sus límites. Reducir R1 a su límite B1 y luego reducir R2 lo menos posible (sin exceder M ). De manera similar, reduzca R2 a B2 como máximo y luego reduzca R2 lo menos posible (sin exceder M ). El producto mínimo obtenido en los dos casos es la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to find the minimum
// product of R1 and R2 possible
int minProductUtil(int R1, int B1, int R2,
                   int B2, int M)
{
    int x = min(R1-B1, M);
     
    M -= x;
     
    // Reaching to its limit
    R1 -= x;
     
    // If M is remaining
    if (M > 0)
    {
        int y = min(R2 - B2, M);
        M -= y;
        R2 -= y;
    }
    return R1 * R2;
}
 
// Function to find the minimum
// product of R1 and R2
int minProduct(int R1, int B1, int R2, int B2, int M)
{
     
    // Case 1 - R1 reduces first
    int res1 = minProductUtil(R1, B1, R2, B2, M);
     
    // Case 2 - R2 reduces first
    int res2 = minProductUtil(R2, B2, R1, B1, M);
 
    return min(res1, res2);
}
 
// Driver Code
int main()
{
     
    // Given Input
    int R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3;
     
    // Function Call
    cout << (minProduct(R1, B1, R2, B2, M));
    return 0;
}
 
// This code is contributed by maddler

// Java program for the above approach
import java.io.*;
class GFG{
     
// Utility function to find the minimum
// product of R1 and R2 possible
static int minProductUtil(int R1, int B1, int R2,
                   int B2, int M)
{
    int x = Math.min(R1-B1, M);
     
    M -= x;
     
    // Reaching to its limit
    R1 -= x;
     
    // If M is remaining
    if (M > 0)
    {
        int y = Math.min(R2 - B2, M);
        M -= y;
        R2 -= y;
    }
    return R1 * R2;
}
 
// Function to find the minimum
// product of R1 and R2
static int minProduct(int R1, int B1, int R2, int B2, int M)
{
     
    // Case 1 - R1 reduces first
    int res1 = minProductUtil(R1, B1, R2, B2, M);
     
    // Case 2 - R2 reduces first
    int res2 = minProductUtil(R2, B2, R1, B1, M);
 
    return Math.min(res1, res2);
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given Input
    int R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3;
     
    // Function Call
    System.out.print((minProduct(R1, B1, R2, B2, M)));
}
}
 
// This code is contributed by shivanisinghss2110

# Python program for the above approach
 
# Utility function to find the minimum
# product of R1 and R2 possible
def minProductUtil(R1, B1, R2, B2, M):
 
    x = min(R1-B1, M)
 
    M -= x
     
    # Reaching to its limit
    R1 -= x
     
    # If M is remaining
    if M > 0:
        y = min(R2-B2, M)
        M -= y
        R2 -= y
 
    return R1 * R2
   
# Function to find the minimum
# product of R1 and R2
def minProduct(R1, B1, R2, B2, M):
     
    # Case 1 - R1 reduces first
    res1 = minProductUtil(R1, B1, R2, B2, M)
     
    # case 2 - R2 reduces first
    res2 = minProductUtil(R2, B2, R1, B1, M)
 
    return min(res1, res2)
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    R1 = 21; B1 = 10; R2 = 13; B2 = 11; M = 3
     
    # Function Call
    print(minProduct(R1, B1, R2, B2, M))

// C# program for the above approach
using System;
class GFG{
     
// Utility function to find the minimum
// product of R1 and R2 possible
static int minProductUtil(int R1, int B1, int R2,
                   int B2, int M)
{
    int x = Math.Min(R1-B1, M);
     
    M -= x;
     
    // Reaching to its limit
    R1 -= x;
     
    // If M is remaining
    if (M > 0)
    {
        int y = Math.Min(R2 - B2, M);
        M -= y;
        R2 -= y;
    }
    return R1 * R2;
}
 
// Function to find the minimum
// product of R1 and R2
static int minProduct(int R1, int B1, int R2, int B2, int M)
{
     
    // Case 1 - R1 reduces first
    int res1 = minProductUtil(R1, B1, R2, B2, M);
     
    // Case 2 - R2 reduces first
    int res2 = minProductUtil(R2, B2, R1, B1, M);
 
    return Math.Min(res1, res2);
}
 
// Driver Code
public static void Main (String[] args)
{
     
    // Given Input
    int R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3;
     
    // Function Call
    Console.Write((minProduct(R1, B1, R2, B2, M)));
}
}
 
// This code is contributed by shivanisinghss2110

<script>
 
// JavaScript program for the above approach
 
// Utility function to find the minimum
// product of R1 and R2 possible
function minProductUtil(R1, B1, R2, B2, M)
{
    let x = Math.min(R1 - B1, M);
    M -= x;
     
    // Reaching to its limit
    R1 -= x;
     
    // If M is remaining
    if (M > 0)
    {
        let y = Math.min(R2 - B2, M);
        M -= y;
        R2 -= y;
    }
    return R1 * R2;
}
 
// Function to find the minimum
// product of R1 and R2
function minProduct(R1, B1, R2, B2, M)
{
     
    // Case 1 - R1 reduces first
    let res1 = minProductUtil(R1, B1, R2, B2, M);
     
    // Case 2 - R2 reduces first
    let res2 = minProductUtil(R2, B2, R1, B1, M);
 
    return Math.min(res1, res2);
}
 
// Driver Code
 
// Given Input
let R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3;
 
// Function Call
document.write((minProduct(R1, B1, R2, B2, M)));
 
// This code is contributed by code_hunt
 
</script>

220

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)