B. Разбиения на множества

Codeforces

IDCF10026B

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Вам даны два числа n и k, нужно вывести все разбиения n элементного множества на k множеств. Строго следуйте формату выходных данных при выводе разбиений. В первой строке записаны два целых числа n и k (1 ≤ k ≤ n ≤ 11). Выведите все разбиения в лексикографическом порядке. Элементы в множествах разбиения сортируйте в порядке возрастания. Сами множества в разбиениях сортируйте в лексикографическом порядке. Не выводите никаких лишних пробелов, строго следуйте формату, указанному в тестовых примерах. ## Входные Данные В первой строке записаны два целых числа n и k (1 ≤ k ≤ n ≤ 11). ## Выходные Данные Выведите все разбиения в лексикографическом порядке. Элементы в множествах разбиения сортируйте в порядке возрастания. Сами множества в разбиениях сортируйте в лексикографическом порядке. Не выводите никаких лишних пробелов, строго следуйте формату, указанному в тестовых примерах. ## Примеры Входные данные1 1Выходные данные[1]Входные данные3 2Выходные данные[1][2,3][1,2][3][1,3][2]Входные данные4 3Выходные данные[1][2][3,4][1][2,3][4][1][2,4][3][1,2][3][4][1,3][2][4][1,4][2][3]Входные данные5 3Выходные данные[1][2][3,4,5][1][2,3][4,5][1][2,3,4][5][1][2,3,5][4][1][2,4][3,5][1][2,4,5][3][1][2,5][3,4][1,2][3][4,5][1,2][3,4][5][1,2][3,5][4][1,2,3][4][5][1,2,4][3][5][1,2,5][3][4][1,3][2][4,5][1,3][2,4][5][1,3][2,5][4][1,3,4][2][5][1,3,5][2][4][1,4][2][3,5][1,4][2,3][5][1,4][2,5][3][1,4,5][2][3][1,5][2][3,4][1,5][2,3][4][1,5][2,4][3] [samples]

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 1 \leq k \leq n \leq 11 $. Let $ U = \{1, 2, \dots, n\} $. A *partition* of $ U $ into $ k $ non-empty subsets is a collection $ \mathcal{P} = \{P_1, P_2, \dots, P_k\} $ such that: - $ \bigcup_{i=1}^k P_i = U $, - $ P_i \cap P_j = \emptyset $ for all $ i \neq j $, - $ P_i \neq \emptyset $ for all $ i $. **Constraints** $ 1 \leq k \leq n \leq 11 $ **Objective** Generate all partitions of $ U $ into exactly $ k $ non-empty subsets, such that: 1. Each subset $ P_i $ is sorted in ascending order. 2. The partition $ \mathcal{P} = \{P_1, \dots, P_k\} $ is sorted lexicographically by the sorted subsets (i.e., compare first elements, then next, etc.). 3. Output all such partitions in lexicographic order, with subsets separated by spaces and elements within subsets by commas, no extra spaces.

API Response (JSON)

{
  "problem": {
    "name": "B. Разбиения на множества",
    "description": {
      "content": "Вам даны два числа n и k, нужно вывести все разбиения n элементного множества на k множеств. Строго следуйте формату выходных данных при выводе разбиений. В первой строке записаны два целых числа n и",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10026B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Вам даны два числа n и k, нужно вывести все разбиения n элементного множества на k множеств. Строго следуйте формату выходных данных при выводе разбиений.\n\nВ первой строке записаны два целых числа n и...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n \\leq 11 $.  \nLet $ U = \\{1, 2, \\dots, n\\} $.  \nA *partition* of $ U $ into $ k $ non-empty subsets is a collection $ \\mathcal{P} = ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments