Story
On Groundhog Day, Xorin decided to take all N of his TakeOff friends on a golf course. He then divides them into groups of 4 players, any way he wants, respecting the following criteria:
- Players' order inside a group is not relevant (groups are defined by the set of players contained, not by their order). For simplicity, we will consider that a group is an ordered set of size 4.
- The order of the groups is also not relevant (i.e. configurations 1234/5678 and 5678/1234 are identical, and should not be counted twice).
However, in his attempt to stay true to the movie plot (as any Bill Murray fan would), Xorin reenacted this scenario for R consecutive days, choosing a configuration each day (not necessarily a new one).
Problem
What is the total number of ways Xorin can split the N golfers in groups of 4, over the course of R days?
The result can be a very large number. Instead of calculating the actual value, you should write a formula that, when evaluated, returns the number of possibilities.
Input
The input file contains two numbers separated by one space: N (the number of players) and R (the number of days).
Output
A formula that, when evaluated, returns the number of ways of dividing all golfers into N / 4 groups, over R days. The formula may only contain the characters 0123456789()*/+-^. No spaces are allowed. The formula may be followed by an optional newline.
Constraints
- N is divisible by 4.
- 4 ≤ N ≤ 60
- 1 ≤ R ≤ 30
- The output (including the optional final newline) must be at most 200 characters long.
- a/b denotes the quotient of integer division. a^b is exponentiation.
Sample
| Input | Output |
|---|---|
| 8 2 | 5^3*8+15^2 |
| 8 1 | 7*5 |
In the 2nd example, the following are the 35 valid combinations:
- 1234/5678
- 1235/4567
- 1236/4578
- 1237/4568
- 1238/4567
- 1245/3678
- 1246/3578
- 1247/3568
- 1248/3567
- 1256/3478
- 1257/3468
- 1258/3467
- 1267/3458
- 1268/3457
- 1278/3456
- 1345/2678
- 1346/2578
- 1347/2568
- 1348/2567
- 1356/2478
- 1357/2468
- 1358/2467
- 1367/2458
- 1368/2457
- 1378/2456
- 1456/2378
- 1457/2368
- 1458/2367
- 1467/2358
- 1468/2357
- 1478/2356
- 1567/2348
- 1568/2347
- 1578/2346
- 1678/2345
Let d[i] be the number of ways we can split i*4 golfers into groups of 4 golfers each.
We have d[1] = 1 and d[i] = d[i - 1] * choose(i * 4, 4) / i, where choose(x, y) is the binomial coefficient, calculated using the formula: choose(x, y) = x! / y! / (x-y)!.
When going from d[i-1] to d[i], we can pick any 4 golfers to be in the newly formed group (choose(i * 4, 4)). However, we need to discount repetitions, thus need to divide by the number of groups i.
The final solution is d[N / 4]R.
Perl solution (Marius Gavrilescu)
In languages with builtin big numbers, we can compute d[N / 4] directly. Since d[N / 4]R has more than 200 digits, we will print d[N / 4]^R.1 #!/usr/bin/perl 2 use v5.14; 3 use warnings; 4 use bigint; 5 6 my ($n, $r) = split ' ', <>; 7 my $ans = 1; 8 $ans *= (4 * $_)->bnok(4) / $_ for 2 .. $n / 4; 9 say "$ans^$r";
C solution (Marius Gavrilescu)
We know that choose(K,4)=K!/(K-4)!/4! = K*(K-1)*(K-2)*(K-3)/24.
By expanding the definition of d we get d[N/4] = N*(N-1)*(N-2)*(N-3) / 24 * (N-4)*(N-5)*(N-6)*(N-7) / 24 * ... * 4*3*2*1 / 24 / (N/4)! which is equal to N! / (N/4)! / 24^(N/4).
Thus, the answer is (N*(N-1)*...*(N/4+1)/24^K)^R.
1 #include <stdio.h> 2 3 int main(void) { 4 int n, k; 5 scanf("%d%d", &n, &k); 6 7 printf("(%d", n); 8 for(int i = n - 1 ; i > n / 4 ; i--) 9 printf("*%d", i); 10 printf("/24^%d)^%d\n", n / 4, k); 11 return 0; 12 }
C++ solution (Gabriel Inelus)
We denote the number of ways to split N golfers into groups of 4 each when the order is important by the function F(x) = x choose 4 * F(x-4). To avoid the repetitions we can divide the answer by (x/4)! and then raise it to the power R. It's easy to observe that x choose 4 = x*(x-1)*(x-2)*(x-3)/24, which is less than 231, thus we can give a straight forward recursive implementation of F(N).1 #include <bits/stdc++.h> 2 using namespace std; 3 4 void F(int k){ 5 cout << k*(k-1)*(k-2)*(k-3) / 24; 6 if(k == 4) return; 7 cout << "*"; 8 F(k - 4); 9 } 10 11 int main() 12 { 13 int N,R; 14 cin >> N >> R; 15 cout << "(("; F(N); cout << ")"; 16 for(int i = 2; i <= N/4; ++i) 17 cout << "/" << i; 18 cout << ")^" << R; 19 return 0; 20 }
