Количество способов распределить N предметов среди 3 человек, при этом один человек получит максимум

Опубликовано: 1 Января, 2022

Учитывая целое число N , задача состоит в том, чтобы найти общее количество способов распределить N между 3 людьми таким образом, чтобы:

  • Ровно один человек получает максимальное количество предметов среди всех 3 человек.
  • Каждому человеку достается минимум 1 предмет.

Примеры:

Input: N = 5 
Output:
Explanation: 
3 way distribute the item among 3 people are {1, 1, 3}, {1, 3, 1} and {3, 1, 1}. 
Distributions like {1, 2, 2} or {2, 1, 2} are not valid as two persons are getting the maximum.
Input: N = 10 
Output: 33 
Explanation: 
For the Input N = 10 there are 33 ways of distribution. 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:
Чтобы решить указанную выше проблему, мы должны заметить, что если N <4 , то такое распределение невозможно.
Для всех значений N ≥ 4 выполните следующие действия для решения проблемы:

  • Общее количество способов распределить N предметов среди 3 человек равно (N - 1) * (N - 2) / 2 .
  • Инициализируйте переменную s = 0, в которой хранится количество случаев, когда распределение невозможно.
  • Итерировать два вложенных цикла, где i находится в диапазоне от [2, N - 3], а от j - до i :
    • Для каждой итерации проверьте, если N = 2 * i + j , то есть 2 человека могут получить максимальное количество элементов
    • Если это так, увеличьте s на 1 . Если N делится на 3 , обновите s на 3 * s + 1 . В противном случае обновите до 3 * s .
  • Наконец, верните ans - s как общее количество способов распределить N элементов между тремя людьми.

Ниже представлена реализация описанного выше подхода:

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 possiblities
// 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 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 possiblities
// 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 possiblities
# 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 possiblities
// 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 possiblities
// 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>
Выход:
 33

Временная сложность: O (N 2 )
Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.