Organic Carrots

/* http://gosucoder.com/problem/PX */
/* The code may be confusing, cause it was a result of experimentation and constant refactoring. It'll be more useful for you just to read the comments.
 * Also, this is not the largeest scoring algorithm that I've submitted, but it probably would be had I improved the last bit of it. This code produced an average profit of 99.2406. A similar but less sophisticated and even uglier code surprisingly gave me 101.3186, due to a more randomized set of "leftovers".
 * My plan was:
 * 1. Pack as many 500g bags with as little waste as possible. To do so I chose to:
 * 2. Sort the carrots and use one of the folsmalling techniques:
 * 2a. (PackHalves method) Take the smallest carrot and the largest carrot, whose combined weight can be statistically expected to be around 250g (smallest carrots are 50g, largest are 200g). Then find two more carrots so that all four combined weigh 500g. Typical bags will initially be like {50g, 200g, 51g, 199g} and eventually more like {121g, 129g, 122g, 128g}. I found that with this method over 90% of carrots could be packed with only a few grams of waste on a bag. However, since the distribution isn't perfectly even, it still leaves hundreds of unmatched carrots that are either all besmall 125g, or all over 125g.
 * 3a. (PackQuarters method) This one works almost exactly the same, except that instead of taking the largest carrot, it now takes the middle carrot (which combined with the smallest one should weigh around 175g). Then it tries to combine them with two of the larger carrots. For example, the first bag may be like {50g, 125g, 125g, 200g} and the last one like {87g, 88g, 161g, 164g}. So essentially carrots are divided into two halves, which are then packed with the "PackHalves" method, hence the "quarter" name. On surface there's no significant advantage of this method: around 90% of carrots get packed into cool, almost ideal 500g bags, but we still get some leftovers. However, those leftovers are now divided into two weigh groups: there are unmatched small carrots and unmatched large carrots. Now if we run the PackHalves method, some of them will match. A more sophisticated combination of different approaches would probably be even better, but just with a simple run of these two we can pack about 95% of all carrots.
 * 4. This still leaves us with the remaining 5% (or 2%-7% depending on the distribution). I didn't find time to develop and debug a good method for those, so I just put a lame first-fit algorithm that resulted in a lot of waste. I hoped that 2400 brilliant 500g bags would provide enough profit to allow myself for an inefficient distribution of the last dozen of 5kg bags (bigger bags = less bags = less waste) */

using System;
using System.Collections.Generic;
public class Test
{
    static List<float> carrots = new List<float>(); //list of carrots

    static void PackHalves(float tolerance)
    {
        int smallLeft = 0, smallRight = carrots.Count - 1;
        int largeLeft = 1, largeRight = smallRight - 1;
        float sum = 0;
        bool small = true;

        while (smallLeft + 2 < smallRight)
        {
            if (small)
            {
                sum = carrots[smallLeft] + carrots[smallRight];
                small = false;
                largeLeft = smallLeft + 1;
                largeRight = smallRight - 1;
            }
            else
            {
                if (largeLeft == largeRight)
                {
                    if (sum > 250f) smallRight--;
                    else smallLeft++;
                    small = true;
                }
                else if (carrots[largeLeft] + carrots[largeRight] + sum < 500f) largeLeft++;
                else if (carrots[largeLeft] + carrots[largeRight] + sum > tolerance) largeRight--;
                else
                {
                    for (int i = 0; i < duets.Count; i += 4)
                        Console.Write("\n500g {0} {1} {2} {3}", carrots[smallLeft], carrots[smallRight], carrots[largeLeft], carrots[largeRight]);

                    carrots.RemoveAt(smallRight);
                    carrots.RemoveAt(largeRight);
                    carrots.RemoveAt(largeLeft);
                    carrots.RemoveAt(smallLeft);

                    smallRight -= 4; //after deleting some entries from the list, we must move our index back a few places

                    small = true;
                }
            }
        }
    }

    static void PackQuarters(float tolerance)
    {
        int smallLeft = 0, smallRight = carrots.Count / 2;
        int largeLeft = smallRight + 1, largeRight = carrots.Count - 1;
        float sum = 0f;
        bool small = true;
        while (smallLeft < smallRight)
        {
            if (small)
            {
                sum = carrots[smallLeft] + carrots[smallRight];
                small = false;
                largeLeft = smallRight + 1;
                largeRight = carrots.Count - 1;
            }
            else
            {
                if (largeLeft == largeRight)
                {
                    if (sum > 250f) smallRight--;
                    else smallLeft++;
                    small = true;
                }
                else if (carrots[largeLeft] + carrots[largeRight] + sum < 500f) largeLeft++;
                else if (carrots[largeLeft] + carrots[largeRight] + sum > tolerance) largeRight--;
                else
                {
                    for (int i = 0; i < duets.Count; i += 4)
                        Console.Write("\n500g {0} {1} {2} {3}", carrots[smallLeft], carrots[smallRight], carrots[largeLeft], carrots[largeRight]);

                    carrots.RemoveAt(largeRight);
                    carrots.RemoveAt(largeLeft);
                    carrots.RemoveAt(smallRight);
                    carrots.RemoveAt(smallLeft);

                    smallRight -= 2;

                    small = true;
                }
            }
        }
    }


    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        List<float> openBags = new List<float>();
        float a;

        for (int i = 0; i < n; i++)
            carrots.Add(float.Parse(Console.ReadLine()));

        carrots.Sort();

    // a lot of experimentation regarding the values
        PackQuarters(500.1f);
        PackHalves(500.1f);
        PackQuarters(520f);
        PackHalves(520f);

        float sum = 0f;

        for (int i = 0; i < carrots.Count; i++)
        {
            openBags.Add(carrots[i]);
            sum += carrots[i];

            if (sum >= 5000f)
            {
                Console.Write("\n5kg");
                foreach (float carrot in openBags)
                    Console.Write(" " + carrot);
                openBags.Clear();
                sum = 0f;
            }
        }
        if (sum >= 500f)
        {
            List<float> extraBag = new List<float>();
            sum = 0f;

            for (int i = 0; i < openBags.Count; i++)
            {
                sum += openBags[i];
                extraBag.Add(openBags[i]);
                if (sum >= 1000f)
                {
                    Console.Write("\n1kg");
                    foreach (float carrot in extraBag)
                        Console.Write(" " + carrot);
                    extraBag.Clear();
                    sum = 0f;
                }
            }

            if (sum >= 500f)
                Console.Write("\n500g");

            foreach (float carrot in extraBag)
                Console.Write(" " + carrot);
        }
        else
            foreach (float carrot in openBags)
                Console.Write(" + " + carrot);
    }
}