A. Крепость

Codeforces

IDCF10026A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

У вас есть n детских игрушечных кубиков. Вы хотите построить из них крепость. Крепость — это последовательность из башен, составленных из кубиков. При этом в каждой башне может быть только нечетное число кубиков. Ваша задача — посчитать количество крепостей, которые можно составить ровно из n кубиков. Две крепости считаются различными, если существует такое i, что количество кубиков в i-ой слева башне первой крепости отличается от количества кубиков в i-ой слева башне второй крепости. В первой строке записано целое число n (1 ≤ n ≤ 70). Выведите количество крепостей, которые можно составить ровно из n кубиков. Обратите внимание, что ответ может не помещаться в 32-битный знаковый тип. ## Входные Данные В первой строке записано целое число n (1 ≤ n ≤ 70). ## Выходные Данные Выведите количество крепостей, которые можно составить ровно из n кубиков.Обратите внимание, что ответ может не помещаться в 32-битный знаковый тип. ## Примеры Входные данные1Выходные данные1Входные данные2Выходные данные1Входные данные4Выходные данные3Входные данные10Выходные данные55 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the total number of cubes, with $ 1 \leq n \leq 70 $. Let a *fort* be a sequence of towers $ (t_1, t_2, \dots, t_k) $, where each $ t_i $ is an odd positive integer, and $ \sum_{i=1}^k t_i = n $. **Constraints** Each tower height $ t_i \in \{1, 3, 5, \dots\} $, i.e., $ t_i \equiv 1 \pmod{2} $ and $ t_i \geq 1 $. **Objective** Compute the number of compositions of $ n $ into positive odd integers. That is, count the number of sequences $ (t_1, t_2, \dots, t_k) $, $ k \geq 1 $, such that: $$ \sum_{i=1}^k t_i = n \quad \text{and} \quad t_i \in 2\mathbb{Z}^+ - 1 \quad \forall i. $$

API Response (JSON)

{
  "problem": {
    "name": "A. Крепость",
    "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": "CF10026A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "У вас есть n детских игрушечных кубиков. Вы хотите построить из них крепость.\n\nКрепость — это последовательность из башен, составленных из кубиков. При этом в каждой башне может быть только нечетное ч...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the total number of cubes, with $ 1 \\leq n \\leq 70 $.  \n\nLet a *fort* be a sequence of towers $ (t_1, t_2, \\dots, t_k) $, where each $ t_i $ is an odd pos...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments