Dado un número entero N , la tarea es pintar una cuadrícula de tamaño N x 3 usando los colores Rojo , Amarillo o Verde mientras se hace que ningún par de celdas adyacentes tenga el mismocolor. Imprime el número de formas distintas en las que es posible
Ejemplos:
Entrada: N = 1
Salida: 12
Explicación:
Existen las siguientes 12 formas posibles de pintar la cuadrícula:
- rojo, amarillo, rojo
- amarillo, rojo, amarillo
- Verde, Rojo, Amarillo
- rojo, amarillo, verde
- amarillo, rojo, verde
- verde, rojo, verde
- rojo, verde, rojo
- amarillo, verde, rojo
- Verde, Amarillo, Rojo
- rojo, verde, amarillo
- amarillo, verde, amarillo
- Verde, Amarillo, Verde
Entrada: N = 2
Salida: 102
Enfoque: siga los pasos a continuación para resolver el problema:
- Las formas de colorear una fila se pueden dividir en las siguientes dos categorías:
- Las celdas más a la izquierda y más a la derecha son del mismo color.
- Las celdas más a la izquierda y más a la derecha son de diferentes colores.
- Considerando el primer caso:
- Existen seis formas posibles de pintar la fila de modo que los colores más a la izquierda y más a la derecha sean del mismo color.
- Por cada color que ocupa tanto la celda más a la izquierda como la más a la derecha, existen dos colores diferentes con los que se puede colorear la fila del medio.
- Considerando el segundo caso:
- Existen seis formas posibles de pintar los colores más a la izquierda y más a la derecha son diferentes.
- Tres opciones para la celda de la izquierda, dos opciones para la del medio y llene la celda más a la derecha con el único color restante. Por lo tanto, el número total de posibilidades es 3*2*1 = 6 .
- Ahora, para las celdas posteriores, observe el siguiente ejemplo:
- Si la fila anterior está pintada como Red Green Red , existen las siguientes cinco formas válidas de colorear la fila actual:
- {Verde Rojo Verde}
- {Verde Rojo Amarillo}
- {Verde Amarillo Verde}
- {Amarillo Rojo Verde}
- {Amarillo Rojo Amarillo}
- De la observación anterior, es claro que tres posibilidades tienen extremos con el mismo color y dos posibilidades tienen extremos con diferentes colores.
- Si la fila anterior es de color Rojo Verde Amarillo , existen las siguientes cuatro posibilidades de colorear la fila actual:
- {Verde Rojo Verde}
- {Verde Amarillo Rojo}
- {Verde Amarillo Verde}
- {Amarillo Rojo Verde}
- De la observación anterior, es claro que las posibilidades tienen extremos del mismo color, y dos posibilidades tienen extremos con colores diferentes.
- Si la fila anterior está pintada como Red Green Red , existen las siguientes cinco formas válidas de colorear la fila actual:
- Por lo tanto, con base en las observaciones anteriores, se puede definir la siguiente relación de recurrencia para el número de formas de pintar las N filas:
Recuento de formas de colorear la fila actual que tiene extremos del mismo color S N+1 = 3 * S N + 2D N
Recuento de formas de colorear la fila actual que tiene extremos de diferentes colores D N+1 = 2 * S N + 2D N
El número total de formas de pintar todas las N filas es igual a la suma de S N y D N .
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 count the number
// of ways to paint N * 3 grid
// based on given conditions
void waysToPaint(int n)
{
// Count of ways to pain a
// row with same colored ends
int same = 6;
// Count of ways to pain a row
// with different colored ends
int diff = 6;
// Traverse up to (N - 1)th row
for (int i = 0; i < n - 1; i++) {
// Calculate the count of ways
// to paint the current row
// For same colored ends
long sameTmp = 3 * same + 2 * diff;
// For different colored ends
long diffTmp = 2 * same + 2 * diff;
same = sameTmp;
diff = diffTmp;
}
// Print the total number of ways
cout << (same + diff);
}
// Driver Code
int main()
{
int N = 2;
waysToPaint(N);
}
// This code is contributed by ukasp.
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to count the number
// of ways to paint N * 3 grid
// based on given conditions
static void waysToPaint(int n)
{
// Count of ways to pain a
// row with same colored ends
long same = 6;
// Count of ways to pain a row
// with different colored ends
long diff = 6;
// Traverse up to (N - 1)th row
for (int i = 0; i < n - 1; i++) {
// Calculate the count of ways
// to paint the current row
// For same colored ends
long sameTmp = 3 * same + 2 * diff;
// For different colored ends
long diffTmp = 2 * same + 2 * diff;
same = sameTmp;
diff = diffTmp;
}
// Print the total number of ways
System.out.println(same + diff);
}
// Driver code
public static void main(String[] args)
{
int N = 2;
// Function call
waysToPaint(N);
}
}
Python3
# Python3 program for the above approach # Function to count the number # of ways to paint N * 3 grid # based on given conditions def waysToPaint(n): # Count of ways to pain a # row with same colored ends same = 6 # Count of ways to pain a row # with different colored ends diff = 6 # Traverse up to (N - 1)th row for _ in range(n - 1): # Calculate the count of ways # to paint the current row # For same colored ends sameTmp = 3 * same + 2 * diff # For different colored ends diffTmp = 2 * same + 2 * diff same = sameTmp diff = diffTmp # Print the total number of ways print(same + diff) # Driver Code N = 2 waysToPaint(N)
C#
// C# program for the above approach
using System;
class GFG {
// Function to count the number
// of ways to paint N * 3 grid
// based on given conditions
static void waysToPaint(int n)
{
// Count of ways to pain a
// row with same colored ends
long same = 6;
// Count of ways to pain a row
// with different colored ends
long diff = 6;
// Traverse up to (N - 1)th row
for (int i = 0; i < n - 1; i++) {
// Calculate the count of ways
// to paint the current row
// For same colored ends
long sameTmp = 3 * same + 2 * diff;
// For different colored ends
long diffTmp = 2 * same + 2 * diff;
same = sameTmp;
diff = diffTmp;
}
// Print the total number of ways
Console.WriteLine(same + diff);
}
// Driver code
static public void Main()
{
int N = 2;
waysToPaint(N);
}
}
// This code is contributed by offbeat
Javascript
<script>
// Javascript program for the above approach
// Function to count the number
// of ways to paint N * 3 grid
// based on given conditions
function waysToPaint(n)
{
// Count of ways to pain a
// row with same colored ends
var same = 6;
// Count of ways to pain a row
// with different colored ends
var diff = 6;
// Traverse up to (N - 1)th row
for(var i = 0; i < n - 1; i++)
{
// Calculate the count of ways
// to paint the current row
// For same colored ends
var sameTmp = 3 * same + 2 * diff;
// For different colored ends
var diffTmp = 2 * same + 2 * diff;
same = sameTmp;
diff = diffTmp;
}
// Print the total number of ways
document.write(same + diff);
}
// Driver code
var N = 2;
// Function call
waysToPaint(N);
// This code is contributed by Khushboogoyal499
</script>
Producción:
12
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA