using System;

using System.Collections.Generic;

​

public class Program

{

    static Random rng = new Random();

​

    // Generate a random permutation of n elements

    public static int[] GeneratePermutation(int n)

    {

        int[] perm = new int[n];

        for (int i = 0; i < n; i++) perm[i] = i;

​

        for (int i = n - 1; i > 0; i--)

        {

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

            int temp = perm[i];

            perm[i] = perm[j];

            perm[j] = temp;

        }

        return perm;

    }

​

    // Get all cycle lengths in the permutation

    public static List<int> GetCycleLengths(int[] perm)

    {

        int n = perm.Length;

        bool[] visited = new bool[n];

        List<int> cycleLengths = new List<int>();

​

        for (int i = 0; i < n; i++)

        {

            if (!visited[i])

            {

                int length = 0;

                int x = i;

                while (!visited[x])

                {

                    visited[x] = true;

                    x = perm[x];

                    length++;

                }

                cycleLengths.Add(length);

            }

        }

        return cycleLengths;

    }

​

    // Run simulation and return the longest cycle in each trial

    public static List<int> SimulateLongestCycle(int n, int trials)

    {

        List<int> longestCycles = new List<int>();

​

        for (int t = 0; t < trials; t++)

        {

            int[] perm = GeneratePermutation(n);

            List<int> cycles = GetCycleLengths(perm);

            int max = 0;

            foreach (int len in cycles)

            {

                if (len > max) max = len;

            }

            longestCycles.Add(max);

        }

​

        return longestCycles;

    }

​

    public static void Main()

    {

        int n = 100;

        int trials = 1999999;

        List<int> results = SimulateLongestCycle(n, trials);

​

        // Count how many times each cycle length appeared

        Dictionary<int, int> counts = new Dictionary<int, int>();

        int successCount = 0;

        int failureCount = 0;

​

        foreach (int length in results)

        {

            if (!counts.ContainsKey(length)) counts[length] = 0;

            counts[length]++;

​

            if (length <= n / 2)

                successCount++;

            else

                failureCount++;

        }

​

        Console.WriteLine($"Simulation of {trials} trials with {n} prisoners:\n");

​

        // Sort the cycle lengths in increasing order before printing

        foreach (var pair in new SortedList<int, int>(counts))

        {

            double percentage = 100.0 * pair.Value / trials;

            Console.WriteLine($"Longest cycle = {pair.Key}: {pair.Value} times ({percentage:F2}%)");

        }

​

        Console.WriteLine("\n--- Cumulative Probability Summary ---");

        Console.WriteLine($"Success (Longest cycle ≤ {n / 2}): {successCount} times ({(100.0 * successCount / trials):F2}%)");

        Console.WriteLine($"Failure (Longest cycle > {n / 2}): {failureCount} times ({(100.0 * failureCount / trials):F2}%)");

    }

}

​

​

​