D. Roman Digits

Codeforces

IDCF998D

Time1000ms

Memory256MB

Difficulty—

brute forcecombinatoricsgreedy

English · Original

Chinese · Translation

Formal · Original

Let's introduce a number system which is based on a roman digits. There are digits _I_, _V_, _X_, _L_ which correspond to the numbers $1$, $5$, $10$ and $50$ respectively. The use of other roman digits is not allowed. Numbers in this system are written as a sequence of one or more digits. We define the value of the sequence simply as the sum of digits in it. For example, the number _XXXV_ evaluates to $35$ and the number _IXI_ — to $12$. Pay attention to the difference to the traditional roman system — in our system any sequence of digits is valid, moreover the order of digits doesn't matter, for example _IX_ means $11$, not $9$. One can notice that this system is ambiguous, and some numbers can be written in many different ways. Your goal is to determine how many distinct integers can be represented by **exactly** $n$ roman digits _I_, _V_, _X_, _L_. ## Input The only line of the input file contains a single integer $n$ ($1 \le n \le 10^9$) — the number of roman digits to use. ## Output Output a single integer — the number of distinct integers which can be represented using $n$ roman digits _exactly_. [samples] ## Note In the first sample there are exactly $4$ integers which can be represented — _I_, _V_, _X_ and _L_. In the second sample it is possible to represent integers $2$ (_II_), $6$ (_VI_), $10$ (_VV_), $11$ (_XI_), $15$ (_XV_), $20$ (_XX_), $51$ (_IL_), $55$ (_VL_), $60$ (_XL_) and $100$ (_LL_).

让我们引入一种基于罗马数字的数制。其中数字 _I_、_V_、_X_、_L_ 分别对应数值 $1$、$5$、$10$ 和 $50$。不允许使用其他罗马数字。在此系统中，数字由一个或多个数字组成的序列表示。我们定义该序列的值为其所有数字的数值之和。例如，序列 _XXXV_ 的值为 $35$，序列 _IXI_ 的值为 $12$。请注意，这与传统罗马数字系统不同——在本系统中，任何数字序列都是合法的，且数字的顺序无关紧要。例如，_IX_ 表示 $11$，而非 $9$。可以注意到，该系统存在歧义，某些数字可以用多种不同方式表示。你的目标是确定恰好使用 $n$ 个罗马数字 _I_、_V_、_X_、_L_ 时，能够表示多少个不同的整数。输入文件仅包含一行，一个整数 $n$（$1 lt.eq n lt.eq 10^9$）——表示要使用的罗马数字个数。请输出一个整数——恰好使用 $n$ 个罗马数字能表示的不同整数的个数。在第一个样例中，恰好有 $4$ 个整数可以表示——_I_、_V_、_X_ 和 _L_。在第二个样例中，可以表示的整数有：$2$（_II_）、$6$（_VI_）、$10$（_VV_）、$11$（_XI_）、$15$（_XV_）、$20$（_XX_）、$51$（_IL_）、$55$（_VL_）、$60$（_XL_）和 $100$（_LL_）。 ## Input 输入文件仅包含一行，一个整数 $n$（$1 lt.eq n lt.eq 10^9$）——表示要使用的罗马数字个数。 ## Output 请输出一个整数——恰好使用 $n$ 个罗马数字能表示的不同整数的个数。 [samples] ## Note 在第一个样例中，恰好有 $4$ 个整数可以表示——_I_、_V_、_X_ 和 _L_。在第二个样例中，可以表示的整数有：$2$（_II_）、$6$（_VI_）、$10$（_VV_）、$11$（_XI_）、$15$（_XV_）、$20$（_XX_）、$51$（_IL_）、$55$（_VL_）、$60$（_XL_）和 $100$（_LL_）。

**Definitions** Let the digit values be: - $ d_I = 1 $, - $ d_V = 5 $, - $ d_X = 10 $, - $ d_L = 50 $. Let $ n \in \mathbb{Z}^+ $ be the total number of digits used, with $ 1 \leq n \leq 10^9 $. Let $ a, b, c, d \in \mathbb{Z}_{\geq 0} $ denote the counts of digits I, V, X, L respectively, such that: $$ a + b + c + d = n $$ The value of a sequence is: $$ v = 1 \cdot a + 5 \cdot b + 10 \cdot c + 50 \cdot d $$ **Objective** Compute the number of **distinct** values of $ v $ over all non-negative integer solutions $ (a, b, c, d) $ to $ a + b + c + d = n $. That is, find the cardinality of the set: $$ \left\{ a + 5b + 10c + 50d \,\middle|\, a,b,c,d \in \mathbb{Z}_{\geq 0},\ a + b + c + d = n \right\} $$

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Roman Digits",
    "description": {
      "content": "Let's introduce a number system which is based on a roman digits. There are digits _I_, _V_, _X_, _L_ which correspond to the numbers $1$, $5$, $10$ and $50$ respectively. The use of other roman digit",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF998D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let's introduce a number system which is based on a roman digits. There are digits _I_, _V_, _X_, _L_ which correspond to the numbers $1$, $5$, $10$ and $50$ respectively. The use of other roman digit...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "让我们引入一种基于罗马数字的数制。其中数字 _I_、_V_、_X_、_L_ 分别对应数值 $1$、$5$、$10$ 和 $50$。不允许使用其他罗马数字。\n\n在此系统中，数字由一个或多个数字组成的序列表示。我们定义该序列的值为其所有数字的数值之和。\n\n例如，序列 _XXXV_ 的值为 $35$，序列 _IXI_ 的值为 $12$。\n\n请注意，这与传统罗马数字系统不同——在本系统中，任何数字序列都是...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet the digit values be:  \n- $ d_I = 1 $,  \n- $ d_V = 5 $,  \n- $ d_X = 10 $,  \n- $ d_L = 50 $.  \n\nLet $ n \\in \\mathbb{Z}^+ $ be the total number of digits used, with $ 1 \\leq n \\leq ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments