Dado un número entero N , la tarea es encontrar el número total de formas de distribuir N entre 3 personas tal que:
- Exactamente una persona obtiene el número máximo de artículos entre las 3 personas.
- Cada persona recibe al menos 1 artículo.
Ejemplos:
Entrada: N = 5
Salida: 3
Explicación:
Las 3 formas de distribuir el artículo entre 3 personas son {1, 1, 3}, {1, 3, 1} y {3, 1, 1}.
Distribuciones como {1, 2, 2} o {2, 1, 2} no son válidas ya que dos personas obtienen el máximo.
Entrada: N = 10
Salida: 33
Explicación:
Para la Entrada N = 10 hay 33 formas de distribución.
Enfoque:
Para resolver el problema mencionado anteriormente, debemos observar que si N < 4 , entonces tal distribución no es posible.
Para todos los valores de N ≥ 4 , siga los pasos para resolver el problema:
- El número total de formas de distribuir N artículos entre 3 personas está dado por (N – 1) * (N – 2) / 2 .
- Inicialice una variable s = 0 que almacena el recuento de formas en que la distribución no es posible.
- Iterar dos bucles anidados, donde i varía entre [2, N – 3] y j hasta i :
- Para cada iteración, verifique si N = 2 * i + j , es decir, 2 personas pueden recibir la cantidad máxima de elementos
- Si es así, entonces incremente s en 1 . Si N es divisible por 3 , actualice s por 3 * s + 1 . De lo contrario, actualice a 3 * s .
- Finalmente, devuelva ans – s como el número total de formas de distribuir N elementos entre tres personas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number
// of ways to distribute N item
// among three people such
// that one person always gets
// the maximum value
#include <bits/stdc++.h>
using namespace std;
// Function to find the number
// of ways to distribute N
// items among 3 people
int countWays(int N)
{
// No distribution
// possible
if (N < 4)
return 0;
// Total number of ways to
// distribute N items
// among 3 people
int ans = ((N - 1) * (N
- 2))
/ 2;
// Store the number of
// distributions which
// are not possible
int s = 0;
for (int i = 2; i <= N - 3;
i++) {
for (int j = 1; j < i;
j++) {
// Count possibilities
// of two persons
// receiving the
// maximum
if (N == 2 * i + j)
s++;
}
}
// If N is divisible by 3
if (N % 3 == 0)
s = 3 * s + 1;
else
s = 3 * s;
// Return the final
// count of ways
// to distribute
return ans - s;
}
// Driver Code
int main()
{
int N = 10;
cout << countWays(N);
return 0;
}
Java
// Java program to find the number
// of ways to distribute N item
// among three people such
// that one person always gets
// the maximum value
class GFG{
// Function to find the number
// of ways to distribute N
// items among 3 people
static int countWays(int N)
{
// No distribution
// possible
if (N < 4)
return 0;
// Total number of ways to
// distribute N items
// among 3 people
int ans = ((N - 1) * (N - 2)) / 2;
// Store the number of
// distributions which
// are not possible
int s = 0;
for (int i = 2; i <= N - 3; i++)
{
for (int j = 1; j < i; j++)
{
// Count possibilities
// of two persons
// receiving the
// maximum
if (N == 2 * i + j)
s++;
}
}
// If N is divisible by 3
if (N % 3 == 0)
s = 3 * s + 1;
else
s = 3 * s;
// Return the final
// count of ways
// to distribute
return ans - s;
}
// Driver Code
public static void main(String[] args)
{
int N = 10;
System.out.println(countWays(N));
}
}
// This code is contributed by rock_cool
Python3
# Python3 program to find the number # of ways to distribute N item # among three people such # that one person always gets # the maximum value # Function to find the number # of ways to distribute N # items among 3 people def countWays(N): # No distribution # possible if (N < 4): return 0 # Total number of ways to # distribute N items # among 3 people ans = ((N - 1) * (N - 2)) // 2 # Store the number of # distributions which # are not possible s = 0 for i in range( 2, N - 2, 1): for j in range( 1, i, 1): # Count possibilities # of two persons # receiving the # maximum if (N == 2 * i + j): s += 1 # If N is divisible by 3 if (N % 3 == 0): s = 3 * s + 1 else: s = 3 * s # Return the final # count of ways # to distribute return ans - s # Driver Code N = 10 print (countWays(N)) # This code is contributed by sanjoy_62
C#
// C# program to find the number
// of ways to distribute N item
// among three people such
// that one person always gets
// the maximum value
using System;
class GFG{
// Function to find the number
// of ways to distribute N
// items among 3 people
static int countWays(int N)
{
// No distribution
// possible
if (N < 4)
return 0;
// Total number of ways to
// distribute N items
// among 3 people
int ans = ((N - 1) * (N - 2)) / 2;
// Store the number of
// distributions which
// are not possible
int s = 0;
for (int i = 2; i <= N - 3; i++)
{
for (int j = 1; j < i; j++)
{
// Count possibilities
// of two persons
// receiving the
// maximum
if (N == 2 * i + j)
s++;
}
}
// If N is divisible by 3
if (N % 3 == 0)
s = 3 * s + 1;
else
s = 3 * s;
// Return the final
// count of ways
// to distribute
return ans - s;
}
// Driver Code
public static void Main()
{
int N = 10;
Console.Write(countWays(N));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript program to find the number
// of ways to distribute N item
// among three people such
// that one person always gets
// the maximum value
// Function to find the number
// of ways to distribute N
// items among 3 people
function countWays(N)
{
// No distribution
// possible
if (N < 4)
return 0;
// Total number of ways to
// distribute N items
// among 3 people
let ans = ((N - 1) * (N - 2)) / 2;
// Store the number of
// distributions which
// are not possible
let s = 0;
for (let i = 2; i <= N - 3; i++) {
for (let j = 1; j < i; j++) {
// Count possibilities
// of two persons
// receiving the
// maximum
if (N == 2 * i + j)
s++;
}
}
// If N is divisible by 3
if (N % 3 == 0)
s = 3 * s + 1;
else
s = 3 * s;
// Return the final
// count of ways
// to distribute
return ans - s;
}
let N = 10;
document.write(countWays(N));
</script>
Producción:
33
Complejidad temporal: O(N 2 )
Espacio auxiliar: O(1)