Dados tres enteros N, M y X, la tarea es encontrar el número de formas de formar una array, de modo que todos los números consecutivos de la array sean distintos, y el valor en cualquier índice de la array de 2 a N – 1( Teniendo en cuenta la indexación basada en 1) se encuentra entre 1 y M, mientras que el valor en el índice 1 es X y el valor en el índice N es 1.
Nota: El valor de X se encuentra entre 1 y M.
Ejemplos:
Entrada: N = 4, M = 3, X = 2
Salida: 3
Son posibles las siguientes arrays:
1) 2, 1, 2, 1
2) 2, 1, 3, 1
3) 2, 3, 2, 1
Entrada : N = 2, M = 3, X = 2
Salida: 1
La única array posible es: 2, 1
Planteamiento: El problema se puede resolver usando Programación Dinámica . Sea f(i) el número de formas de formar el arreglo hasta el i-ésimo índice, de modo que cada elemento consecutivo del arreglo sea distinto. Sea f(i, Uno) que represente el número de formas de formar el arreglo hasta el i-ésimo índice tal que cada elemento consecutivo del arreglo sea distinto y arr i = 1.
De manera similar, sea f(i, Ninguno) quien represente el número de formas de formar el arreglo hasta el i-ésimo índice, tal que cada elemento consecutivo del arreglo sea distinto y arr i no sea igual a 1.
Se forma la siguiente recurrencia:
f(i, Non-One) = f(i - 1, One) * (M - 1) + f(i - 1, Non-One) * (M - 2)
lo que significa que el número de formas de formar el arreglo hasta el i-ésimo índice con el arreglo i diferente a 1 se forma usando dos casos:
- Si el número en el arreglo i – 1 es 1, entonces seleccione un número de las opciones (M – 1) para colocarlo en el i -ésimo índice, ya que el arreglo i no es igual a 1.
- Si el número en la array i – 1 no es 1, entonces debemos excluir un número de las opciones (M – 2) , ya que la array i no es igual a 1 y la array i ≠ la array i – 1 .
De manera similar, f(i, One) = f(i – 1, Non-One) , dado que el número de formas de formar el arreglo hasta el i-ésimo índice con el arreglo i = 1, es el mismo que el número de formas de formar el arreglo hasta el índice (i – 1) con array i – 1 ≠ 1, por lo que en el índice i sólo hay una opción. Al final, la respuesta requerida es f(N, One), ya que la array N debe ser igual a 1.
A continuación, se muestra la implementación del enfoque anterior:
C++
// C++ program to count the number of ways
// to form arrays of N numbers such that the
// first and last numbers are fixed
// and all consecutive numbers are distinct
#include <bits/stdc++.h>
using namespace std;
// Returns the total ways to form arrays such that
// every consecutive element is different and each
// element except the first and last can take values
// from 1 to M
int totalWays(int N, int M, int X)
{
// define the dp[][] array
int dp[N + 1][2];
// if the first element is 1
if (X == 1) {
// there is only one way to place
// a 1 at the first index
dp[0][0] = 1;
}
else {
// the value at first index needs to be 1,
// thus there is no way to place a non-one integer
dp[0][1] = 0;
}
// if the first element was 1 then at index 1,
// only non one integer can be placed thus
// there are M - 1 ways to place a non one integer
// at index 2 and 0 ways to place a 1 at the 2nd index
if (X == 1) {
dp[1][0] = 0;
dp[1][1] = M - 1;
}
// Else there is one way to place a one at
// index 2 and if a non one needs to be placed here,
// there are (M - 2) options, i.e
// neither the element at this index
// should be 1, neither should it be
// equal to the previous element
else {
dp[1][0] = 1;
dp[1][1] = (M - 2);
}
// Build the dp array in bottom up manner
for (int i = 2; i < N; i++) {
// f(i, one) = f(i - 1, non-one)
dp[i][0] = dp[i - 1][1];
// f(i, non-one) = f(i - 1, one) * (M - 1) +
// f(i - 1, non-one) * (M - 2)
dp[i][1] = dp[i - 1][0] * (M - 1) + dp[i - 1][1] * (M - 2);
}
// last element needs to be one, so return dp[n - 1][0]
return dp[N - 1][0];
}
// Driver Code
int main()
{
int N = 4, M = 3, X = 2;
cout << totalWays(N, M, X) << endl;
return 0;
}
Java
// Java program to count the
// number of ways to form
// arrays of N numbers such
// that the first and last
// numbers are fixed and all
// consecutive numbers are
// distinct
import java.io.*;
class GFG
{
// Returns the total ways to
// form arrays such that every
// consecutive element is
// different and each element
// except the first and last
// can take values from 1 to M
static int totalWays(int N,
int M, int X)
{
// define the dp[][] array
int dp[][] = new int[N + 1][2];
// if the first element is 1
if (X == 1)
{
// there is only one
// way to place a 1
// at the first index
dp[0][0] = 1;
}
else
{
// the value at first index
// needs to be 1, thus there
// is no way to place a
// non-one integer
dp[0][1] = 0;
}
// if the first element was 1
// then at index 1, only non
// one integer can be placed
// thus there are M - 1 ways
// to place a non one integer
// at index 2 and 0 ways to
// place a 1 at the 2nd index
if (X == 1)
{
dp[1][0] = 0;
dp[1][1] = M - 1;
}
// Else there is one way to
// place a one at index 2
// and if a non one needs to
// be placed here, there are
// (M - 2) options, i.e neither
// the element at this index
// should be 1, neither should
// it be equal to the previous
// element
else
{
dp[1][0] = 1;
dp[1][1] = (M - 2);
}
// Build the dp array
// in bottom up manner
for (int i = 2; i < N; i++)
{
// f(i, one) = f(i - 1,
// non-one)
dp[i][0] = dp[i - 1][1];
// f(i, non-one) =
// f(i - 1, one) * (M - 1) +
// f(i - 1, non-one) * (M - 2)
dp[i][1] = dp[i - 1][0] * (M - 1) +
dp[i - 1][1] * (M - 2);
}
// last element needs to be
// one, so return dp[n - 1][0]
return dp[N - 1][0];
}
// Driver Code
public static void main (String[] args)
{
int N = 4, M = 3, X = 2;
System.out.println(totalWays(N, M, X));
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 program to count the number of ways # to form arrays of N numbers such that the # first and last numbers are fixed # and all consecutive numbers are distinct # Returns the total ways to form arrays such that # every consecutive element is different and each # element except the first and last can take values # from 1 to M def totalWays(N,M,X): # define the dp[][] array dp = [[0 for i in range(2)] for j in range(N+1)] # if the first element is 1 if (X == 1): # there is only one way to place # a 1 at the first index dp[0][0] = 1 else: # the value at first index needs to be 1, # thus there is no way to place a non-one integer dp[0][1] = 0 # if the first element was 1 then at index 1, # only non one integer can be placed thus # there are M - 1 ways to place a non one integer # at index 2 and 0 ways to place a 1 at the 2nd index if (X == 1): dp[1][0] = 0 dp[1][1] = M - 1 # Else there is one way to place a one at # index 2 and if a non one needs to be placed here, # there are (M - 2) options, i.e # neither the element at this index # should be 1, neither should it be # equal to the previous element else: dp[1][0] = 1 dp[1][1] = (M - 2) # Build the dp array in bottom up manner for i in range(2,N): # f(i, one) = f(i - 1, non-one) dp[i][0] = dp[i - 1][1] # f(i, non-one) = f(i - 1, one) * (M - 1) + # f(i - 1, non-one) * (M - 2) dp[i][1] = dp[i - 1][0] * (M - 1) + dp[i - 1][1] * (M - 2) # last element needs to be one, so return dp[n - 1][0] return dp[N - 1][0] # Driver Code if __name__ == '__main__': N = 4 M = 3 X = 2 print(totalWays(N, M, X)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to count the
// number of ways to form
// arrays of N numbers such
// that the first and last
// numbers are fixed and all
// consecutive numbers are
// distinct
using System;
class GFG
{
// Returns the total ways to
// form arrays such that every
// consecutive element is
// different and each element
// except the first and last
// can take values from 1 to M
static int totalWays(int N,
int M, int X)
{
// define the dp[][] array
int [,]dp = new int[N + 1, 2];
// if the first element is 1
if (X == 1)
{
// there is only one
// way to place a 1
// at the first index
dp[0, 0] = 1;
}
else
{
// the value at first index
// needs to be 1, thus there
// is no way to place a
// non-one integer
dp[0, 1] = 0;
}
// if the first element was 1
// then at index 1, only non
// one integer can be placed
// thus there are M - 1 ways
// to place a non one integer
// at index 2 and 0 ways to
// place a 1 at the 2nd index
if (X == 1)
{
dp[1, 0] = 0;
dp[1, 1] = M - 1;
}
// Else there is one way to
// place a one at index 2
// and if a non one needs to
// be placed here, there are
// (M - 2) options, i.e neither
// the element at this index
// should be 1, neither should
// it be equal to the previous
// element
else
{
dp[1, 0] = 1;
dp[1, 1] = (M - 2);
}
// Build the dp array
// in bottom up manner
for (int i = 2; i < N; i++)
{
// f(i, one) = f(i - 1,
// non-one)
dp[i, 0] = dp[i - 1, 1];
// f(i, non-one) =
// f(i - 1, one) * (M - 1) +
// f(i - 1, non-one) * (M - 2)
dp[i, 1] = dp[i - 1, 0] * (M - 1) +
dp[i - 1, 1] * (M - 2);
}
// last element needs to be
// one, so return dp[n - 1][0]
return dp[N - 1, 0];
}
// Driver Code
public static void Main ()
{
int N = 4, M = 3, X = 2;
Console.WriteLine(totalWays(N, M, X));
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP program to count the
// number of ways to form
// arrays of N numbers such
// that the first and last
// numbers are fixed and all
// consecutive numbers are distinct
// Returns the total ways to
// form arrays such that every
// consecutive element is
// different and each element
// except the first and last
// can take values from 1 to M
function totalWays($N, $M, $X)
{
// define the dp[][] array
$dp = array(array());
// if the first element is 1
if ($X == 1)
{
// there is only one
// way to place a 1
// at the first index
$dp[0][0] = 1;
}
else
{
// the value at first
// index needs to be 1,
// thus there is no way
// to place a non-one integer
$dp[0][1] = 0;
}
// if the first element was
// 1 then at index 1, only
// non one integer can be
// placed thus there are M - 1
// ways to place a non one
// integer at index 2 and 0 ways
// to place a 1 at the 2nd index
if ($X == 1)
{
$dp[1][0] = 0;
$dp[1][1] = $M - 1;
}
// Else there is one way
// to place a one at index
// 2 and if a non one needs
// to be placed here, there
// are (M - 2) options, i.e
// neither the element at
// this index should be 1,
// neither should it be equal
// to the previous element
else
{
$dp[1][0] = 1;
$dp[1][1] = ($M - 2);
}
// Build the dp array
// in bottom up manner
for ($i = 2; $i <$N; $i++)
{
// f(i, one) =
// f(i - 1, non-one)
$dp[$i][0] = $dp[$i - 1][1];
// f(i, non-one) =
// f(i - 1, one) * (M - 1) +
// f(i - 1, non-one) * (M - 2)
$dp[$i][1] = $dp[$i - 1][0] *
($M - 1) +
$dp[$i - 1][1] *
($M - 2);
}
// last element needs to
// be one, so return dp[n - 1][0]
return $dp[$N - 1][0];
}
// Driver Code
$N = 4; $M = 3; $X = 2;
echo totalWays($N, $M, $X);
// This code is contributed
// by anuj_67.
?>
Javascript
<script>
// Javascript program to count the
// number of ways to form
// arrays of N numbers such
// that the first and last
// numbers are fixed and all
// consecutive numbers are
// distinct
// Returns the total ways to
// form arrays such that every
// consecutive element is
// different and each element
// except the first and last
// can take values from 1 to M
function totalWays(N, M, X)
{
// define the dp[][] array
let dp = new Array(N + 1);
for(let i = 0; i < N + 1; i++)
{
dp[i] = new Array(2);
for(let j = 0; j < 2; j++)
{
dp[i][j] = 0;
}
}
// if the first element is 1
if (X == 1)
{
// there is only one
// way to place a 1
// at the first index
dp[0][0] = 1;
}
else
{
// the value at first index
// needs to be 1, thus there
// is no way to place a
// non-one integer
dp[0][1] = 0;
}
// if the first element was 1
// then at index 1, only non
// one integer can be placed
// thus there are M - 1 ways
// to place a non one integer
// at index 2 and 0 ways to
// place a 1 at the 2nd index
if (X == 1)
{
dp[1][0] = 0;
dp[1][1] = M - 1;
}
// Else there is one way to
// place a one at index 2
// and if a non one needs to
// be placed here, there are
// (M - 2) options, i.e neither
// the element at this index
// should be 1, neither should
// it be equal to the previous
// element
else
{
dp[1][0] = 1;
dp[1][1] = (M - 2);
}
// Build the dp array
// in bottom up manner
for (let i = 2; i < N; i++)
{
// f(i, one) = f(i - 1,
// non-one)
dp[i][0] = dp[i - 1][1];
// f(i, non-one) =
// f(i - 1, one) * (M - 1) +
// f(i - 1, non-one) * (M - 2)
dp[i][1] = dp[i - 1][0] * (M - 1) +
dp[i - 1][1] * (M - 2);
}
// last element needs to be
// one, so return dp[n - 1][0]
return dp[N - 1][0];
}
let N = 4, M = 3, X = 2;
document.write(totalWays(N, M, X));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
3
Complejidad de tiempo: O(N), donde N es el tamaño de la array