Blackone

// Jeffrey Cartagena Alicea
//
using System;
using System.IO;
using System.Text;
using System.Text.RegularExpressions;

namespace SternNumberSystem
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            try
            {
                StreamReader inFile = new StreamReader("input.in");
                StreamWriter outFile = new StreamWriter("output.out");
                BinarySearchTree tree = new BinarySearchTree();
                MatchCollection matches = Regex.Matches(inFile.ReadLine(), @"\d+");
                int i, j;
                //int a = 1, b = 1;

                ResizeTree(100, 100, tree);

                if(matches.Count != 2)
                    throw new Exception("Invalid Input");

                i = Convert.ToInt32(matches[0].ToString());
                j = Convert.ToInt32(matches[1].ToString());


                while(i != j)
                {
                    if(!tree.Search(i, j))
                    {
                        tree.RemoveAllNodes();
                        ResizeTree(i, j, tree);
                        tree.ResetRoute();
                        tree.Search(i,j);
                    }

                    outFile.WriteLine(tree.Result());
                    matches = Regex.Matches(inFile.ReadLine(), @"\d{1,5}");
                    if(matches.Count != 2)
                        break;
                    tree.ResetRoute();
                    i = Convert.ToInt32(matches[0].ToString());
                    j = Convert.ToInt32(matches[1].ToString());
                }
                Console.Write("Please press enter");
                Console.Read();
                inFile.Close();
                outFile.Close();
            }
            catch(System.IO.FileNotFoundException)
            {
                Console.WriteLine("Input File does not exist\n");
            }
        }

        static public void ResizeTree(int num, int den, BinarySearchTree tree)
        {
            for(int i=1; i <= num; i++)
                for(int j=1; j <= den; j++)
                    tree.Insert(i, j);
        }
    }

    public class BinarySearchTree
    {
        private TreeNode root;
        private String route;

        public bool Search(int num, int den)
        {
            return PrintSearch(root, num, den);
        }

        // Search the value in the tree
        private bool PrintSearch(TreeNode node, int num, int den)
        {
            float nodeValue, val;

            if(node == null)
                return false;
            else
            {
                nodeValue = node.numerator/(float)node.denominator;
                val = num/(float)den;

                if(nodeValue == val)
                    return true;
                else if(val < nodeValue)
                {
                    route += "L";
                    PrintSearch(node.left, num, den);
                }
                else
                {
                    route += "R";
                    PrintSearch(node.right, num, den);
                }
            }
            return true;

        }

        // Insert a new value in the tree
        public void Insert(int num, int den)
        {
            TreeNode newNode = new TreeNode(num, den);
            TreeNode parent = null;

            if(IsEmpty())
                root = newNode;

            else if(num == den && num != 1 && den != 1)
                return;

            else
            {
                TreeNode current = root;
                float nodeValue, currentValue;

                while(current != null)
                {
                    parent = current;
                    nodeValue = (float)newNode.numerator/newNode.denominator;
                    currentValue = (float)current.numerator/current.denominator;

                    if(nodeValue == currentValue)
                        return;
                    else if(nodeValue > currentValue)
                        current = current.right;
                    else
                        current = current.left;
                }

                nodeValue = (float)newNode.numerator/newNode.denominator;
                currentValue = (float)parent.numerator/parent.denominator;

                if(nodeValue < currentValue)
                    parent.left = newNode;
                else
                    parent.right = newNode;
            }
        }


        public bool IsEmpty()
        {
            return root == null;
        }

        // Default Constructor
        public BinarySearchTree()
        {
            root = null;
            route = "";
        }

        // Returns the Result
        public String Result()
        {
            return route;
        }

        // Reset the route to null
        public void ResetRoute()
        {
            route = "";
        }

        public void RemoveAllNodes()
        {
            RemoveAllNodes(root);
            root = null;
        }

        private void RemoveAllNodes(TreeNode node)
        {
            if(node != null)
            {
                RemoveAllNodes(node.left);
                RemoveAllNodes(node.right);
                node = null;
                route = "";
            }
        }


    }

    public class TreeNode
    {
        public TreeNode left;
        public TreeNode right;
        public int numerator, denominator;

        // Parameterized Constructor
        public TreeNode(int num, int den)
        {
            left = null;
            right = null;
            numerator = num;
            denominator = den;
        }
    }
}