Consider a tournament with n participants, numbered 1 to n in decreasing order by strength. The outcome of the tournament is a ranking of all the participants: participant p1 in first place (ranking 1), participant p2 in second place (ranking 2), ..., participant pn in last place (ranking n). It can be easily seen that p is a permutation.
An outcome of the tournament is called k-fair if every participant gets a ranking that differs from his number by at most k. In other words, p is a permutation where the following condition holds for all i: |i-pi|<=k.
Given an int n and an int k, return the number of different possible k-fair outcomes for a n-player tournament. The return value must be a String with no extra leading zeroes.
|