tuenti15.cs

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

namespace Tuenti15
{
    /// <summary>
    /// Markov's chain
    /// </summary>
    /// 

    class Fraction
    {
        public BigInteger Numerator { get; set; }
        public BigInteger Denominator { get; set; }

        public Fraction(BigInteger numerator, BigInteger denominator)
        {
            Numerator = numerator;
            Denominator = denominator;
        }


        private static BigInteger GCD(BigInteger a, BigInteger b)
        {
            while (b != 0)
            {
                var tmp = b;
                b = a % b;
                a = tmp;
            }

            return a;
        }

        public void Irreduce()
        {
            var gcd = GCD(Numerator, Denominator);

            Numerator = Numerator / gcd;
            Denominator = Denominator / gcd;
        }

        public static Fraction operator *(Fraction f1, Fraction f2)
        {
            BigInteger n = f1.Numerator * f2.Numerator;
            BigInteger d = f1.Denominator * f2.Denominator;
            var f = new Fraction(n, d);
            f.Irreduce();

            return f;
        }

        public static Fraction operator +(Fraction f1, Fraction f2)
        {
            var gcd = GCD(f1.Denominator, f2.Denominator);
            var d = f1.Denominator * f2.Denominator / gcd;
            var n = f1.Numerator * d / f1.Denominator + f2.Numerator * d / f2.Denominator;

            var f = new Fraction(n, d);
            f.Irreduce();
            return f;
        }

        public override string ToString()
        {
            return Numerator.ToString() + "/" + Denominator.ToString();
        }
        public static bool operator >(Fraction f1, Fraction f2)
        {
            return f1.Numerator * f2.Denominator > f1.Denominator * f2.Numerator;
        }

        public static bool operator <(Fraction f1, Fraction f2)
        {
            return f1.Numerator * f2.Denominator < f1.Denominator * f2.Numerator;
        }
    }

    class Matrix
    {
        public int Width { get; set; }
        public int Height { get; set; }
        public Fraction[,] M { get; set; }

        public void InitMatrix()
        {
            for (int row = 0; row < Height; row++)
            {
                for (int col = 0; col < Width; col++)
                {
                    M[row, col] = new Fraction(0, 1);
                }
            }
        }

        public static Matrix operator *(Matrix m1, Matrix m2)
        {
            var c = new Fraction[m1.Height, m2.Width];

            for (int row = 0; row < m1.Height; row++)
            {
                for (int col = 0; col < m2.Width; col++)
                {
                    Fraction s = new Fraction(0, 1);
                    for (int i = 0; i < m2.Height; i++)
                    {
                        s = s + m1.M[row, i] * m2.M[i, col];
                    }
                    c[row, col] = s;
                }
            }

            return new Matrix() { M = c, Height = m1.Height, Width = m2.Width };
        }

        public Fraction this[int row, int col]
        {
            get { return M[row, col]; }
            set { M[row, col] = value; }
        }
    }

    class Program
    {
        static List<Matrix> _mTimes = new List<Matrix>();

        static void Main(string[] args)
        {
            var lines = File.ReadAllLines("testInput.txt");
            var nChair = Convert.ToInt32(lines[0]);

            var matrix = new Matrix() { M = new Fraction[nChair, nChair], Height = nChair, Width = nChair };
            matrix.InitMatrix();

            var nLinks = Convert.ToInt32(lines[1]);
            for (int i = 0; i < nLinks; i++)
            {
                var line = lines[i + 2];
                var idx = Convert.ToInt32(line.Split(' ')[0]);
                var targetIdx = Convert.ToInt32(line.Split(' ')[1]);
                var num = Convert.ToInt32(line.Split(' ')[2].Split('/')[0]);
                var de = Convert.ToInt32(line.Split(' ')[2].Split('/')[1]);

                matrix[idx, targetIdx] = new Fraction(num, de);
            }

            //buffer exponential matrix up to 2^10
            _mTimes.Add(matrix);
            for (int i = 0; i < 9; i++)
            {
                var m = _mTimes[_mTimes.Count - 1] * _mTimes[_mTimes.Count - 1];
                _mTimes.Add(m);
            }

            var r1 ="";
            var r2 = "";
            for (int i = 0; i < 100; i++)
            {
                r1 += "Time " + i.ToString() + ": " + Solve(nChair, 5, i);
                r2 += "Time " + i.ToString() + ": " + Solve(nChair, 9, i);
            }

            File.WriteAllText("debug1.txt", r1);
            File.WriteAllText("debug2.txt", r2);

            var q = Convert.ToInt32(lines[2 + nLinks]);
            var allResult = "";
            for (int i = 0; i < q; i++)
            {
                var line = lines[i + 3 + nLinks];
                var idx = Convert.ToInt32(line.Split(' ')[0]);
                var times = Convert.ToInt32(line.Split(' ')[1]);
                if (i < 11)
                {
                    var result = Solve(nChair, idx, times);

                    Console.WriteLine("Case {0}: {1}\n", i + 1, result);
                    allResult += string.Format("Case #{0}: {1}", i + 1, result);
                }
                else
                {
                    allResult += string.Format("Case #{0}: Sorry, I don't have time for calculating buffer matrix\n", i + 1);
                }
            }

            File.WriteAllText("submitOutput.txt", allResult);
        }

        private static string Solve(int nChair, int idx, int times)
        {
            if (times <= 1024) 
            {
                return TrySolve(nChair, idx, times);
            }
            else
            {
                var skip = 0;
                var steps = 0;
                var t = 0;

                List<string> lst = new List<string>();
                List<string> pattern = new List<string>();
                while (steps == 0)
                {
                    if (steps > 100) return "Impossible to solve\n";

                    var r = TrySolve(nChair, idx, t);
                    var fidx = lst.IndexOf(r);

                    if (fidx >= 0)
                    {   
                        if (pattern.Count == 0)
                        {
                            for (int i = fidx; i < lst.Count; i++)
                            {
                                pattern.Add(lst[i]);
                            }
                            skip = lst.Count;
                            lst.Clear();
                        }
                        else 
                        {
                            var isMatch = true;
                            for (int i = 0; i < pattern.Count; i++)
                            {
                                if (pattern[i] != lst[i])
                                {
                                    isMatch = false;
                                    break;
                                }
                            }
                            if (isMatch)
                            {
                                steps = pattern.Count;
                                break;
                            }
                            else
                            {
                                skip += lst.Count;
                                pattern.Clear();
                                for (int i = fidx; i < lst.Count; i++)
                                {
                                    pattern.Add(lst[i]);
                                }
                                lst.Clear();
                            }
                        }
                    }

                    lst.Add(r);
                    
                    t++;
                }

                times = (times - skip) % steps;
                return pattern[times];
            }
        }

        private static string TrySolve(int nChair, int idx, int times)
        {
            Fraction[,] fractions = new Fraction[1, nChair];
            for (int i = 0; i < nChair; i++)
            {
                var f = new Fraction(0, 1);
                if (i == idx)
                    f = new Fraction(1, 1);
                fractions[0, i] = f;
            }

            var stTimes = Convert.ToString(times, 2);
            Matrix p = new Matrix() { M = fractions, Height = 1, Width = nChair };

            for (int i = 0; i < stTimes.Length; i++)
            {
                if (stTimes[i] == '1')
                    p = p * _mTimes[stTimes.Length - i - 1];
            }

            var strOut = "";

            var max = p[0, 0];
            var maxIdx = 0;
            for (int i = 0; i < nChair; i++)
            {
                strOut += p[0, i].Numerator.ToString()[p[0, i].Numerator.ToString().Length - 1] + "/" + p[0, i].Denominator.ToString()[p[0, i].Denominator.ToString().Length - 1] + " ";

                if (p[0, i] > max || (p[0, i].Denominator == max.Denominator && max.Numerator == p[0, i].Numerator))
                {
                    max = p[0, i];
                    maxIdx = i;
                }
            }

            var maxN = max.Numerator.ToString();
            var n = maxN[maxN.Length - 1];

            var maxD = max.Denominator.ToString();
            var d = maxD[maxD.Length - 1];

            var st = string.Format("Chair: {0} Last digits: {1}/{2}\n", maxIdx, n, d);

            return strOut.TrimEnd() + "\n";
        }
    }
}