Recuento de strings binarias posibles según las condiciones dadas

Dados dos enteros N y M , donde N denota el conteo de ‘0’ y M denota el conteo de ‘1’ , y un entero K , la tarea es encontrar el número máximo de strings binarias que se pueden generar de los siguientes dos tipos: 

• Una string puede constar de K ‘ 0 ‘s y un solo ‘ 1 ‘.
• Una string puede constar de K ‘ 1 ‘s y un solo ‘ 0 ‘.

Ejemplos: 

Entrada: N = 4, M = 4, K = 2 
Salida: 6 
Explicación: 
Recuento de ‘ 0 ‘s = 4 
Recuento de ‘ 1 ‘s = 4 
Las formas posibles de combinar 0 y 1 bajo restricciones dadas son {“001”, “001”} o {“001”, “110”} o {“110”, “110”} 
Por lo tanto, existen como máximo 2 combinaciones en una selección. 
Cada combinación se puede organizar en formas K + 1 , es decir, «001» se puede reorganizar para formar «010», «100» también. 
Por lo tanto, el máximo de strings posibles que se pueden generar es 3 * 2 = 6

Entrada: N = 101, M = 231, K = 15 
Salida: 320 

Enfoque: 
siga los pasos a continuación para resolver el problema: 

• Considere las siguientes tres condiciones para generar las máximas combinaciones posibles de strings binarias: 
  • El número de combinaciones no puede exceder N .
  • El número de combinaciones no puede exceder M .
  • El número de combinaciones no puede exceder (A+B)/(K + 1) .
• Por lo tanto, las combinaciones máximas posibles son min(A, B, (A + B)/ (K + 1)) .
• Por lo tanto, las máximas strings posibles que se pueden generar son (K + 1) * min(A, B, (A + B)/ (K + 1)) .

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate maximum
// possible strings that can be generated
long long countStrings(long long A,
                    long long B,
                    long long K)
{
 
    long long X = (A + B) / (K + 1);
 
    // Maximum possible strings
    return (min(A, min(B, X)) * (K + 1));
}
int main()
{
 
    long long N = 101, M = 231, K = 15;
    cout << countStrings(N, M, K);
    return 0;
}

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to generate maximum
// possible strings that can be generated
static long countStrings(long A, long B,
                        long K)
{
    long X = (A + B) / (K + 1);
 
    // Maximum possible strings
    return (Math.min(A, Math.min(B, X)) *
                                (K + 1));
}
 
// Driver Code
public static void main (String[] args)
{
    long N = 101, M = 231, K = 15;
     
    System.out.print(countStrings(N, M, K));
}
}
 
// This code is contributed by offbeat

# Python3 program to implement 
# the above approach 
  
# Function to generate maximum 
# possible strings that can be
# generated 
def countStrings(A, B, K): 
   
    X = (A + B) // (K + 1) 
   
    # Maximum possible strings 
    return (min(A, min(B, X)) * (K + 1)) 
 
# Driver code
N, M, K = 101, 231, 15
 
print(countStrings(N, M, K))
 
# This code is contributed divyeshrabadiya07

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to generate maximum
// possible strings that can be generated
static long countStrings(long A, long B,
                        long K)
{
    long X = (A + B) / (K + 1);
 
    // Maximum possible strings
    return (Math.Min(A, Math.Min(B, X)) *
                                (K + 1));
}
 
// Driver Code
public static void Main (string[] args)
{
    long N = 101, M = 231, K = 15;
     
    Console.Write(countStrings(N, M, K));
}
}
 
// This code is contributed by rock_cool

<script>
// JavaScript Program to implement
// the above approach
 
// Function to generate maximum
// possible strings that can be generated
function countStrings(A, B, K)
{
 
    let X = Math.floor((A + B) / (K + 1));
 
    // Maximum possible strings
    return (Math.min(A, Math.min(B, X)) * (K + 1));
}
 
 
    let N = 101, M = 231, K = 15;
    document.write(countStrings(N, M, K));
 
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Producción:

320

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