F. Мегаломания

Codeforces

IDCF10136F

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Галактическая федерация проводит национальный конкурс на должность самого великого министра. В конкурсе участвуют N министров, каждый из которых оценивается в судьями в баллах в зависимости от степени величия. Участники конкурса распределяются в таблице по местам от 1-го до N-го в порядке убывания набранных баллов. Если какие-то K участников набрали одинаковые баллы, то есть заняли в таблице места X, X + 1, ..., X + K - 1, то всем им назначается место равное X, а следующим свободным местом в таблице становится X + K. Рассмотрим пример из шести участников. Пусть участники 1 и 2 набрали по 10 баллов, участник 3 — 9 баллов, участники 4, 5 и 6 — по 8 баллов. Тогда места в таблице распределятся следующим образом: . Посчитайте, сколько существует различных распределений мест в таблице. Два распределения с одинаковым набором мест, но разными участниками на этих местах, считайте одинаковыми. Единственное число N (1 ≤ N ≤ 50) — количество участников конкурса. Искомое количество различных распределений мест в таблице результатов. В первом тесте места участников могут распределиться так: ; ; ; . Во втором тесте единственное возможное распределение: . ## Входные Данные Единственное число N (1 ≤ N ≤ 50) — количество участников конкурса. ## Выходные Данные Искомое количество различных распределений мест в таблице результатов. ## Примеры Входные данные3Выходные данные4Входные данные1Выходные данные1 ## Примечание В первом тесте места участников могут распределиться так: ; ; ; .Во втором тесте единственное возможное распределение: . [samples]

Let $ N \in \mathbb{Z} $ with $ 1 \leq N \leq 50 $. Let $ P = (p_1, p_2, \dots, p_k) $ be a composition of $ N $, i.e., a sequence of positive integers such that $ \sum_{i=1}^k p_i = N $, where each $ p_i $ represents the size of a group of participants sharing the same score (and thus the same rank). Each such composition corresponds to a distinct ranking distribution under the rule: participants with equal scores receive the same rank, and the next distinct score receives the rank immediately following the last tied position. The number of distinct rank distributions is equal to the number of compositions of $ N $. $$ \boxed{2^{N-1}} $$

API Response (JSON)

{
  "problem": {
    "name": "F. Мегаломания",
    "description": {
      "content": "Галактическая федерация проводит национальный конкурс на должность самого великого министра. В конкурсе участвуют 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": "CF10136F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Галактическая федерация проводит национальный конкурс на должность самого великого министра. В конкурсе участвуют N министров, каждый из которых оценивается в судьями в баллах в зависимости от степени...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ N \\in \\mathbb{Z} $ with $ 1 \\leq N \\leq 50 $.\n\nLet $ P = (p_1, p_2, \\dots, p_k) $ be a composition of $ N $, i.e., a sequence of positive integers such that $ \\sum_{i=1}^k p_i = N $, where each ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments