using System;

using System.Linq;

​

namespace Prison

{

    class Program

    {

        public static void Main()

        {

            int randWin = 0;

            int loopWin = 0;

            double randWinTotal = 0;

            double randCycles = 0;

            double loopWinTotal = 0;

            double loopCycles = 0;

​

            Room room = new(100);

            for (int j = 1; j < 1001; j++)

            {

                room.Shuffle();

                for (int i = 1; i < 101; i++)

                {

                    Prisoner prisonerRand = new(i, false, 50);

                    if (prisonerRand.Search(room.Boxes))

                        randWin++;

                    Prisoner prisonerLoop = new(i, true, 50);

                    if (!prisonerLoop.Search(room.Boxes))

                        continue;   

                    loopWin++;

                }

                if (randWin == 100)

                    randWinTotal++;

                randCycles++;

                randWin = 0;

                if (loopWin == 100)

                    loopWinTotal++;

                loopCycles++;

                loopWin = 0;

            }

​

            Console.WriteLine($"Random strategy: {randWinTotal / randCycles}");

            Console.WriteLine($"Loop strategy: {loopWinTotal / loopCycles}");

        }

​

    class Room

    {

        public int[] Boxes;

​

        public Room(int weight = 100)

        {

            Boxes = new int[weight];

            for(int i = 0; i < Boxes.Length; i++)

                Boxes[i] = i+1;

        }

​

        public void Shuffle()

        {

            Random rand = new();

​

            for (int i = Boxes.Length - 1; i >= 1; i--)

            {

                int j = rand.Next(i + 1);

​

                int tmp = Boxes[j];

                Boxes[j] = Boxes[i];

                Boxes[i] = tmp;

            }

        }

    }

​

    class Prisoner

        {

            public bool LoopSearch;

            public int AtteptsAmount;

            public int PrisonerNumber;

​

            public Prisoner(int prisonerNumber, bool loopSearch = true, int atteptsNum = 50)

            {

                LoopSearch = loopSearch;

                AtteptsAmount = atteptsNum;

                PrisonerNumber = prisonerNumber;

            }

​

            public bool Search(int[] boxes)

            {

                int[] WathedBoxes = boxes.ToArray();

                Random rand = new();

                int selectedBox;

​

                if (!this.LoopSearch)

                {

                    for(int i = 0; i < this.AtteptsAmount; i++)

                    {

                        while (true)

                        {

                            selectedBox = rand.Next(1, boxes.Length);

                            if (WathedBoxes[selectedBox - 1] == -1)

                                continue;

                            break;

                        }

                        if (this.PrisonerNumber != boxes[selectedBox - 1])

                            WathedBoxes[selectedBox - 1] = -1;

                        else

                            return true;

                    }

                    return false;

                }

                else

                {

                    int firstBox = PrisonerNumber;

                    int nextBox;

​

                    if (boxes[firstBox - 1] == PrisonerNumber)

                        return true;

                    nextBox = boxes[firstBox - 1];

​

                    for (int i = 0; i < this.AtteptsAmount; i++)

                    {

                        if (boxes[nextBox - 1] == PrisonerNumber)

                            return true;

                        nextBox = boxes[nextBox - 1];

                    }

                    return false;

                }

            }

        }

    }

}