FairTournament | Topcoder Archive

Problem Statement

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 p₁ in first place (ranking 1), participant p₂ in second place (ranking 2), ..., participant p_n 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-p_i|<=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.

Definition

Class:: FairTournament
Method:: countPermutations
Parameters:: int, int
Returns:: String
Method signature:: String countPermutations(int n, int k)
(be sure your method is public)

Constraints

n will be between 1 and 100, inclusive.
k will be between 1 and 6, inclusive.

Examples

```
3
```
```
1
```
```
Returns: "3"
```
Rankings "1,2,3", "2,1,3" and "1,3,2" are 1-fair, while "2,3,1", "3,1,2" and "3,2,1" are not.
```
3
```
```
2
```
```
Returns: "6"
```
```
10
```
```
3
```
```
Returns: "19708"
```
```
100
```
```
1
```
```
Returns: "573147844013817084101"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.