ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Junior Contest October'2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Pseudo-Roman Number

Time limit: 1.0 second
Memory limit: 64 MB
We can’t say that all the programmers are absent-minded people but it is usual to some of them… Once Artemy Sidorovich tested his program. Particularly it was to be able to define a day of the week by the date. Artemy Sidorovich inputted "October 11, 2003" and got the answer "Saturday". "Aha!" — thought Artmy Sidorovich and started to search for a mistake (the calendar that was hung in his room said that October 11th, 2003 is Monday).
After an hour Artemy Sidorovich glances up and saw big digits in the calendar: 1999. Swearing under his breath and promising to through away the old calendar he looked at the clock. The hour hand was at the mark IIII. The day was almost finished.
— It’s interesting, — thought Artermy Sidorovich, — I’ve seen many times that the number 4 is written down by the Roman numerals as IV. It turns out that a decimal number can’t be represented by the Roman number unambiguously. He looked again at the calendar and thought so:
— Let the numbers 1, 5, 10, 50, 100, 500, 1000 be denoted by the Roman numerals I, V, X, L, C, D, M. Then the number 1999 may be represented as MDCCCCLXXXXVIIII or simply MIM. Or may be MCMXCIX. It’s evident that the record MIM is the shortest. But which one is correct?
In order to adjust differences Artemy Sidorovich decided:
We'll call a pseoudo-roman number the sequence of numerals: A1A2An, where:
  1. Every numeral denotes on of the numbers 1, 5, 10, 50, 100, 500, 1000, … The different digits correspond to the different numbers. Let’s denote the number according to the numeral A as [A].
  2. There may be not more than 3 identical numerals one after another, if the numerals denote a power of 10 and not more than 2 identical numerals otherwise.
  3. In the number A1A2An the following two statements are correct:
    • [Ai] ≥ [Ai+1] or
    • ([Ai] < [Ai+1] ≤ 10[Ai] and [Ai] = 10k), where i < n.
  4. Before a numeral there may not be more than one lower numeral.
  5. [Ai] ≥ [Ai+1] ≥ [Ai+2], or [Ai+2] < [Ai] < [Ai+1], or [Ai+1] < [Ai+2] ≤ [Ai], where i < n − 1
  6. A1 = [A1].
         A1A2An = A2An − [A1], if [A1] < [A2].
         A1A2An = A2An + [A1], if [A1] > [A2].
Then the number 4 will be written down as IV, and not as IIII (according to the rule 2). The number 1999 will be written down as MCMXCIX. It’s not the shortest way but every number is represented unambiguously.

Input

There is a decimal integer number N, 1 ≤ N ≤ 102003.

Output

Output the integer K — that is an amount of numerals in pseudo-roman notation of the number N.

Sample

inputoutput
1939
8

Notes

1939 = MCMXXXIX
Problem Author: Alexander Ipatov
Problem Source: Open collegiate programming contest for high school children of the Sverdlovsk region, October 11, 2003
To submit the solution for this problem go to the Problem set: 1262. Pseudo-Roman Number