Problem link : contest practice
Difficulty : Simple
Pre-requisites : basic math
Solution :
If we reformulate the problem, we’ll get the following one: given an integer N, calculate the number of integer vectors (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}) such that:
- a_{i} > 0, for each i, 1 <= i <= 7;
- 2(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6})+a_{7}=N.
Let’s brute-force a_{7}. Then, we’ll have to calculate the number of integer vectors (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}) such that 2(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6})=N-a_{7}=M. Of course, M should be even, otherwise there won’t be any solution.
And now, we use the well-known fact that the number of integer vectors (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}) such that a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}=M/2=K is C(K-1, 5). These numbers can be obtained by the calculation of the first 6 columns of the Pascal triangle.
Setter’s solution: link
Tester’s solution: link