En tiempos de COVID, una sala de cine debe seguir una regla de distancia social en la que cada dos personas sentadas deben tener al menos 6 pies de distancia entre ellas.
Ejemplos:
Entrada: lista = {5, 2, 4, 1, 2}
Salida: 16
Explicación: De acuerdo con la lista dada, los asientos están dispuestos como:
S1 <–5–> S2 <–2–> S3 <–4–> S4 <–1–> S5 <–2–> S6
Esto tiene 16 posibles arreglos de asientos
Estas son las combinaciones válidas (1 medio tomado):
000000 101000 000010 100001
100000 000100 100010 010001
010000 100100 010010
001001 0010100 010Entrada: lista = {8, 10, 16}
Salida: 16
Explicación: Esto tiene 16 arreglos de asientos posibles
Cada combinación es una combinación válida. Cuatro plazas => 2^4 combinaciones.
Enfoque ingenuo: el enfoque ingenuo consiste en utilizar el retroceso . En cada asiento dado, hay dos opciones, sentarse o no sentarse. Visite todos los arreglos posibles y encuentre las soluciones válidas. Siga los pasos que se mencionan a continuación:
- Comience desde el primer asiento.
- Para cada asiento comprobar si la distancia del asiento anterior es válida o no.
- Si no es válido, pase al siguiente asiento.
- Si es válido, entonces hay dos posibilidades, sentarse o no sentarse. Utilice ambas opciones y muévase al siguiente asiento.
- Utilice estos criterios de forma recursiva para todos los asientos.
- El número total de arreglos encontrados al final es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior.
Python3
# Python program to implement the approach # Function to count all valid arrangements def get_possible_seatings(seats): # Account for the last seat seats.append(0) arrangement = [] total_seatings = 0 dist = 6 # Function for backtracking def dfs(curr, prev_dist): nonlocal total_seatings if curr > len(seats): return if curr == len(seats): # This arrangement possible total_seatings += 1 return # Have only one choice, don't sit if prev_dist < dist: dfs(curr+1, prev_dist+seats[curr]) else: # Have 2 choices here arrangement.append(curr) # Sit here dfs(curr+1, seats[curr]) arrangement.pop(-1) # Don't sit here dfs(curr+1, prev_dist+seats[curr]) return # Loop to implement backtracking # and call the dfs function for index in range(len(seats)): arrangement.clear() arrangement.append(index) dfs(index + 1, seats[index]) # Account for no seats occupied return total_seatings + 1 # Driver code if __name__ == "__main__": list = [5, 2, 4, 1, 2] ans = get_possible_seatings(list) print(ans)
Javascript
<script>
// JavaScript program to implement the approach
// Function to count all valid arrangements
function get_possible_seatings(seats){
// Account for the last seat
seats.push(0)
arrangement = []
total_seatings = 0
dist = 6
// Function for backtracking
function dfs(curr, prev_dist){
if(curr > seats.length)
return
if(curr == seats.length){
// This arrangement possible
total_seatings += 1
return
}
// Have only one choice, don't sit
if(prev_dist < dist)
dfs(curr+1, prev_dist+seats[curr])
else{
// Have 2 choices here
arrangement.push(curr)
// Sit here
dfs(curr+1, seats[curr])
arrangement.pop(-1)
// Don't sit here
dfs(curr+1, prev_dist+seats[curr])
}
return
}
// Loop to implement backtracking
// and call the dfs function
for(let index=0;index<seats.length;index++){
arrangement = []
arrangement.push(index)
dfs(index + 1, seats[index])
}
// Account for no seats occupied
return total_seatings + 1
}
// Driver code
list = [5, 2, 4, 1, 2]
ans = get_possible_seatings(list)
document.write(ans)
// This code is contributed by shinjanpatra
</script>
Producción
16
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: un enfoque eficiente es usar programación dinámica . Use una array dp[] para almacenar los posibles arreglos de asientos hasta el i-ésimo asiento. Revisa cada uno de los asientos a partir del 1ro. Si la distancia entre el asiento actual ‘i’ y el asiento anterior ‘j’ es válida (>= 6), agregue dp[j] a dp[i] . Básicamente, esto significa que tanto el asiento anterior como el asiento actual se pueden ocupar juntos. El número total de formas de sentarse aumentará según el número de formas de sentarse en el asiento anterior. Siga los pasos que se mencionan a continuación:
- Comience a iterar desde el primer asiento.
- Para cada asiento comprobar si la distancia desde el asiento ocupado anteriormente es válida o no.
- Si es válido, entonces incremente el número de arreglos posibles por los arreglos del asiento ocupado previamente.
- Si no, mantenga los arreglos sin cambios y muévase al siguiente asiento.
- El valor final en el último asiento es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
// sum function
int sum(vector<int>& v)
{
int res = 0;
for (auto dt : v)
res += dt;
return res;
}
// Function to count all valid arrangements
int get_possible_seatings(vector<int>& seats)
{
int dist = 6;
// Account for the last seat
seats.push_back(0);
// Each seat can be occupied individually
vector<int> dp(seats.size(), 1);
// Keep track of total distance
// from first seat
vector<int> total_distance(seats.size(), 0);
int prefix_sum = seats[0];
for (int index = 1; index < seats.size(); ++index) {
total_distance[index] = prefix_sum;
prefix_sum += seats[index];
}
// Start from second seat onwards,
// this is the curr seat 'i'
for (int i = 1; i < seats.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (total_distance[i] - total_distance[j]
>= dist)
dp[i] += dp[j];
}
}
// Account for no seat occupied
return sum(dp) + 1;
}
// Driver code
int main()
{
vector<int> list{ 5, 2, 4, 1, 2 };
int ans = get_possible_seatings(list);
cout << (ans);
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// sum function
static int sum(int[] v)
{
int res = 0;
for (int i = 0; i < v.length; i++)
res += v[i];
return res;
}
// Function to count all valid arrangements
static int get_possible_seatings(ArrayList<Integer> seats)
{
int dist = 6;
// Account for the last seat
seats.add(0);
// Each seat can be occupied individually
int[] dp = new int[seats.size()];
for (int i = 0; i < seats.size(); i++) {
dp[i] = 1;
}
// Keep track of total distance
// from first seat
int[] total_distance = new int[seats.size()];
for (int i = 0; i < seats.size(); i++) {
total_distance[i] = 0;
}
int prefix_sum = (int)seats.get(0);
for (int index = 1; index < seats.size(); ++index) {
total_distance[index] = prefix_sum;
prefix_sum += (int)seats.get(index) ;
}
// Start from second seat onwards,
// this is the curr seat 'i'
for (int i = 1; i < seats.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (total_distance[i] - total_distance[j]
>= dist)
dp[i] += dp[j];
}
}
// Account for no seat occupied
return sum(dp) + 1;
}
// Driver Code
public static void main(String[] args)
{
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(5);
list.add(2);
list.add(4);
list.add(1);
list.add(2);
int ans = get_possible_seatings(list);
System.out.print(ans);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python program to implement the approach # Function to count all valid arrangements def get_possible_seatings(seats): dist = 6 # Account for the last seat seats.append(0) # Each seat can be occupied individually dp = [1] * len(seats) # Keep track of total distance # from first seat total_distance = [0] * len(seats) prefix_sum = seats[0] for index, i in enumerate(seats[1:], 1): total_distance[index] = prefix_sum prefix_sum += i # Start from second seat onwards, # this is the curr seat 'i' for i in range(1, len(seats)): for j in range(i): if total_distance[i] \ - total_distance[j] >= dist: dp[i] += dp[j] # Account for no seat occupied return sum(dp) + 1 # Driver code if __name__ == "__main__": list = [5, 2, 4, 1, 2] ans = get_possible_seatings(list) print(ans)
C#
// C# program to implement the approach
using System;
using System.Collections;
class GFG {
// sum function
static int sum(int[] v)
{
int res = 0;
for (int i = 0; i < v.Length; i++)
res += v[i];
return res;
}
// Function to count all valid arrangements
static int get_possible_seatings(ArrayList seats)
{
int dist = 6;
// Account for the last seat
seats.Add(0);
// Each seat can be occupied individually
int[] dp = new int[seats.Count];
for (int i = 0; i < seats.Count; i++) {
dp[i] = 1;
}
// Keep track of total distance
// from first seat
int[] total_distance = new int[seats.Count];
for (int i = 0; i < seats.Count; i++) {
total_distance[i] = 0;
}
int prefix_sum = (int)seats[0];
for (int index = 1; index < seats.Count; ++index) {
total_distance[index] = prefix_sum;
prefix_sum += (int)seats[index];
}
// Start from second seat onwards,
// this is the curr seat 'i'
for (int i = 1; i < seats.Count; ++i) {
for (int j = 0; j < i; ++j) {
if (total_distance[i] - total_distance[j]
>= dist)
dp[i] += dp[j];
}
}
// Account for no seat occupied
return sum(dp) + 1;
}
// Driver code
public static void Main()
{
ArrayList list = new ArrayList();
list.Add(5);
list.Add(2);
list.Add(4);
list.Add(1);
list.Add(2);
int ans = get_possible_seatings(list);
Console.Write(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// sum function
function sum(v) {
let res = 0;
for (let dt of v)
res += dt;
return res;
}
// Function to count all valid arrangements
function get_possible_seatings(seats) {
let dist = 6;
// Account for the last seat
seats.push(0);
// Each seat can be occupied individually
let dp = new Array(seats.length).fill(1);
// Keep track of total distance
// from first seat
let total_distance = new Array(seats.length).fill(0)
let prefix_sum = seats[0];
for (let index = 1; index < seats.length; ++index) {
total_distance[index] = prefix_sum;
prefix_sum += seats[index];
}
// Start from second seat onwards,
// this is the curr seat 'i'
for (let i = 1; i < seats.length; ++i) {
for (let j = 0; j < i; ++j) {
if (total_distance[i] - total_distance[j]
>= dist)
dp[i] += dp[j];
}
}
// Account for no seat occupied
return sum(dp) + 1;
}
// Driver code
let list = [5, 2, 4, 1, 2];
let ans = get_possible_seatings(list);
document.write(ans);
// This code is contributed by Potta Lokesh
</script>
Producción
16
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)