Dadas dos strings S y T , donde S representa el primer carril en el que los vehículos se mueven de izquierda a derecha y T representa el segundo carril en el que los vehículos se mueven de derecha a izquierda. Los vehículos pueden ser B (bicicleta) , C (automóvil) o T (camión) . La tarea es encontrar la probabilidad de colisión entre dos camiones.
Ejemplos:
Entrada: S = “TCCBCTTB”, T = “BTCCBBTT”
Salida: 0,194444
Explicación:
Colisión total = 7
Accidente total = 36
Por lo tanto, la probabilidad se puede calcular por 7/36 = 0,19444.Entrada: S = “BTT”, T = “BTCBT”
Salida: 0,25000
Ilustración:
S = "TCCBCTTB", T = "BTCCBBTT"
Possible cases | Accidents | Collision
-----------------------------------------
TCCBCTTB | |
BTCCBBTT | 8 | 1
| |
TCCBCTTB | |
BTCCBBTT | 7 | 3
| |
TCCBCTTB | |
BTCCBBTT | 6 | 1
| |
TCCBCTTB | |
BTCCBBTT | 5 | 0
| |
TCCBCTTB | |
BTCCBBTT | 4 | 0
| |
TCCBCTTB | |
BTCCBBTT | 3 | 0
| |
TCCBCTTB | |
BTCCBBTT | 2 | 1
| |
TCCBCTTB | |
BTCCBBTT | 1 | 1
Total number of accidents: 8+7+6+5+4+3+2+1=36
Total number of collision: 1+3+1+0+0+0+1+1=7
Probability: 7/36=0.19444
Enfoque: siga los pasos a continuación para resolver el problema:
- Encuentre el número total de resultados favorables como el número total de colisiones (accidentes entre camiones) y el número total de resultados posibles (número total de colisiones) como el número total de accidentes.
- Inicialice una respuesta variable igual a 0 para almacenar el recuento de colisiones.
- Cuente el número de camiones en la string T y guárdelo en una cuenta variable .
- Iterar sobre los caracteres de las strings S y T simultáneamente:
- Si S[i] es igual a ‘T’ , incrementa la respuesta por conteo .
- Si T[i] es igual a ‘T’, disminuya la cuenta en 1 .
- Ahora, calcule el número total de posibles resultados (número total de accidentes). Es la suma de toda la longitud de la superposición si sigue desplazando la string a hacia la derecha o la string b hacia la izquierda en una unidad.
- Sea N la longitud de la string y M la string b . Entonces, el número total de superposiciones será:
- Si N > M entonces, será la suma de los primeros M números naturales, es decir, M*(M + 1)/2 .
- De lo contrario, será N*(N + 1)/2 + (M – N)*N .
- Encuentre la probabilidad como la razón del conteo de colisiones y el conteo de accidentes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate total
// number of accidents
double count_of_accident(string a,
string b)
{
// String size
int n = a.size(), m = b.size();
if (n > m)
return (m * (m + 1)) / 2;
else
return (n * (n + 1))
/ 2
+ (m - n) * n;
}
// Function to calculate count
// of all possible collision
double count_of_collision(string a,
string b)
{
int n = a.size(), m = b.size();
// Stores the count of collisions
int answer = 0;
// Total number of truck in lane b
int count_of_truck_in_lane_b = 0;
for (int i = 0; i < m; i++)
if (b[i] == 'T')
count_of_truck_in_lane_b++;
// Count total number of collisions
// while traversing the string a
for (int i = 0; i < n && i < m; i++) {
if (a[i] == 'T')
answer
+= count_of_truck_in_lane_b;
if (b[i] == 'T')
count_of_truck_in_lane_b--;
}
return answer;
}
// Function to calculate the
// probability of collisions
double findProbability(string a,
string b)
{
// Evaluate total outcome that is
// all the possible accident
double total_outcome
= count_of_accident(a, b);
// Evaluate favourable outcome i.e.,
// count of collision of trucks
double favourable_outcome
= count_of_collision(a, b);
// Print desired probability
cout << favourable_outcome
/ total_outcome;
}
// Driver Code
int main()
{
string S = "TCCBCTTB", T = "BTCCBBTT";
// Function Call
findProbability(S, T);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to calculate total
// number of accidents
static int count_of_accident(String a,
String b)
{
// String size
int n = a.length(), m = b.length();
if (n > m)
return (m * (m + 1)) / 2;
else
return (n * (n + 1))
/ 2
+ (m - n) * n;
}
// Function to calculate count
// of all possible collision
static double count_of_collision(String a,
String b)
{
int n = a.length(), m = b.length();
// Stores the count of collisions
double answer = 0;
// Total number of truck in lane b
int count_of_truck_in_lane_b = 0;
for (int i = 0; i < m; i++)
if (b.charAt(i) == 'T')
count_of_truck_in_lane_b++;
// Count total number of collisions
// while traversing the String a
for (int i = 0; i < n && i < m; i++)
{
if (a.charAt(i) == 'T')
answer
+= count_of_truck_in_lane_b;
if (b.charAt(i) == 'T')
count_of_truck_in_lane_b--;
}
return answer;
}
// Function to calculate the
// probability of collisions
static void findProbability(String a,
String b)
{
// Evaluate total outcome that is
// all the possible accident
int total_outcome
= count_of_accident(a, b);
// Evaluate favourable outcome i.e.,
// count of collision of trucks
double favourable_outcome
= count_of_collision(a, b);
// Print desired probability
System.out.printf("%4f",favourable_outcome
/ total_outcome);
}
// Driver Code
public static void main(String[] args)
{
String S = "TCCBCTTB", T = "BTCCBBTT";
// Function Call
findProbability(S, T);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to calculate total # number of accidents def count_of_accident(a, b): n = len(a) m = len(b) if (n > m): return (m * (m + 1)) / 2 else: return ((n * (n + 1)) / 2 + (m - n) * n) # Function to calculate count # of all possible collision def count_of_collision(a, b): # Size of string n = len(a) m = len(b) # Stores the count of collisions answer = 0 # Total number of truck in lane b count_of_truck_in_lane_b = 0 for i in range(0, m): if (b[i] == 'T'): count_of_truck_in_lane_b += 1 # Count total number of collisions # while traversing the string a i = 0 while (i < m and i < n): if (a[i] == 'T'): answer += count_of_truck_in_lane_b if (b[i] == 'T'): count_of_truck_in_lane_b -= 1 i += 1 return answer # Function to calculate the # probability of collisions def findProbability(a, b): # Evaluate total outcome that is # all the possible accident total_outcome = count_of_accident(a, b); # Evaluate favourable outcome i.e., # count of collision of trucks favourable_outcome = count_of_collision(a, b); # Print desired probability print(favourable_outcome / total_outcome) # Driver Code if __name__ == "__main__" : S = "TCCBCTTB" T = "BTCCBBTT" # Function Call findProbability(S, T) # This code is contributed by Virusbuddah_
C#
// C# program for the above approach
using System;
class GFG
{
// Function to calculate total
// number of accidents
static int count_of_accident(String a,
String b)
{
// String size
int n = a.Length, m = b.Length;
if (n > m)
return (m * (m + 1)) / 2;
else
return (n * (n + 1))
/ 2
+ (m - n) * n;
}
// Function to calculate count
// of all possible collision
static double count_of_collision(String a,
String b)
{
int n = a.Length, m = b.Length;
// Stores the count of collisions
double answer = 0;
// Total number of truck in lane b
int count_of_truck_in_lane_b = 0;
for (int i = 0; i < m; i++)
if (b[i] == 'T')
count_of_truck_in_lane_b++;
// Count total number of collisions
// while traversing the String a
for (int i = 0; i < n && i < m; i++)
{
if (a[i] == 'T')
answer
+= count_of_truck_in_lane_b;
if (b[i] == 'T')
count_of_truck_in_lane_b--;
}
return answer;
}
// Function to calculate the
// probability of collisions
static void findProbability(String a,
String b)
{
// Evaluate total outcome that is
// all the possible accident
int total_outcome
= count_of_accident(a, b);
// Evaluate favourable outcome i.e.,
// count of collision of trucks
double favourable_outcome
= count_of_collision(a, b);
// Print desired probability
Console.Write("{0:F4}", favourable_outcome
/ total_outcome);
}
// Driver Code
public static void Main(String[] args)
{
String S = "TCCBCTTB", T = "BTCCBBTT";
// Function Call
findProbability(S, T);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to calculate total
// number of accidents
function count_of_accident(a, b)
{
// String size
let n = a.length, m = b.length;
if (n > m)
return (m * (m + 1)) / 2;
else
return (n * (n + 1))
/ 2
+ (m - n) * n;
}
// Function to calculate count
// of all possible collision
function count_of_collision(a, b)
{
let n = a.length, m = b.length;
// Stores the count of collisions
let answer = 0;
// Total number of truck in lane b
let count_of_truck_in_lane_b = 0;
for (let i = 0; i < m; i++)
if (b[i] == 'T')
count_of_truck_in_lane_b++;
// Count total number of collisions
// while traversing the String a
for (let i = 0; i < n && i < m; i++)
{
if (a[i] == 'T')
answer
+= count_of_truck_in_lane_b;
if (b[i] == 'T')
count_of_truck_in_lane_b--;
}
return answer;
}
// Function to calculate the
// probability of collisions
function findProbability(a, b)
{
// Evaluate total outcome that is
// all the possible accident
let total_outcome
= count_of_accident(a, b);
// Evaluate favourable outcome i.e.,
// count of collision of trucks
let favourable_outcome
= count_of_collision(a, b);
// Print desired probability
document.write( favourable_outcome
/ total_outcome);
}
// Driver Code
let S = "TCCBCTTB", T = "BTCCBBTT";
// Function Call
findProbability(S, T);
// This code is contributed by souravghosh0416.
</script>
Producción:
0.194444
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ArifShaikh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA