// https://leetcode.com/problems/maximum-average-pass-ratio/

​

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text.Json;

​

public class Program

{

    public class Class

    {

        public int Pass { get; set; }

        public int Total { get; set; }

    }

​

    // initial thought would be to add extra student to the class with highest pass ratio

    // but correct approach here is to get the highest change to the pass ratio when adding 1 student

    //  e.g. ((Pass + 1) / (Total + 1)) - (Pass / Total)

    // here we will be using the PriorityQueue, new to .NET 6

    // but since C# PriorityQueue is a min-heap, we will store the delta pass ratio as negative

    public static decimal GetMaxAvgPassRatio(List<Class> classes, int extraStudents)

    {

        var pQueue = new PriorityQueue<Class, decimal>();

        Console.Write("class delta pass ratio: ");

        classes.ForEach(c =>

        {

            decimal deltaPassRatio = getDeltaPassRatio(c);

            Console.Write($"{deltaPassRatio.ToString("#0.00000")} ");

            pQueue.Enqueue(c, -deltaPassRatio);

        });

        Console.WriteLine();

        while (extraStudents > 0)

        {

            var c = pQueue.Dequeue();

            Console.Write($"adding extra student to class: {JsonSerializer.Serialize(c)}");

            c.Pass++;

            c.Total++;

            extraStudents--;

            decimal deltaPassRatio = getDeltaPassRatio(c);

            Console.WriteLine($", new delta pass ratio: {deltaPassRatio.ToString("#0.00000")}");

            pQueue.Enqueue(c, -deltaPassRatio);

        }

        decimal sumPassRatio = 0;

        Console.Write("dequeueing priority queue: ");

        while (pQueue.Count > 0)

        {

            var c = pQueue.Dequeue();

            Console.Write($"{JsonSerializer.Serialize(c)} ");

            sumPassRatio += (decimal)c.Pass / c.Total;

        }

        Console.WriteLine();

        return sumPassRatio / classes.Count();

    }

    private static decimal getDeltaPassRatio(Class c)

    {

        return ((decimal)(c.Pass + 1) / (c.Total + 1)) - ((decimal)c.Pass / c.Total);

    }

    public static void Main()

    {

        var classes = new List<Class>()

        {

            new Class { Pass = 1, Total = 2 },

            new Class { Pass = 3, Total = 5 },

            new Class { Pass = 2, Total = 2 }

        };

        int extraStudents = 2;

        Console.WriteLine($"input: classes: {NestedListToString(classes, true)}; extra students: {extraStudents}");

        Console.WriteLine($"output: {GetMaxAvgPassRatio(classes, extraStudents).ToString("#0.00000")}");

​

        Console.WriteLine();

        classes = new List<Class>()

        {

            new Class { Pass = 2, Total = 4 },

            new Class { Pass = 3, Total = 9 },

            new Class { Pass = 4, Total = 5 },

            new Class { Pass = 2, Total = 10 }

        };

        extraStudents = 4;

        Console.WriteLine($"input: classes: {NestedListToString(classes, true)}; extra students: {extraStudents}");

        Console.WriteLine($"output: {GetMaxAvgPassRatio(classes, extraStudents).ToString("#0.00000")}");

    }

    // helpers

    public static string NestedListToString<T>

    (

        List<T> nestedList,

        bool asArray = false,

        bool indented = false,

        int level = 1

    )

    {

        string openingBracket = $"{(asArray ? "[" : "{")}{(indented ? $"\n{new string('\t', level)}" : "")}";

        string closingBracket = $"{(indented ? $"\n{new string('\t', level - 1)}" : "")}{(asArray ? "]" : "}")}";

        string joinSeparator = $",{(indented ? $"\n{new string('\t', level)}" : "")}";

​

        if (typeof(T).IsValueType || typeof(T) == typeof(String))

        {

            // if elements in the list is of value type (e.g. int, decimal, bool, char) or string type

            return $"{(asArray ? "[" : "{")}{string.Join(',', nestedList)}{(asArray ? "]" : "}")}";

        }

        else if (typeof(T).IsNested)

        {

            // if elements in the list is a class type

            return $"{openingBracket}{string.Join(joinSeparator, nestedList.Select(i => JsonSerializer.Serialize(i)))}{closingBracket}";

        }

        else

        {

            // here we're still dealing with nested list and so we do a recursive call on the generic method

            // just calling the generic method and passing the nested list element causes the compiler to complain about it not being able to infer the type

            //  thus, we're doing an Invoke() on the generic method with generic argument and that worked

            var nestedListString = string.Join(joinSeparator,

                nestedList.Select(nl => typeof(Program)

                    .GetMethod("NestedListToString")

                    .MakeGenericMethod(typeof(T).GetGenericArguments()[0])

                    .Invoke(null, new object[] { nl, asArray, indented, level + 1 })).ToList());

            return $"{openingBracket}{nestedListString}{closingBracket}";

        }

    }

}