EUROPEAN ITERATION

 

We know about number systems: The Roman numerals and the alternative place-value system with a given base.

For the purposes of this problem, we limit ourselves to

  • Roman numerals with values up to 3999 MMMCMXCIX
  • "Place value system" numbers having bases from 2 (with possible symbols 0, 1) through 36 (with possible symbols 0, 1, ..., 9, A, ... ,Z)

Consider the following procedure:

  1. Accept a natural number N (in base 10).
  2. If N lies in the closed interval [1,3999], i.e. between 1 and 3999 (both inclusive), convert N to R, its Roman numeral representation; else output N as the result and stop.
  3. Identify the base in which the value of R, now considered to be in "place value system", is least and calculate its value in base 10, replacing N with this value.
  4. Repeat from step 2.

Constraints

1 <= N <= 3999

Input Format

  • A single Integer N.

Output

  • Converted N


Test Case

Example Input

1

Output

45338950

Explanation

The procedure goes as follows in this case:

  1. Accept N = 1.
  2. Since 1 lies in [1,3999], covert it to Roman R = I
  3. The least value of I (in bases 19 and above) is 18 in base 10. Hence N = 18.
  4. Repeating step 2, since 18 lies in [1,3999], convert it to R = XVIII
  5. The least value of XVIII (in base 34) is
    33*34^4+31*34^3+18*34^2+18*34+18 or N = 45338950
  6. Repeating step 2, since 45338950 lies outside [1,3999] output 45338950 and stop.

Here's how the conversions go:

Input = 1 => I => 18 => XVIII => 45338950 = Output



Solution:


def roman(n):  #gets the roman number

    r=''

    num=[1,4,5,9,10,40,50,90,100,400,500,900,1000]

    sym=['I','IV','V','IX','X','XL','L','XC','C','CD','D','CM','M']

    i=12

    while(n):

        d=int(n/num[i])

        n=n%num[i]

        while(d):

            r=r+sym[i]

            d=d-1

        i=i-1

    return(r)

def dec(rom,base):    #calculates the decimal value of the roman numeral with given base

    return(int(rom,base))


n=int(input())

ch='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'

while(n>=1 and n<=3999):

    p=roman(n)

    b=ch.find(max(p))+1      #finds the base of the roman numeral

    n=dec(p,b)

print(n)

Comments

Post a Comment

Popular posts from this blog

Efficient Janitor

  The janitor of a high school is insanely efficient. By the end of the day, all of the waster from the trash cans in the school has been shifted into plastic bags which can carry waster weighting between 1.01 pounds and 3.00 pounds. All of the plastic bags must be dumped into the trash cans outside the school. The janitor can carry at most 3.00 pounds at once. One trip is described as selecting a few bags which together don't weigh more than 3.00 pounds, dumping them in the outdoor trash can and returning to the school. The janitor wants to make minimum number of trips to the outdoor trash can. Given the number of plastic bags, n and the weights of each bag, determine the minimum number of trips if the janitor selects bags in the optimal way. For example, given  n=5 , plastic bags weighing weights  [1.01, 1.99, 2.5, 1.5, 1.01] , the janitor can carry all of the trash out in 3 trips:  [1.01+1.99, 2.5, 1.5+1.01] Constraints 1 <= n <= 1000 1.01 <= weight <=...
Read more

Right Arrow Pattern

Write a program to print the Right Arrow Pattern. Input Format: Take an input Integer which is from stdin. Output Format: print Right Arrow pattern Example Input: 5 Output: ***** **** *** ** * ** *** **** ***** SOLUTION: n=int(input()) for i in range(n):     for j in range(2*i):      #for spaces as each i th row has 2*i spaces         print(" ",end="")     for k in range(n-i):     #for stars as each i th row has n-i stars         print("*",end="")          print("")                     # half pattern is completed here for i in range(2,n+1):     #range started from 2 as the single star at middle is already                                         ...
Read more

X Pattern

  Write a program to take String if the length of String is odd print X pattern otherwise print INVALID. Input Format: Take a String as input from stdin. Output Format: print the desired Pattern or INVALID. Example Input: edyst Output: e t d s y d s e t SOLUTION: s=input() l=len(s) if(l%2 != 0): for i in range(0,l): j=l-i-1 for k in range(0,l): if(k==i or k==j): print(s[k],end="") else: print(end=" ") print("") else: print("INVALID")
Read more