using System;
using System.Collections.Generic;

namespace simplex_method
{
    class SimplexMethod
    {
        List<double> c;
        List<double> newc;
        List<double> b;
        List<double> [] a;
        int cnt = 2;// количество иксов
        public SimplexMethod( List<double> []aa, List<double> bb, List<double>cc)
        {
            a = new List<double>[aa.Length];
            b = new List<double>();
            c = new List<double>();
            for (int i = 0; i<aa.Length; i++)
            {
                a[i] = new List<double>();
                for (int j = 0; j<aa[i].Count; j++)
                {
                    a[i].Add(aa[i][j]);
                }
                b.Add(bb[i]);
            }
            for (int i = 0; i<cc.Count; i++)
                c.Add(cc[i]);
        }
        public void norm()
        {
            for (int i = 0; i<b.Count; i++)
            {
                if (b[i]<0)
                {
                    for (int j = 0; j<b.Count; j++)
                        if (j == i)
                            a[j].Add(1);
                        else
                            a[j].Add(0);

                    for (int j = 0; j<a[i].Count; j++)
                        a[i][j]*=-1;
                    b[i]*=-1;
                    c.Add(0);
                }
            }
            newc = new List<double>();

            for (int j = 0; j<c.Count; j++)
                newc.Add(0);
            for (int j = 0; j<a.Length; j++)
            {
                newc.Add(-1);
                for (int i = 0; i<a.Length; i++)
                {
                    if (i == j)
                        a[i].Add(1);
                    else
                        a[i].Add(0);
                }
            }

        }
        public List<double> solve()
        {
            norm(); // после нормализации, целевая функция ищет max sum(-xi), i>3, т.к. 2 икса найти, третий икс гамма

            List<int> inBazis = new List<int>();
            int n = a.Length;
            int m = a[0].Count;
            for (int i = 0; i<n; i++)
            {
                inBazis.Add(m - n + i);
            }



            int step = 0;
            while (true)
            {
                step++;
                Console.WriteLine("\nCelevaya function at step " + step);
                for (int j = 0; j<m; j++)
                    Console.Write(newc[j] +" ");
                Console.WriteLine();

                Console.WriteLine("In bazis in the step " + step);
                for (int i = 0; i<n; i++)
                {
                    Console.Write(inBazis[i]);
                    Console.Write(' ');
                }


                  Console.WriteLine("coefficients in the step " + step);
                for (int i = 0; i<n; i++, Console.WriteLine())
                {
                    Console.Write(b[i]+" ");
                    for (int j = 0; j<m; j++)
                        Console.Write(a[i][j]+" ");
                }

                List<double> deltas = new List<double>();
                List<bool> baddelta = new List<bool>();
                for (int j = 0; j<m; j++)
                {
                    double sum = -newc[j];
                    for (int i = 0; i<n; i++)
                        sum+=newc[inBazis[i]]*a[i][j];
                    deltas.Add(sum);
                    baddelta.Add(false);
                }
                Console.WriteLine("deltas at the step "+ step);
                bool hasnegative = false;
                for (int j = 0; j<m; j++)
                {
                    if(deltas[j]<0)
                        hasnegative = true;
                    Console.Write(deltas[j]+" ");
                }
                Console.WriteLine();


                if (!hasnegative)   // если отрицательных нет значит план оптимальный
                    break;
                bool ok = true;
                int idx = -1;
                while (ok)
                {
                    ok = false;
                    int minidx = -1;
                    for (int j = 0; j<m; j++)
                    {
                        if (deltas[j] < 0 && !baddelta[j])
                        {
                            if (minidx == -1)
                                minidx = j;
                            else if(deltas[j]<deltas[minidx])
                                minidx = j;
                            ok = true;
                        }
                    }
                    bool haspositive = false;
                    for (int i = 0; i<n; i++)
                    {
                        if (a[i][minidx]>0)
                        {
                            haspositive = true;
                        }
                    }
                    if (!haspositive)// если в столбце нет положительных значит плохой столбец, смотрим след оценку
                        baddelta[minidx] = true;
                    else
                    {
                        idx = minidx;
                        ok = false;
                    }
                }
                if (idx == -1)// решения нет
                    return new List<double>();

                // нашли ведущий столбец, у которого номер idx, надо апдейтнуть таблицу
                // найдем щас че из базиса выкинуть надо и че закинуть
                int tokick = -1;
                double minsootnoshenie = 0;
                for (int i = 0; i<n; i++)
                {
                    if (a[i][idx]>0)
                    {
                        double sootn = newc[inBazis[i]]/a[i][idx];
                        if (tokick == -1)
                        {
                            tokick = i;
                            minsootnoshenie = sootn;
                        }
                        else if (sootn < minsootnoshenie)
                        {
                            minsootnoshenie = sootn;
                            tokick = i;
                        }
                    }
                }
                inBazis[tokick] = idx;
                double coef = 1.0/a[tokick][idx];
                for (int j = 0; j<m; j++)
                {
                    a[tokick][j]*=coef;
                }
                b[tokick]*=coef;
                for (int i = 0; i<n; i++)
                {
                    if (i != tokick)
                    {
                        double coef2= a[i][idx];
                        for (int j = 0; j<m; j++)
                        {
                            a[i][j]-=a[tokick][j] * coef2;
                        }
                        b[i]-=b[tokick]*coef2;
                    }
                }


                bool canstart2 = true;
                for (int i = 0;i<n; i++)
                    if (inBazis[i]>=m-n+i && b[i]>0)
                        canstart2 = false;

                if (canstart2)
                {
                    for (int i = 0; i<n; i++)
                    {
                        if(inBazis[i]>=m-n+i)
                        {
                            for (int j = 0; j<m-n; j++)
                            {
                                if(a[i][j]!=0)
                                {
                                    double coef3 = 1.0/a[i][j];
                                    inBazis[i] = j;
                                    for (int t = 0; t<m; t++)
                                        a[i][t]*=coef3;
                                    break;
                                }
                            }
                        }
                    }

                    for (int i = 0; i<newc.Count; i++)
                        newc[i] = 0;
                    for (int i = 0; i<c.Count; i++)
                        newc[i] = c[i];
                }
            }
            List<double> ans = new List<double>();

            for (int i = 0; i<c.Count; i++)
                ans.Add(0);
                // подумать про случай когда ans[i]>0 , при i>2!!!
            for (int i = 0; i<n; i++)
            {
                if (inBazis[i]>=c.Count)
                    return new List<double>();

                ans[inBazis[i]] = b[i];
            }



            return ans;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            List<double> c = new List<double>();
            List<double> b = new List<double>();
            List<double>[]a = new List<double>[2];
            a[0] = new List<double>();
            a[1] = new List<double>();
            // задача 1
            // c.Add(1);
            // c.Add(-1);
            // c.Add(-1);
            // c.Add(-1);
            // b.Add(2);
            // b.Add(4);
            // a[0].Add(1);
            // a[0].Add(-1);
            // a[0].Add(1);
            // a[0].Add(-2);

            // a[1].Add(1);
            // a[1].Add(1);
            // a[1].Add(1);
            // a[1].Add(1);

            // задача 2
            // c.Add(1);
            // c.Add(0);
            // c.Add(0);
            // c.Add(1);
            // b.Add(10);
            // b.Add(2);
            // a[0].Add(1);
            // a[0].Add(1);
            // a[0].Add(1);
            // a[0].Add(1);
            // a[1].Add(2);
            // a[1].Add(1);
            // a[1].Add(2);
            // a[1].Add(1);
            c.Add(1);
            c.Add(-1);
            c.Add(0);
            c.Add(0);
            b.Add(8);
            b.Add(2);
            a[0].Add(8);
            a[0].Add(4);
            a[0].Add(2);
            a[0].Add(1);
            a[1].Add(2);
            a[1].Add(1);
            a[1].Add(1);
            a[1].Add(2);





            SimplexMethod s = new SimplexMethod(a,b,c);
            List<double> ans = s.solve();
            Console.WriteLine("x* = ");
            for (int i = 0; i<ans.Count; i++)
               Console.Write(ans[i]+" ");
        }
    }
}