Roman Digits
Contest: Codeforces Round 493 (Div. 1)
Difficulty rating: 2000
Tags: brute force, combinatorics, dp, greedy, math

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 format:
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 format:
Output a single integer — the number of distinct integers which can be represented using $$$n$$$ roman digits exactly.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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).

Example input:
1

Example output:
4

Example input:
2

Example output:
10

Editorial:
TL; DR — among all the sequences, select the one, which contains the maximum number of $$$50$$$, in case of tie, select one with largest number of $$$9$$$. Bruteforce all configurations in such way, that each number is counted only in it's "maximum" configuration.
Since the length of sequence is fixed, we can solve problem not for digits $$$\{1, 5, 10, 50\}$$$, but for digits $$$\{0, 4, 9, 49\}$$$.
Let's solve the problem for digits $$$\{0, 4, 9\}$$$ first.
We have a problem that some numbers have many representations. But this, in fact, is easy to deal with — if we have at least nine digits "4" than we can convert them no some number of "9" digits, and fill the rest with zeroes.
In this case, the solution is to bruteforce the number of "4" from $$$0$$$ to $$$min(8, n)$$$, and then from the remaining digits select any arbitrary number of "9", each such choice leads to an unique number.
Let's return to the original problem with $$$\{0, 4, 9, 49\}$$$.
In this case we can also face the situation, when the number of $$$49$$$ can be increased. We need to identify all pairs $$$(x, y)$$$ where $$$x, y \le 50$$$, such that they can be transformed to other pair $$$(x', y')$$$ with detachment of few $$$49$$$.
We can bruteforce all $$$x$$$, $$$y$$$, $$$x'$$$, $$$y'$$$ with four nested for-loops and check, that the sum of first differs from sum of latter by few number of $$$49$$$ removed, in such case we mark the pair $$$(x, y)$$$ as broken.
We can also note, that if some pair is marked as broken, than all "dominating" pairs also marked as broken.
When we discovered which pairs are good we can simply:
———
Another solution: if you examine the solution above precisely, you will notice that starting some reasonable $$$n$$$ (you can easy proof a lowerbound like $$$50$$$ or $$$100$$$, but it is, in fact, $$$12$$$), the function grows linearly.
So if $$$n \le 12$$$, you count the answer in any stupid way, and otherwise, simply approximate it linearly using $$$answer(12)$$$ and $$$answer(13)$$$.