using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace лаба_1
{
    class Program
    {
        public class CharProbability : IComparable
        {
            public char Character;
            public double Probability;
            public CharProbability(char Character, double Probability)
            {
                this.Character = Character;
                this.Probability = Probability;
            }

            public int CompareTo(object obj)
            {
                CharProbability secondCharProbability = (CharProbability)obj;
                return this.Probability.CompareTo(secondCharProbability.Probability);
            }
        }


        static public void ShannonFanoCode(List<CharProbability> charProbabilities, Dictionary<char,string> CharCode, int l, int r)
        {
            if (l == r)
                return;
            double sum = 0;
            for (int i = l; i <= r; i++)
                sum += charProbabilities[i].Probability;
            double half = sum / 2;
            double SumFirstGroup = 0;
            int GroupSeparationIndex = 0;
            for (int i = l; i <= r; i++)
            {
                if(SumFirstGroup + charProbabilities[i].Probability > half)
                {
                    if (half - SumFirstGroup > charProbabilities[i].Probability / 2)
                        GroupSeparationIndex = i;
                    else
                        GroupSeparationIndex = i - 1;
                    break;
                }
                SumFirstGroup += charProbabilities[i].Probability;
            }
            for(int i = l; i <= GroupSeparationIndex; i++)
            {
                CharCode[charProbabilities[i].Character] += "0";
            }
            for (int i = GroupSeparationIndex+1; i <= r; i++)
            {
                CharCode[charProbabilities[i].Character] += "1";
            }
            ShannonFanoCode(charProbabilities, CharCode, l, GroupSeparationIndex);
            ShannonFanoCode(charProbabilities, CharCode, GroupSeparationIndex + 1, r);
        }


        static void Main(string[] args)
        {
            Console.Write("Enter the string: ");
            string StartedInputString = Console.ReadLine();
            StartedInputString = StartedInputString.ToLower();
            string InputString = StartedInputString.Replace(" ", string.Empty);
            Dictionary<char, int> CharCount = new Dictionary<char, int>();
            for(int i = 0; i< InputString.Length; i++)
            {
                if (!CharCount.Keys.Contains(InputString[i]))
                    CharCount[InputString[i]] = 1;
                else
                    CharCount[InputString[i]]++;
            }
            List<CharProbability> charProbabilities = new List<CharProbability>();
            foreach(char character in CharCount.Keys)
            {
                charProbabilities.Add(new CharProbability(character,CharCount[character] / (double)InputString.Length));
            }
            charProbabilities.Sort();
            charProbabilities.Reverse();
            Dictionary<char, string> CharCode = new Dictionary<char, string>();
            foreach(char character in CharCount.Keys)
            {
                CharCode[character] = "";
            }
            ShannonFanoCode(charProbabilities, CharCode, 0, charProbabilities.Count-1);


            for(int i = 0; i < StartedInputString.Length; i++)
            {
                if(StartedInputString[i] == ' ')
                    Console.Write(' ');
                else
                    Console.Write(CharCode[StartedInputString[i]]);
                Console.Write(".");
            }
            Console.WriteLine();

            foreach(char character in CharCode.Keys)
            {
                Console.WriteLine($"{character} -> {CharCode[character]}");
            }
        }
    }
}