Número de formas de anotar carreras R en bolas B con portillos W como máximo

Posted on by Rudeus Greyrat

Dados tres números enteros R , B y W que denotan el número de carreras , bolas y wickets . Uno puede anotar 0, 1, 2, 3, 4, 6 o un wicket en una sola bola en un partido de cricket. La tarea es contar el número de formas en que un equipo puede anotar exactamente R carreras en exactamente B bolas con un máximo de W wickets . Dado que la cantidad de formas será grande, imprima la respuesta módulo 1000000007 . 
Ejemplos: 
 

Entrada: R = 4, B = 2, W = 2 
Salida: 7 
Las 7 vías son: 
0, 4 
4, 0 
Wicket, 4 
4, Wicket 
1, 3 
3, 1 
2, 2 
Entrada: R = 40, B = 10, W = 4 
Salida: 653263 
 

Enfoque: El problema se puede resolver usando Programación Dinámica y Combinatoria . La recurrencia tendrá 6 estados, inicialmente comenzamos con carreras = 0 , bolas = 0 y ventanillas = 0 . Los estados serán: 
 

  • Si un equipo anota 1 carrera con una pelota entonces corre = corre + 1 y pelotas = pelotas + 1 .
  • Si un equipo anota 2 carreras de una pelota entonces carreras = carreras + 2 y bolas = bolas + 1 .
  • Si un equipo anota 3 corridas de una pelota entonces corre = corre + 3 y pelotas = pelotas + 1 .
  • Si un equipo anota 4 corridas de una pelota entonces corre = corre + 4 y pelotas = pelotas + 1 .
  • Si un equipo anota 6 corridas de una pelota entonces corre = corre + 6 y pelotas = pelotas + 1 .
  • Si un equipo no anota ninguna corrida con una pelota entonces corre = corre y pelotas = pelotas + 1 .
  • Si un equipo pierde 1 wicket de una pelota entonces corre = corre y pelotas = pelotas + 1 y wickets = wickets + 1 .

El DP constará de tres etapas, siendo el estado corrido un máximo de 6* Bolas , ya que es el máximo posible. Por lo tanto , dp[i][j][k] denota el número de formas en que se pueden anotar i carreras exactamente en j bolas con k wickets perdidos . 
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define RUNMAX 300
#define BALLMAX 50
#define WICKETMAX 10
 
// Function to return the number of ways
// to score R runs in B balls with
// at most W wickets
int CountWays(int r, int b, int l, int R, int B, int W,
              int dp[RUNMAX][BALLMAX][WICKETMAX])
{
 
    // If the wickets lost are more
    if (l > W)
        return 0;
 
    // If runs scored are more
    if (r > R)
        return 0;
 
    // If condition is met
    if (b == B && r == R)
        return 1;
 
    // If no run got scored
    if (b == B)
        return 0;
 
    // Already visited state
    if (dp[r][b][l] != -1)
        return dp[r][b][l];
 
    int ans = 0;
 
    // If scored 0 run
    ans += CountWays(r, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 1 run
    ans += CountWays(r + 1, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 2 runs
    ans += CountWays(r + 2, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 3 runs
    ans += CountWays(r + 3, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 4 runs
    ans += CountWays(r + 4, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 6 runs
    ans += CountWays(r + 6, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored no run and lost a wicket
    ans += CountWays(r, b + 1, l + 1, R, B, W, dp);
    ans = ans % mod;
 
    // Memoize and return
    return dp[r][b][l] = ans;
}
 
// Driver code
int main()
{
    int R = 40, B = 10, W = 4;
 
    int dp[RUNMAX][BALLMAX][WICKETMAX];
    memset(dp, -1, sizeof dp);
 
    cout << CountWays(0, 0, 0, R, B, W, dp);
 
    return 0;
}

Java

// Java implementation of the approach
 
class GFG
{
      
static int mod = 1000000007;
static int RUNMAX = 300;
static int BALLMAX = 50;
static int WICKETMAX = 10;
  
// Function to return the number of ways
// to score R runs in B balls with
// at most W wickets
static int CountWays(int r, int b, int l,
                    int R, int B, int W,
                            int [][][]dp)
{
  
    // If the wickets lost are more
    if (l > W)
        return 0;
  
    // If runs scored are more
    if (r > R)
        return 0;
  
    // If condition is met
    if (b == B && r == R)
        return 1;
  
    // If no run got scored
    if (b == B)
        return 0;
  
    // Already visited state
    if (dp[r][b][l] != -1)
        return dp[r][b][l];
  
    int ans = 0;
  
    // If scored 0 run
    ans += CountWays(r, b + 1, l, R, B, W, dp);
    ans = ans % mod;
  
    // If scored 1 run
    ans += CountWays(r + 1, b + 1, l, R, B, W, dp);
    ans = ans % mod;
  
    // If scored 2 runs
    ans += CountWays(r + 2, b + 1, l, R, B, W, dp);
    ans = ans % mod;
  
    // If scored 3 runs
    ans += CountWays(r + 3, b + 1, l, R, B, W, dp);
    ans = ans % mod;
  
    // If scored 4 runs
    ans += CountWays(r + 4, b + 1, l, R, B, W, dp);
    ans = ans % mod;
  
    // If scored 6 runs
    ans += CountWays(r + 6, b + 1, l, R, B, W, dp);
    ans = ans % mod;
  
    // If scored no run and lost a wicket
    ans += CountWays(r, b + 1, l + 1, R, B, W, dp);
    ans = ans % mod;
  
    // Memoize and return
    return dp[r][b][l] = ans;
}
  
// Driver code
public static void main(String[] args)
{
    int R = 40, B = 10, W = 4;
  
    int[][][] dp = new int[RUNMAX][BALLMAX][WICKETMAX];
    for(int i = 0; i < RUNMAX;i++)
        for(int j = 0; j < BALLMAX; j++)
            for(int k = 0; k < WICKETMAX; k++)
    dp[i][j][k]=-1;
  
    System.out.println(CountWays(0, 0, 0, R, B, W, dp));
}
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
mod = 1000000007
RUNMAX = 300
BALLMAX = 50
WICKETMAX = 10
 
# Function to return the number of ways
# to score R runs in B balls with
# at most W wickets
def CountWays(r, b, l, R, B, W, dp):
     
    # If the wickets lost are more
    if (l > W):
        return 0;
 
    # If runs scored are more
    if (r > R):
        return 0;
 
    # If condition is met
    if (b == B and r == R):
        return 1;
 
    # If no run got scored
    if (b == B):
        return 0;
 
    # Already visited state
    if (dp[r][b][l] != -1):
        return dp[r][b][l]
         
    ans = 0;
 
    # If scored 0 run
    ans += CountWays(r, b + 1, l,
                     R, B, W, dp);
    ans = ans % mod;
 
    # If scored 1 run
    ans += CountWays(r + 1, b + 1, l,
                     R, B, W, dp);
    ans = ans % mod;
 
    # If scored 2 runs
    ans += CountWays(r + 2, b + 1, l,
                     R, B, W, dp);
    ans = ans % mod;
 
    # If scored 3 runs
    ans += CountWays(r + 3, b + 1, l,
                     R, B, W, dp);
    ans = ans % mod;
 
    # If scored 4 runs
    ans += CountWays(r + 4, b + 1, l,
                     R, B, W, dp);
    ans = ans % mod;
 
    # If scored 6 runs
    ans += CountWays(r + 6, b + 1, l,
                     R, B, W, dp);
    ans = ans % mod;
 
    # If scored no run and lost a wicket
    ans += CountWays(r, b + 1, l + 1,
                     R, B, W, dp);
    ans = ans % mod;
     
    # Memoize and return
    dp[r][b][l] = ans
     
    return ans;
     
# Driver code   
if __name__=="__main__":
     
    R = 40
    B = 10
    W = 40
     
    dp = [[[-1 for k in range(WICKETMAX)]
               for j in range(BALLMAX)]
               for i in range(RUNMAX)]
     
    print(CountWays(0, 0, 0, R, B, W, dp))
 
# This code is contributed by rutvik_56

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG
{
     
static int mod = 1000000007;
static int RUNMAX = 300;
static int BALLMAX = 50;
static int WICKETMAX = 10;
 
// Function to return the number of ways
// to score R runs in B balls with
// at most W wickets
static int CountWays(int r, int b, int l,
                    int R, int B, int W,
                            int [,,]dp)
{
 
    // If the wickets lost are more
    if (l > W)
        return 0;
 
    // If runs scored are more
    if (r > R)
        return 0;
 
    // If condition is met
    if (b == B && r == R)
        return 1;
 
    // If no run got scored
    if (b == B)
        return 0;
 
    // Already visited state
    if (dp[r, b, l] != -1)
        return dp[r, b, l];
 
    int ans = 0;
 
    // If scored 0 run
    ans += CountWays(r, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 1 run
    ans += CountWays(r + 1, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 2 runs
    ans += CountWays(r + 2, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 3 runs
    ans += CountWays(r + 3, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 4 runs
    ans += CountWays(r + 4, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored 6 runs
    ans += CountWays(r + 6, b + 1, l, R, B, W, dp);
    ans = ans % mod;
 
    // If scored no run and lost a wicket
    ans += CountWays(r, b + 1, l + 1, R, B, W, dp);
    ans = ans % mod;
 
    // Memoize and return
    return dp[r, b, l] = ans;
}
 
// Driver code
static void Main()
{
    int R = 40, B = 10, W = 4;
 
    int[,,] dp = new int[RUNMAX, BALLMAX, WICKETMAX];
    for(int i = 0; i < RUNMAX;i++)
        for(int j = 0; j < BALLMAX; j++)
            for(int k = 0; k < WICKETMAX; k++)
    dp[i, j, k]=-1;
 
    Console.WriteLine(CountWays(0, 0, 0, R, B, W, dp));
}
}
 
// This code is contributed by mits

Javascript

<script>
// javascript implementation of the approach
    var mod = 1000000007;
    var RUNMAX = 300;
    var BALLMAX = 50;
    var WICKETMAX = 10;
 
    // Function to return the number of ways
    // to score R runs in B balls with
    // at most W wickets
    function CountWays(r , b , l , R , B , W,  dp) {
 
        // If the wickets lost are more
        if (l > W)
            return 0;
 
        // If runs scored are more
        if (r > R)
            return 0;
 
        // If condition is met
        if (b == B && r == R)
            return 1;
 
        // If no run got scored
        if (b == B)
            return 0;
 
        // Already visited state
        if (dp[r][b][l] != -1)
            return dp[r][b][l];
 
        var ans = 0;
 
        // If scored 0 run
        ans += CountWays(r, b + 1, l, R, B, W, dp);
        ans = ans % mod;
 
        // If scored 1 run
        ans += CountWays(r + 1, b + 1, l, R, B, W, dp);
        ans = ans % mod;
 
        // If scored 2 runs
        ans += CountWays(r + 2, b + 1, l, R, B, W, dp);
        ans = ans % mod;
 
        // If scored 3 runs
        ans += CountWays(r + 3, b + 1, l, R, B, W, dp);
        ans = ans % mod;
 
        // If scored 4 runs
        ans += CountWays(r + 4, b + 1, l, R, B, W, dp);
        ans = ans % mod;
 
        // If scored 6 runs
        ans += CountWays(r + 6, b + 1, l, R, B, W, dp);
        ans = ans % mod;
 
        // If scored no run and lost a wicket
        ans += CountWays(r, b + 1, l + 1, R, B, W, dp);
        ans = ans % mod;
 
        // Memoize and return
        return dp[r][b][l] = ans;
    }
 
    // Driver code   
        var R = 40, B = 10, W = 4;
 
        var dp = Array(RUNMAX).fill().map(()=>Array(BALLMAX).fill().map(()=>Array(WICKETMAX).fill(0)));
        for (i = 0; i < RUNMAX; i++)
            for (j = 0; j < BALLMAX; j++)
                for (k = 0; k < WICKETMAX; k++)
                    dp[i][j][k] = -1;
 
        document.write(CountWays(0, 0, 0, R, B, W, dp));
 
// This code is contributed by umadevi9616
</script>
Producción: 

653263

 

Complejidad de tiempo: O(r*b*w), ya que estamos usando recursividad con memorización, por lo que evitaremos llamadas a funciones redundantes y la complejidad será O(r*b*w)

Espacio auxiliar: O(300*50*10), ya que estamos usando espacio extra para la array dp.

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *