DAILY - Editorial

PROBLEM LINKS

Practice
Contest

EXPLANATION

It’s obvious that we can solve the problem for each compartment separately. Let’s find the number of free places in a particular compartment, say Y. If Y > X then our group of friends can’t be placed in this compartment. In the other case the number of ways to choose any X places out of given Y should be added to the answer – in other words, the number of X-combinations of Y elements should be added. This number (let’s call it C(Y,X)) can be calculated in many ways:

  • using the formula C(Y,X) = Y! / ( X! * (Y-X)! ),
  • using the relation C(Y,X) = C(Y-1,X) + C(Y-1,X-1),
  • or even calculating all the required values by hand (both X and Y are very small).

SETTER’S SOLUTION

Can be found here

TESTER’S SOLUTION

Can be found here

note: dont forget to use loop while assigning 0 to array a[] (array that keeps track of empty places at every compartment). dont use memset(a, 0, sizeof(a)), it gave runtime error signal:8 (sigfpe) on my code and it cost me hours to realize that bug.