// ZADANIE 4
        static void wypiszZad4()
        {
            int[] studenci  =  { 0, 1, 2, 3 };
            int[] pytania   =  { 2, 1, 3, 2 };

            // zlozonosc nlogn  taka sama jak dla quicksorta, rozwiazanie jest optymalne  STF shortest time first

            UstalKolejnosc(studenci, pytania);
        }

        static void UstalKolejnosc(int[] studenci, int[] pytania)
        {
            QuickSortInt(0, studenci.Length - 1, pytania, studenci);

            Console.WriteLine("Kolejnosc przyjmowania studentow");

            for (int i = 0; i < studenci.Length; i++)
            {
                Console.WriteLine($"{i+1}. Student #{studenci[i]}");
            }
        }

        static void QuickSortInt(int lo, int hi, int[] t1, int[] t2)
        {
            int i = lo;
            int j = hi;
            int mid = t1[(lo + hi) / 2];

            do
            {
                while (mid > t1[i]) i++;
                while (mid < t1[j]) j--;

                if (i <= j)
                {
                    int temp = t1[i];
                    t1[i] = t1[j];
                    t1[j] = temp;

                    int temp2 = t2[i];
                    t2[i] = t2[j];
                    t2[j] = temp2;

                    i++;
                    j--;
                }
            } while (i <= j);

            if (j > lo) QuickSortInt(lo, j, t1 ,t2);
            if (i < hi) QuickSortInt(i, hi, t1, t2);


        }


        // ZADANIE 5
        static void wypiszZad5()
        {
            int[,] d =
            {
                {2,3,5,2 },
                {1,0,6,1},
                {8,9,2,1},
                {2,5,1,3}
            };

            int[,] p =
            {
                {2,0,1},
                {1,2,5},
                {6,2,1},
                {0,7,0},
                {2,5,4}
            };

            int[,] s =
            {
                {9,4,1 },
                {5,2,1},
                {6,3,1},
                {11, 3, 2}
            };

            int x = 3;
            int y = 4;

            int[,] kroki = new int[y + 1, x + 1];
            int[,] wynik = new int[y + 1, x + 1];

            // zlozonosc  x*y
            findPath(p, d, s, kroki, wynik, x, y);

            wypiszKroki(kroki);
        }

        static void wypiszKroki(int[,] kroki)
        {
            Stack<string> str = new Stack<string>();
            int i = kroki.GetLength(0) - 1;
            int j = kroki.GetLength(1) - 1;
            int m = 0;

            while (i >= 0 && j >= 0)
            {
                if (kroki[i, j] == 1)
                {
                    str.Push("Skoks");
                    i--;
                    j--;
                }
                else if (kroki[i, j] == 2)
                {
                    str.Push("Dół");
                    i--;

                }
                else if (kroki[i, j] == 3)
                {
                    str.Push("Prawo");
                    j--;

                }

                if (i == 0 && j == 0)
                {
                    i = -1;
                    j = -1;
                }
            }

            while (str.Count != 0)
                Console.WriteLine(str.Pop());

        }

        static void findPath(int[,] p, int[,] d, int[,] s, int[,] kroki, int[,] wynik, int x, int y)
        {
            for (int i = 1; i < x + 1; i++)
            {
                wynik[0, i] = wynik[0, i - 1] + p[0, i - 1];
                kroki[0, i] = 3; // PRAWO
            }
            for (int i = 1; i < y + 1; i++)
            {
                wynik[i, 0] = wynik[i - 1, 0] + d[i - 1, 0];
                kroki[i, 0] = 2; // DÓŁ
            }

            for (int i = 1; i < y + 1; i++)
            {
                for (int j = 1; j < x + 1; j++)
                {
                    int ss = wynik[i - 1, j - 1] + s[i - 1, j - 1];
                    int dd = wynik[i - 1, j] + d[i - 1, j];
                    int pp = wynik[i, j - 1] + p[i, j - 1];
                    List<int> temp = new List<int>() { ss, dd, pp };
                    int min = temp.Min();
                    int krok = temp.IndexOf(min) + 1; // indeks 0 + 1 = 1 czyli skoks indeks 1 + 1 = 2 czyli dol itd ...
                    wynik[i, j] = min;
                    kroki[i, j] = krok;
                }
            }
        }

        // ZADANIE 2

        static void wypiszZad2()
        {
            Console.WriteLine("Zadanie 2 quicksort początek");
            Console.WriteLine();


            string[] tStr = new string[] { "aa", "bb", "zz", "cc", "człowiek", "dd", "fantastico działa" };
            string[] tStr2 = new string[] { "Kolos z algorytmow", "Fajny quicksort", "Niesamowite" };
            QuickSort(0, tStr.Length - 1, tStr);

            for (int m = 0; m < tStr.Length; m++)
            {
                Console.WriteLine(tStr[m]);
            }

            Console.WriteLine();

            QuickSort(0, tStr2.Length - 1, tStr2);

            for (int m = 0; m < tStr2.Length; m++)
            {
                Console.WriteLine(tStr2[m]);
            }


            Console.WriteLine();
            Console.WriteLine("Koniec zad 2");
            Console.WriteLine();
            Console.WriteLine();
        }

        static void QuickSort(int lo, int hi, string[] t)
        {
            int i = lo;
            int j = hi;
            string mid = t[(lo + hi) / 2];

            do
            {
                while (StringGreater(t[i], mid)) i++;
                while (StringGreater(mid, t[j])) j--;

                if (i <= j)
                {
                    string temp = t[i];
                    t[i] = t[j];
                    t[j] = temp;
                    i++;
                    j--;
                }
            } while (i <= j);

            if (j > lo) QuickSort(lo, j, t);
            if (i < hi) QuickSort(i, hi, t);


        }

        static bool StringGreater(string s1, string s2)
        {
            int m = 0;
            int i = s1.Length;
            int j = s2.Length;

            while (m < i && m < j)
            {
                if (s1[m] > s2[m])
                    return true;
                else
                    return false;
            }

            return false;
        }

        /*
         ZADANIE 1

        T(n) = n^2 * log(n)

        n = 8  64log8 = 64 * 3 = 192
        n = 16 256log16 = 256 * 4 = 1024

        192 - 30 s
        1024 - x s

        x = 1024 * 30 / 192 = 160 s

        160 s / 2 = 80 s

        ODP wykonanie algorytmu na drugim komputerze (szybszym) zajmie 80 sekund


         */