G. Count Permutations

Codeforces

IDCF10058G

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Given N and K, count number of permutations of [1, 2, 3...N] in which no two adjacent elements differ by more than K. For example, permutation [4, 1, 2, 3] cannot be counted for . First line contains T(1 ≤ T ≤ 10), the number of test cases. Each test case consists of N(1 ≤ N ≤ 15) and K(0 ≤ N) in single line. For each test case print the required answer in one line. Example case 1. All permutations are valid. Example case 2. Permutations [1, 2, 3, [3, 2, 1]] are counted. ## Input First line contains T(1 ≤ T ≤ 10), the number of test cases. Each test case consists of N(1 ≤ N ≤ 15) and K(0 ≤ N) in single line. ## Output For each test case print the required answer in one line. [samples] ## Note Example case 1. All permutations are valid.Example case 2. Permutations [1, 2, 3, [3, 2, 1]] are counted.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ i \in \{1, \dots, T\} $: - $ N_i \in \mathbb{Z} $ denotes the size of the set $ \{1, 2, \dots, N_i\} $. - $ K_i \in \mathbb{Z} $ denotes the maximum allowed absolute difference between adjacent elements. Let $ \mathcal{P}_{N_i} $ be the set of all permutations of $ \{1, 2, \dots, N_i\} $. **Constraints** 1. $ 1 \leq T \leq 10 $ 2. For each test case $ i $: - $ 1 \leq N_i \leq 15 $ - $ 0 \leq K_i \leq N_i - 1 $ **Objective** For each test case $ i $, compute the number of permutations $ \pi \in \mathcal{P}_{N_i} $ such that for all $ j \in \{1, 2, \dots, N_i - 1\} $: $$ |\pi(j+1) - \pi(j)| \leq K_i $$

API Response (JSON)

{
  "problem": {
    "name": "G. Count Permutations",
    "description": {
      "content": "Given N and K, count number of permutations of [1, 2, 3...N] in which no two adjacent elements differ by more than K. For example, permutation [4, 1, 2, 3] cannot be counted for . First line contains",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10058G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given N and K, count number of permutations of [1, 2, 3...N] in which no two adjacent elements differ by more than K. For example, permutation [4, 1, 2, 3] cannot be counted for .\n\nFirst line contains...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ i \\in \\{1, \\dots, T\\} $:  \n- $ N_i \\in \\mathbb{Z} $ denotes the size of the set $ \\{1, 2, \\dots, N_i\\} $....",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments