Количество способов распределить N предметов среди 3 человек, при этом один человек получит максимум
Учитывая целое число N , задача состоит в том, чтобы найти общее количество способов распределить N между 3 людьми таким образом, чтобы:
- Ровно один человек получает максимальное количество предметов среди всех 3 человек.
- Каждому человеку достается минимум 1 предмет.
Примеры:
Input: N = 5
Output: 3
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.
Подход:
Чтобы решить указанную выше проблему, мы должны заметить, что если 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.