import java.util.*;
public class Solution 
{
    public static void main (String []args)
    {
        System.out.println(decimalToRoman(49));
    }
    
    //NUMERALS numeral = NUMERAL.1000.value();

    static int remainingNumber;

    //this will be remainder once it passes through the switch statement


    public static String decimalToRoman(int num) 
    
    {
        int numberFoundMatches=0;
        boolean foundMatch=false;
        int counter=0;
        String conversion="";
        int currentNumeral=0;
        int match=0;
        char fourInRowNumeral=' ';
        char incorrectPredecessor=' ';
        String successor="";

        String [] nextHighest = new String[8];
        nextHighest[0] = "I=>V";
        nextHighest[1] = "V=>X";
        nextHighest[2] = "X=>L";
        nextHighest[3] = "L=>C";
        nextHighest[4] = "C=>D";
        nextHighest[5] = "D=>M";


        //M=1000, C=100, D=500, L=50, X=10,  V=5,  I=1



        //these have to be descending order

   

        //return "test";

        //I will first attempt this from recursive perspective..
        //using a class level variable

        //This should much easier than conversion numeral => decimal number

        //we only need to worry about the valid subtractive notations (as a pair)
        
        //do not need to worry about adjacent subtractive notation being in the same range

        //not relevant
        //i.e  IX XC
             //range (1-10)  (range 10-100)

        // these are the valid combinations....

        //String IV =  "IV";
        //String IX =  "IX";
        //String XL =  "XL";
        //String XC =  "XC";
        //String CD=   "CD"; 
        //String CM=   "CM";

        //Also need to consider this rule
        //The xcletters V, L, and D are not repeated.


        //I will work this example using the following two numbers
        //27  and also 19
        //both will bring their own challenges

       
            //main structure of code
            if (num==0)
            {
                return conversion;
            }
                  
            else
            {
                            
            //M=1000, C=100, D=500, L=50, X=10,  V=5,  I=1

            //only way to tackle this challenge is using an if else
            //and check if larger than numbers
            //1000, 500, 100, 50, 10, 5 , 1
            //Map will not work!!!
            //Switch will not work!!!
            //So similar to numeral => decimal, there will be no collections!!!!!

            //do
            //{

                 do
                {

                if (num >= 1000) 
                {
                    currentNumeral++;
                    conversion = conversion + "M";
                    num=num-1000;
                    System.out.println("remaining num is greater than or equal to: " + 1000);
                } 
                
                else if (num>=500) 
                {
                    currentNumeral++;
                    conversion = conversion + "D";
                    num=num-500;
                    System.out.println("remaining num is greater than or equal to: " + 500);
                }

                else if (num>=100) 
                {
                    currentNumeral++;
                    conversion = conversion + "C";
                    num=num-100;
                    System.out.println("remaining num is greater than or equal to: " + 100);
                }

                 else if (num>=50) 
                {
                    
                    currentNumeral++;
                    conversion = conversion + "L";
                    num = num - 50;
                    System.out.println("remaining num is greater than or equal to: " + 50);
                }

                 else if (num>=10) 
                {
                    
                    currentNumeral++;
                    conversion = conversion + "X";
                    num = num -10;
                    System.out.println("remaining num is greater than or equal to: " + 10);
                }

                 else if (num>=5) 
                {
                   
                    currentNumeral++;
                    conversion = conversion + "V";
                    num = num - 5;
                    System.out.println("remaining num is greater than or equal to: " + 5);
                }

                else if (num>=1)
                {
                    currentNumeral++;
                    conversion = conversion + "I";
                    num = num - 1;
                    System.out.println("remaining num is greater than or equal to: " + 1);
                }
                else
                {
                    
                }
                
                System.out.println(currentNumeral);
                System.out.println("*************REMAINING num: " + num);
                
            //}    while (conversion.length()<=3)
            //this might continue to run indefinitely....
            //so its a big issue having this....

            //it can be tricky having lots of nested do while loops
            //from previous research, if the outer breaks...
            //it will continue to run the inner loop
            //Therefore, if a break is placed in the inner loop, the outer loop still continues. However, if the break is placed in the outer loop, all of the looping stops.
            //I am ensuring this can occur

            char lastNumeralInConversion;
            int lengthConversion = conversion.length();

            if (currentNumeral>=4)
            {
                System.out.println("***************Curentnumeral: " + currentNumeral);
                System.out.println("---------------Initial counter: " + counter);
                
                do
                    {
                        counter++;                       
                        System.out.println("counter: " + counter);
                        
                        //when it reaches here for instance
                        //when filling in XXXX  and has  I remaining for 41
                        //the counter will hit 1)
                        //currentNumeral=4;
                        
                        if (counter==currentNumeral)
                        {
                            System.out.println("HERE AT END");
                            break;
                        }
                        
                        //for 41,  it would have produced  XXXX  and compare  XX (X) X   with  XXX (X)   
                        if (conversion.charAt(lengthConversion-1-counter) == conversion.charAt(lengthConversion-1))
                        {
                            System.out.println("comparing: " + conversion.charAt(lengthConversion-counter) + " with: " + conversion.charAt(lengthConversion-1)); 
                            fourInRowNumeral = conversion.charAt(conversion.length()-1);
                            
                            
                            //this scenario for examples such as 90  LXXXX would come into play
                            //it would get the L and find correct alternative
                            if (currentNumeral>4)
                            {
                            incorrectPredecessor = conversion.charAt(conversion.length()-5);
                            }

                            match++;

                        }  //end of big if

                            }while(counter<currentNumeral);
                            
                            System.out.println("EXIT loop");
                            System.out.println("NUMBER MATCHES: " + match);

                        if (match==3)
                        {
                            System.out.println("THREE MATCHES FOUND");
                            //{

                        //now need to add next higher numeral
                        //this will be slightly more challenging since we don't have conversion in any Collection at all.
                        
                        //Let's say 
                         //four in a row...
                        //now need to remove the four in a row
                        //also need to remove the one before in conversion...

                        //for instance
                        //94 might appear as

                        //94  
                        //-50    L
                        //-10    X
                        //-10    X
                        //-10    X
                        //-10    X

                        //then need to input  XC
                        //and let the process start again from
                        //94-90
                        System.out.println("000000000000000000000000000");
                        //removing 5 characters
                        //note counter is increasing before the do while loop terminates.
                        //so it has to be set a number higher
                        if (counter>5)
                        {
                        conversion=conversion.substring(conversion.length()-5);
                        
                        
                        //this will input the X back in
                        conversion = conversion + fourInRowNumeral;

                        //now need to get the next highest value to L

                        for (String g: nextHighest)
                        {
                            if (g.indexOf(String.valueOf(incorrectPredecessor)+"=>")!=-1)

                            //if (g.indexOf(Character.toString(incorrectPredecessor+"=>")))
                            {
                                //we know notation of Stirngs are C=>D

                                successor = g.substring(4);
                                
                            }
                        }

                        conversion = conversion + successor;
                    }
                    
                    else
                    {
                        System.out.println("REMEDIATING XXXX and IIII and CCCC");
                        //here would need to check the amount of reduction in decimal value.....
                        //this is dealing with situation such as XXXX where it would need a straight
                        //changeover from  XXXX =>  XL
                        
                        //would need another array in order to transform these.
                        //no other possibilities exist since they would be superseded
                        //for instance VVVV (would have rendered XX)
                        
                        String [] incorrectFourNumerals = new String[]{"XXXX=>XL","IIII=>IV","CCCC=>IM"};
                        String correctNumeral;
                        
                       
                        for (String m: incorrectFourNumerals)
                        {
                            System.out.println("----------------------ENTRY IN CONVERTED STRING: " + conversion);
                            correctNumeral = m.substring(0,m.indexOf("="));
                            System.out.println("INCORRECT NUMERAL: " +  correctNumeral);
                            
                            if (conversion.indexOf(correctNumeral)!=-1)
                            {
                                System.out.println("MATCH FOUND IN EXISTING CONVERSION STRING");
                                
                                
                                //similar to before, it would take contents after XXXX=>
                                
                                //it would now wipe the whole conversion and input correctNumeral
                                String temp = conversion;
                                
                                //we know for every numberFoundMatches, it has reduced from XXXX => IL   or IIII=>IV
                                //so we need to preserve 2 x numberFoundMatches
                                
                                if (numberFoundMatches==0)
                                {
                                    conversion = m.substring(m.indexOf(">")+1);
                                }
                                else
                                {
                                    conversion = conversion.substring(0,(2*numberFoundMatches)) + m.substring(m.indexOf(">")+1);
                                }
                                
                                numberFoundMatches++;
                                
                                System.out.println("Correction: " + temp +"=>"+conversion);
                                
                                foundMatch = true;
                                
                            }
                            
                    
                        if(foundMatch)
                        {
                            foundMatch=false;
                            counter=0;
                            currentNumeral=0;
                            match=0;
                            break;
                        }
                    }
                        
                        //M=1000, C=100, D=500, L=50, X=10,  V=5,  I=1
                    }

            }   //end of if match =3

                        }    //end of if match  (current numeral=5)                       


        }  while (num>0);   
        
        }  //end of else    

        return conversion;  

}
}