Cuente el número de cuerdas (hechas de R, G y B) usando la combinación dada

Necesitamos hacer una string de tamaño n. Cada carácter de la string es ‘R’, ‘B’ o ‘G’. En la string final debe haber al menos r número de ‘R’, al menos b número de ‘B’ y al menos g número de ‘G’ (tal que r + g + b <= n). Necesitamos encontrar el número de tales strings posibles.

Ejemplos: 

Input : n = 4, r = 1, 
        b = 1, g = 1.
Output: 36 
No. of 'R' >= 1, 
No. of ‘G’ >= 1, 
No. of ‘B’ >= 1 and 
(No. of ‘R’) + (No. of ‘B’) + (No. of ‘G’) = n
then following cases are possible:
1. RBGR and its 12 permutation
2. RBGB and its 12 permutation
3. RBGG and its 12 permutation
Hence answer is 36.

Preguntado en : Directi

Implementación:

// C++ program to count number of possible strings
// with n characters.
#include<bits/stdc++.h>
using namespace std;
 
// Function to calculate number of strings
int possibleStrings( int n, int r, int b, int g)
{
    // Store factorial of numbers up to n
    // for further computation
    int fact[n+1];
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i-1] * i;
 
    // Find the remaining values to be added
    int left = n - (r+g+b);
    int sum = 0;
 
    // Make all possible combinations
    // of R, B and G for the remaining value
    for (int i = 0; i <= left; i++)
    {
        for (int j = 0; j<= left-i; j++)
        {
            int k = left - (i+j);
 
            // Compute permutation of each combination
            // one by one and add them.
            sum = sum + fact[n] /
                       (fact[i+r]*fact[j+b]*fact[k+g]);
        }
    }
 
    // Return total no. of strings/permutation
    return sum;
}
 
// Drivers code
int main()
{
    int n = 4, r = 2;
    int b = 0, g = 1;
    cout << possibleStrings(n, r, b, g);
    return 0;
}

// Java program to count number of possible
// strings with n characters.
 
class GFG{
     
    //Function to calculate number of strings
    static int possibleStrings( int n, int r, int b, int g)
    {
     // Store factorial of numbers up to n
     // for further computation
     int fact[] = new int[n+1];
     fact[0] = 1;
     for (int i = 1; i <= n; i++)
         fact[i] = fact[i-1] * i;
 
     // Find the remaining values to be added
     int left = n - (r+g+b);
     int sum = 0;
 
     // Make all possible combinations
     // of R, B and G for the remaining value
     for (int i = 0; i <= left; i++)
     {
         for (int j = 0; j<= left-i; j++)
         {
             int k = left - (i+j);
 
             // Compute permutation of each combination
             // one by one and add them.
             sum = sum + fact[n] /
                        (fact[i+r]*fact[j+b]*fact[k+g]);
         }
     }
 
     // Return total no. of strings/permutation
     return sum;
    }
 
    //Drivers code
    public static void main(String []args)
    {
        int n = 4, r = 2;
         int b = 0, g = 1;
         System.out.println(possibleStrings(n, r, b, g));
    }
}

# Python 3 program to count number of
# possible strings with n characters.
 
# Function to calculate number of strings
def possibleStrings(n, r, b, g):
     
    # Store factorial of numbers up to n
    # for further computation
    fact = [0 for i in range(n + 1)]
    fact[0] = 1
    for i in range(1, n + 1, 1):
        fact[i] = fact[i - 1] * i
 
    # Find the remaining values to be added
    left = n - (r + g + b)
    sum = 0
 
    # Make all possible combinations of
    # R, B and G for the remaining value
    for i in range(0, left + 1, 1):
        for j in range(0, left - i + 1, 1):
            k = left - (i + j)
 
            # Compute permutation of each
            # combination one by one and add them.
            sum = (sum + fact[n] / (fact[i + r] *
                         fact[j + b] * fact[k + g]))
     
    # Return total no. of
    # strings/permutation
    return sum
 
# Driver code
if __name__ == '__main__':
    n = 4
    r = 2
    b = 0
    g = 1
    print(int(possibleStrings(n, r, b, g)))
     
# This code is contributed by
# Sanjit_Prasad

// C# program to count number of possible
// strings with n characters.
using System;
 
class GFG
{
 
    //Function to calculate number of strings
    static int possibleStrings( int n, int r,
                                int b, int g)
    {
        // Store factorial of numbers up to n
        // for further computation
        int[] fact = new int[n + 1];
        fact[0] = 1;
     
        for (int i = 1; i <= n; i++)
            fact[i] = fact[i - 1] * i;
 
        // Find the remaining values to be added
        int left = n - (r + g + b);
        int sum = 0;
 
        // Make all possible combinations
        // of R, B and G for the remaining value
        for (int i = 0; i <= left; i++)
        {
            for (int j = 0; j <= left - i; j++)
            {
                int k = left - (i + j);
 
                // Compute permutation of each combination
                // one by one and add them.
                sum = sum + fact[n] / (fact[i + r] *
                        fact[j + b] * fact[k + g]);
            }
        }
 
        // Return total no. of strings/permutation
        return sum;
    }
 
    //Drivers code
    public static void Main()
    {
        int n = 4, r = 2;
        int b = 0, g = 1;
        Console.WriteLine(possibleStrings(n, r, b, g));
    }
}
 
// This Code is contributed by Code_Mech.

<?php
// PHP program to count number
// of possible strings with
// n characters.
 
// Function to calculate
// number of strings
function possibleStrings( $n, $r, $b, $g)
{
     
    // Store factorial of
    // numbers up to n for
    // further computation
    $fact[0] = 1;
    for ($i = 1; $i <= $n; $i++)
        $fact[$i] = $fact[$i - 1] * $i;
 
    // Find the remaining
    // values to be added
    $left = $n - ($r + $g + $b);
    $sum = 0;
 
    // Make all possible combinations
    // of R, B and G for the remaining value
    for ($i = 0; $i <= $left; $i++)
    {
        for ($j = 0; $j <= $left - $i; $j++)
        {
            $k = $left - ($i+$j);
 
            // Compute permutation of
            // each combination one
            // by one and add them.
            $sum = $sum + $fact[$n] /
                   ($fact[$i + $r] *
                   $fact[$j + $b] *
                   $fact[$k + $g]);
        }
    }
 
    // Return total no. of
    // strings/permutation
    return $sum;
}
 
    // Driver Code
    $n = 4; $r = 2;
    $b = 0; $g = 1;
     
    echo possibleStrings($n, $r, $b, $g);
 
// This code is contributed by jit_t.
?>

<script>
// Javascript program to count number of possible
// strings with n characters.
     
    // Function to calculate number of strings
    function possibleStrings(n,r,b,g)
    {
        // Store factorial of numbers up to n
     // for further computation
     let fact = new Array(n+1);
     fact[0] = 1;
     for (let i = 1; i <= n; i++)
         fact[i] = fact[i-1] * i;
   
     // Find the remaining values to be added
     let left = n - (r+g+b);
     let sum = 0;
   
     // Make all possible combinations
     // of R, B and G for the remaining value
     for (let i = 0; i <= left; i++)
     {
         for (let j = 0; j<= left-i; j++)
         {
             let k = left - (i+j);
   
             // Compute permutation of each combination
             // one by one and add them.
             sum = sum + fact[n] /
                        (fact[i+r]*fact[j+b]*fact[k+g]);
         }
     }
   
     // Return total no. of strings/permutation
     return sum;
    }
     
    // Drivers code
    let n = 4, r = 2;
    let b = 0, g = 1;
    document.write(possibleStrings(n, r, b, g));
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

22

Complejidad temporal: O(n*n).
Espacio Auxiliar: O(n).

Para manejar n con números grandes, podemos usar el concepto de Factorial Grande .

Este artículo es una contribución de Sahil Chhabra . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.