eolymp
bolt
Try our new interface for solving problems
Məsələlər

Roman numerals

Roman numerals

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Roman numbers are based on seven symbols "I", "V", "X", "L", "C", "D" and "M". The "costs" of those symbols are 1,5, 10, 50, 100, 500 and 1000, respectively. To calculate decimal value of a Roman number, we will use the following algorithm:

  1. Find the most significant (the most "expensive") symbol. If there are several such symbols take the leftmost one. Let the found symbol is placed in position i.

  2. Denote as Middle the "cost" of symbol placed in position i.

  3. Calculate the value of Roman number formed by the symbols, standing to the right of i. Denote this value asRight.

  4. Calculate the value of Roman number formed by the numerals, standing to the left of i. Denote this value asLeft.

  5. Let Middle + Right – Left be the value of a Roman number. Obviously, if we use this algorithm, the same number can be written in many ways. For example, the number 19 can be written as "IXX", "XIX", "XVIV", "XVIIII" and so on.

Given decimal number n and Roman number S, you are to find such digits transposition of S, that represents n in Roman notation.

Giriş verilənləri

The first line contains an integer n in decimal notation. The second line contains a number S in Roman notation (–50000n50000, 1length(S)50).

Çıxış verilənləri

The first line of output file should contain the Roman number or word "NO" (without the quotes) if there is no solution.

Nümunə

Giriş verilənləri #1
16
XXVI
Çıxış verilənləri #1
VXXI