Introduction to Greedy Algorithms

def greedy(coins, x):                          # largest coin first; the coins come largest first
    count = 0
    for c in coins:
        count += x // c
        x %= c
    return count


def fewest(coins, top):                        # the fewest coins for every amount up to top
    best = [0] * (top + 1)
    for x in range(1, top + 1):
        best[x] = min(best[x - c] + 1 for c in coins if c <= x)
    return best


systems = wrong = 0
worst = (0, None, 0)                           # coins too many, the coin system, the amount
for a in range(2, 30):
    for b in range(a + 1, 31):
        coins = [b, a, 1]
        best = fewest(coins, 2 * b)
        systems += 1
        bad = False
        for x in range(1, 2 * b + 1):
            extra = greedy(coins, x) - best[x]
            if extra > 0:
                bad = True
                if extra > worst[0]:
                    worst = (extra, coins, x)
        wrong += bad
print(f"{systems} coin systems {{1, a, b}} with b up to 30: greedy pays some amount with too many coins in {wrong}")
extra, coins, x = worst
g = greedy(coins, x)
print(f"the worst, {{1, {coins[1]}, {coins[0]}}}: {x} paid with {g} coins, where {g - extra} do")
india = [1000, 500, 100, 50, 20, 10, 5, 2, 1]
india_best = fewest(india, 5000)
always = all(greedy(india, x) == india_best[x] for x in range(1, 5001))
print("India's coins and notes, every amount up to 5,000:",
      "greedy is always the fewest" if always else "greedy is wrong somewhere")

# 406 coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in 260
# the worst, {1, 29, 30}: 58 paid with 29 coins, where 2 do
# India's coins and notes, every amount up to 5,000: greedy is always the fewest

public class Main {
    static int greedy(int[] coins, int x) {          // largest coin first; the coins come largest first
        int count = 0;
        for (int c : coins) {
            count += x / c;
            x %= c;
        }
        return count;
    }

    static int[] fewest(int[] coins, int top) {      // the fewest coins for every amount up to top
        int[] best = new int[top + 1];
        for (int x = 1; x <= top; x++) {
            best[x] = Integer.MAX_VALUE;
            for (int c : coins) if (c <= x) best[x] = Math.min(best[x], best[x - c] + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        int systems = 0, wrong = 0, worstExtra = 0, worstAmount = 0;
        int[] worstCoins = null;                     // coins too many, the coin system, the amount
        for (int a = 2; a < 30; a++) {
            for (int b = a + 1; b <= 30; b++) {
                int[] coins = {b, a, 1};
                int[] best = fewest(coins, 2 * b);
                systems++;
                boolean bad = false;
                for (int x = 1; x <= 2 * b; x++) {
                    int extra = greedy(coins, x) - best[x];
                    if (extra > 0) {
                        bad = true;
                        if (extra > worstExtra) {
                            worstExtra = extra;
                            worstCoins = coins;
                            worstAmount = x;
                        }
                    }
                }
                if (bad) wrong++;
            }
        }
        System.out.println(systems + " coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in " + wrong);
        int g = greedy(worstCoins, worstAmount);
        System.out.println("the worst, {1, " + worstCoins[1] + ", " + worstCoins[0] + "}: " + worstAmount + " paid with " + g
                + " coins, where " + (g - worstExtra) + " do");
        int[] india = {1000, 500, 100, 50, 20, 10, 5, 2, 1};
        int[] indiaBest = fewest(india, 5000);
        boolean always = true;
        for (int x = 1; x <= 5000; x++) if (greedy(india, x) != indiaBest[x]) always = false;
        System.out.println("India's coins and notes, every amount up to 5,000: "
                + (always ? "greedy is always the fewest" : "greedy is wrong somewhere"));
    }
}

// 406 coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in 260
// the worst, {1, 29, 30}: 58 paid with 29 coins, where 2 do
// India's coins and notes, every amount up to 5,000: greedy is always the fewest

#include <bits/stdc++.h>
using namespace std;

int greedy(const vector<int>& coins, int x) {        // largest coin first; the coins come largest first
    int count = 0;
    for (int c : coins) {
        count += x / c;
        x %= c;
    }
    return count;
}

vector<int> fewest(const vector<int>& coins, int top) {   // the fewest coins for every amount up to top
    vector<int> best(top + 1, 0);
    for (int x = 1; x <= top; x++) {
        best[x] = INT_MAX;
        for (int c : coins) if (c <= x) best[x] = min(best[x], best[x - c] + 1);
    }
    return best;
}

int main() {
    int systems = 0, wrong = 0, worstExtra = 0, worstAmount = 0;
    vector<int> worstCoins;                              // coins too many, the coin system, the amount
    for (int a = 2; a < 30; a++) {
        for (int b = a + 1; b <= 30; b++) {
            vector<int> coins = {b, a, 1};
            vector<int> best = fewest(coins, 2 * b);
            systems++;
            bool bad = false;
            for (int x = 1; x <= 2 * b; x++) {
                int extra = greedy(coins, x) - best[x];
                if (extra > 0) {
                    bad = true;
                    if (extra > worstExtra) {
                        worstExtra = extra;
                        worstCoins = coins;
                        worstAmount = x;
                    }
                }
            }
            if (bad) wrong++;
        }
    }
    cout << systems << " coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in " << wrong
         << "\n";
    int g = greedy(worstCoins, worstAmount);
    cout << "the worst, {1, " << worstCoins[1] << ", " << worstCoins[0] << "}: " << worstAmount << " paid with " << g
         << " coins, where " << g - worstExtra << " do\n";
    vector<int> india = {1000, 500, 100, 50, 20, 10, 5, 2, 1};
    vector<int> indiaBest = fewest(india, 5000);
    bool always = true;
    for (int x = 1; x <= 5000; x++) if (greedy(india, x) != indiaBest[x]) always = false;
    cout << "India's coins and notes, every amount up to 5,000: "
         << (always ? "greedy is always the fewest" : "greedy is wrong somewhere") << "\n";
}

// 406 coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in 260
// the worst, {1, 29, 30}: 58 paid with 29 coins, where 2 do
// India's coins and notes, every amount up to 5,000: greedy is always the fewest

function greedy(coins, x) {                       // largest coin first; the coins come largest first
    let count = 0;
    for (const c of coins) {
        count += Math.floor(x / c);
        x %= c;
    }
    return count;
}

function fewest(coins, top) {                     // the fewest coins for every amount up to top
    const best = new Array(top + 1).fill(0);
    for (let x = 1; x <= top; x++) {
        best[x] = Infinity;
        for (const c of coins) if (c <= x) best[x] = Math.min(best[x], best[x - c] + 1);
    }
    return best;
}

let systems = 0, wrong = 0;
let worst = [0, null, 0];                         // coins too many, the coin system, the amount
for (let a = 2; a < 30; a++) {
    for (let b = a + 1; b <= 30; b++) {
        const coins = [b, a, 1];
        const best = fewest(coins, 2 * b);
        systems++;
        let bad = false;
        for (let x = 1; x <= 2 * b; x++) {
            const extra = greedy(coins, x) - best[x];
            if (extra > 0) {
                bad = true;
                if (extra > worst[0]) worst = [extra, coins, x];
            }
        }
        if (bad) wrong++;
    }
}
console.log(`${systems} coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in ${wrong}`);
const [extra, coins, amount] = worst;
const g = greedy(coins, amount);
console.log(`the worst, {1, ${coins[1]}, ${coins[0]}}: ${amount} paid with ${g} coins, where ${g - extra} do`);
const india = [1000, 500, 100, 50, 20, 10, 5, 2, 1];
const indiaBest = fewest(india, 5000);
let always = true;
for (let x = 1; x <= 5000; x++) if (greedy(india, x) !== indiaBest[x]) always = false;
console.log(`India's coins and notes, every amount up to 5,000: ${always ? "greedy is always the fewest" : "greedy is wrong somewhere"}`);

// 406 coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in 260
// the worst, {1, 29, 30}: 58 paid with 29 coins, where 2 do
// India's coins and notes, every amount up to 5,000: greedy is always the fewest

function greedy(coins: number[], x: number): number {   // largest coin first; the coins come largest first
    let count = 0;
    for (const c of coins) {
        count += Math.floor(x / c);
        x %= c;
    }
    return count;
}

function fewest(coins: number[], top: number): number[] {   // the fewest coins for every amount up to top
    const best: number[] = new Array(top + 1).fill(0);
    for (let x = 1; x <= top; x++) {
        best[x] = Infinity;
        for (const c of coins) if (c <= x) best[x] = Math.min(best[x], best[x - c] + 1);
    }
    return best;
}

let systems = 0, wrong = 0;
let worst: [number, number[], number] = [0, [], 0];   // coins too many, the coin system, the amount
for (let a = 2; a < 30; a++) {
    for (let b = a + 1; b <= 30; b++) {
        const coins = [b, a, 1];
        const best = fewest(coins, 2 * b);
        systems++;
        let bad = false;
        for (let x = 1; x <= 2 * b; x++) {
            const extra = greedy(coins, x) - best[x];
            if (extra > 0) {
                bad = true;
                if (extra > worst[0]) worst = [extra, coins, x];
            }
        }
        if (bad) wrong++;
    }
}
console.log(`${systems} coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in ${wrong}`);
const [extra, coins, amount] = worst;
const g = greedy(coins, amount);
console.log(`the worst, {1, ${coins[1]}, ${coins[0]}}: ${amount} paid with ${g} coins, where ${g - extra} do`);
const india = [1000, 500, 100, 50, 20, 10, 5, 2, 1];
const indiaBest = fewest(india, 5000);
let always = true;
for (let x = 1; x <= 5000; x++) if (greedy(india, x) !== indiaBest[x]) always = false;
console.log(`India's coins and notes, every amount up to 5,000: ${always ? "greedy is always the fewest" : "greedy is wrong somewhere"}`);

// 406 coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in 260
// the worst, {1, 29, 30}: 58 paid with 29 coins, where 2 do
// India's coins and notes, every amount up to 5,000: greedy is always the fewest

using System;

class Program {
    static int Greedy(int[] coins, int x) {          // largest coin first; the coins come largest first
        int count = 0;
        foreach (int c in coins) {
            count += x / c;
            x %= c;
        }
        return count;
    }

    static int[] Fewest(int[] coins, int top) {      // the fewest coins for every amount up to top
        var best = new int[top + 1];
        for (int x = 1; x <= top; x++) {
            best[x] = int.MaxValue;
            foreach (int c in coins) if (c <= x) best[x] = Math.Min(best[x], best[x - c] + 1);
        }
        return best;
    }

    static void Main() {
        int systems = 0, wrong = 0, worstExtra = 0, worstAmount = 0;
        int[] worstCoins = Array.Empty<int>();       // coins too many, the coin system, the amount
        for (int a = 2; a < 30; a++) {
            for (int b = a + 1; b <= 30; b++) {
                int[] coins = { b, a, 1 };
                int[] best = Fewest(coins, 2 * b);
                systems++;
                bool bad = false;
                for (int x = 1; x <= 2 * b; x++) {
                    int extra = Greedy(coins, x) - best[x];
                    if (extra > 0) {
                        bad = true;
                        if (extra > worstExtra) {
                            worstExtra = extra;
                            worstCoins = coins;
                            worstAmount = x;
                        }
                    }
                }
                if (bad) wrong++;
            }
        }
        Console.WriteLine($"{systems} coin systems {{1, a, b}} with b up to 30: greedy pays some amount with too many coins in {wrong}");
        int g = Greedy(worstCoins, worstAmount);
        Console.WriteLine($"the worst, {{1, {worstCoins[1]}, {worstCoins[0]}}}: {worstAmount} paid with {g} coins, where {g - worstExtra} do");
        int[] india = { 1000, 500, 100, 50, 20, 10, 5, 2, 1 };
        int[] indiaBest = Fewest(india, 5000);
        bool always = true;
        for (int x = 1; x <= 5000; x++) if (Greedy(india, x) != indiaBest[x]) always = false;
        Console.WriteLine("India's coins and notes, every amount up to 5,000: "
            + (always ? "greedy is always the fewest" : "greedy is wrong somewhere"));
    }
}

// 406 coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in 260
// the worst, {1, 29, 30}: 58 paid with 29 coins, where 2 do
// India's coins and notes, every amount up to 5,000: greedy is always the fewest

package main

import (
	"fmt"
	"math"
)

func greedy(coins []int, x int) int { // largest coin first; the coins come largest first
	count := 0
	for _, c := range coins {
		count += x / c
		x %= c
	}
	return count
}

func fewest(coins []int, top int) []int { // the fewest coins for every amount up to top
	best := make([]int, top+1)
	for x := 1; x <= top; x++ {
		best[x] = math.MaxInt32
		for _, c := range coins {
			if c <= x && best[x-c]+1 < best[x] {
				best[x] = best[x-c] + 1
			}
		}
	}
	return best
}

func main() {
	systems, wrong, worstExtra, worstAmount := 0, 0, 0, 0
	var worstCoins []int // coins too many, the coin system, the amount
	for a := 2; a < 30; a++ {
		for b := a + 1; b <= 30; b++ {
			coins := []int{b, a, 1}
			best := fewest(coins, 2*b)
			systems++
			bad := false
			for x := 1; x <= 2*b; x++ {
				extra := greedy(coins, x) - best[x]
				if extra > 0 {
					bad = true
					if extra > worstExtra {
						worstExtra, worstCoins, worstAmount = extra, coins, x
					}
				}
			}
			if bad {
				wrong++
			}
		}
	}
	fmt.Printf("%d coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in %d\n", systems, wrong)
	g := greedy(worstCoins, worstAmount)
	fmt.Printf("the worst, {1, %d, %d}: %d paid with %d coins, where %d do\n", worstCoins[1], worstCoins[0], worstAmount, g, g-worstExtra)
	india := []int{1000, 500, 100, 50, 20, 10, 5, 2, 1}
	indiaBest := fewest(india, 5000)
	always := true
	for x := 1; x <= 5000; x++ {
		if greedy(india, x) != indiaBest[x] {
			always = false
		}
	}
	verdict := "greedy is wrong somewhere"
	if always {
		verdict = "greedy is always the fewest"
	}
	fmt.Println("India's coins and notes, every amount up to 5,000: " + verdict)
}

// 406 coin systems {1, a, b} with b up to 30: greedy pays some amount with too many coins in 260
// the worst, {1, 29, 30}: 58 paid with 29 coins, where 2 do
// India's coins and notes, every amount up to 5,000: greedy is always the fewest

greed, cookies = sorted([4, 2, 7, 1, 5]), sorted([3, 6, 1, 5, 2, 2])
got, j = [], 0
for g in greed:                                # smallest greed first, each gets the smallest cookie that's enough
    while j < len(cookies) and cookies[j] < g:
        j += 1                                 # too small for this child, so too small for every child after
    if j == len(cookies):
        break
    got.append(f"greed {g} gets {cookies[j]}")
    j += 1
print(f"fed {len(got)} of {len(greed)} children:", ", ".join(got))

# fed 4 of 5 children: greed 1 gets 1, greed 2 gets 2, greed 4 gets 5, greed 5 gets 6

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] greed = {4, 2, 7, 1, 5}, cookies = {3, 6, 1, 5, 2, 2};
        Arrays.sort(greed);
        Arrays.sort(cookies);
        List<String> got = new ArrayList<>();
        int j = 0;
        for (int g : greed) {                        // smallest greed first, each gets the smallest cookie that's enough
            while (j < cookies.length && cookies[j] < g) j++;   // too small for this child, so for every child after
            if (j == cookies.length) break;
            got.add("greed " + g + " gets " + cookies[j]);
            j++;
        }
        System.out.println("fed " + got.size() + " of " + greed.length + " children: " + String.join(", ", got));
    }
}

// fed 4 of 5 children: greed 1 gets 1, greed 2 gets 2, greed 4 gets 5, greed 5 gets 6

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> greed = {4, 2, 7, 1, 5}, cookies = {3, 6, 1, 5, 2, 2};
    sort(greed.begin(), greed.end());
    sort(cookies.begin(), cookies.end());
    vector<string> got;
    size_t j = 0;
    for (int g : greed) {                                // smallest greed first, each gets the smallest cookie that's enough
        while (j < cookies.size() && cookies[j] < g) j++;    // too small for this child, so for every child after
        if (j == cookies.size()) break;
        got.push_back("greed " + to_string(g) + " gets " + to_string(cookies[j]));
        j++;
    }
    cout << "fed " << got.size() << " of " << greed.size() << " children: ";
    for (size_t k = 0; k < got.size(); k++) cout << (k ? ", " : "") << got[k];
    cout << "\n";
}

// fed 4 of 5 children: greed 1 gets 1, greed 2 gets 2, greed 4 gets 5, greed 5 gets 6

const greed = [4, 2, 7, 1, 5].sort((a, b) => a - b), cookies = [3, 6, 1, 5, 2, 2].sort((a, b) => a - b);
const got = [];
let j = 0;
for (const g of greed) {                          // smallest greed first, each gets the smallest cookie that's enough
    while (j < cookies.length && cookies[j] < g) j++;    // too small for this child, so for every child after
    if (j === cookies.length) break;
    got.push(`greed ${g} gets ${cookies[j]}`);
    j++;
}
console.log(`fed ${got.length} of ${greed.length} children: ${got.join(", ")}`);

// fed 4 of 5 children: greed 1 gets 1, greed 2 gets 2, greed 4 gets 5, greed 5 gets 6

const greed: number[] = [4, 2, 7, 1, 5].sort((a, b) => a - b);
const cookies: number[] = [3, 6, 1, 5, 2, 2].sort((a, b) => a - b);
const got: string[] = [];
let j = 0;
for (const g of greed) {                          // smallest greed first, each gets the smallest cookie that's enough
    while (j < cookies.length && cookies[j] < g) j++;    // too small for this child, so for every child after
    if (j === cookies.length) break;
    got.push(`greed ${g} gets ${cookies[j]}`);
    j++;
}
console.log(`fed ${got.length} of ${greed.length} children: ${got.join(", ")}`);

// fed 4 of 5 children: greed 1 gets 1, greed 2 gets 2, greed 4 gets 5, greed 5 gets 6

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] greed = { 4, 2, 7, 1, 5 }, cookies = { 3, 6, 1, 5, 2, 2 };
        Array.Sort(greed);
        Array.Sort(cookies);
        var got = new List<string>();
        int j = 0;
        foreach (int g in greed) {                   // smallest greed first, each gets the smallest cookie that's enough
            while (j < cookies.Length && cookies[j] < g) j++;   // too small for this child, so for every child after
            if (j == cookies.Length) break;
            got.Add($"greed {g} gets {cookies[j]}");
            j++;
        }
        Console.WriteLine($"fed {got.Count} of {greed.Length} children: {string.Join(", ", got)}");
    }
}

// fed 4 of 5 children: greed 1 gets 1, greed 2 gets 2, greed 4 gets 5, greed 5 gets 6

package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
	greed, cookies := []int{4, 2, 7, 1, 5}, []int{3, 6, 1, 5, 2, 2}
	sort.Ints(greed)
	sort.Ints(cookies)
	var got []string
	j := 0
	for _, g := range greed { // smallest greed first, each gets the smallest cookie that's enough
		for j < len(cookies) && cookies[j] < g {
			j++ // too small for this child, so too small for every child after
		}
		if j == len(cookies) {
			break
		}
		got = append(got, fmt.Sprintf("greed %d gets %d", g, cookies[j]))
		j++
	}
	fmt.Printf("fed %d of %d children: %s\n", len(got), len(greed), strings.Join(got, ", "))
}

// fed 4 of 5 children: greed 1 gets 1, greed 2 gets 2, greed 4 gets 5, greed 5 gets 6

def change(bills):                             # every lemonade costs 5; give change from what's in the till
    fives = tens = 0
    for i, bill in enumerate(bills):
        if bill == 5:
            fives += 1
        elif bill == 10:
            if not fives:
                return f"stuck at bill {i + 1}"
            fives, tens = fives - 1, tens + 1
        elif tens and fives:                   # a 20: a 10 and a 5 back keeps the 5s, which more bills need
            tens, fives = tens - 1, fives - 1
        elif fives >= 3:
            fives -= 3
        else:
            return f"stuck at bill {i + 1}"
    return f"everyone served, {fives} fives and {tens} tens left"


print(change([5, 5, 5, 5, 10, 20, 10, 10]))

# everyone served, 0 fives and 2 tens left

public class Main {
    static String change(int[] bills) {              // every lemonade costs 5; give change from what's in the till
        int fives = 0, tens = 0;
        for (int i = 0; i < bills.length; i++) {
            int bill = bills[i];
            if (bill == 5) fives++;
            else if (bill == 10) {
                if (fives == 0) return "stuck at bill " + (i + 1);
                fives--;
                tens++;
            } else if (tens > 0 && fives > 0) {      // a 20: a 10 and a 5 back keeps the 5s, which more bills need
                tens--;
                fives--;
            } else if (fives >= 3) fives -= 3;
            else return "stuck at bill " + (i + 1);
        }
        return "everyone served, " + fives + " fives and " + tens + " tens left";
    }

    public static void main(String[] args) {
        System.out.println(change(new int[] {5, 5, 5, 5, 10, 20, 10, 10}));
    }
}

// everyone served, 0 fives and 2 tens left

#include <bits/stdc++.h>
using namespace std;

string change(const vector<int>& bills) {           // every lemonade costs 5; give change from what's in the till
    int fives = 0, tens = 0;
    for (size_t i = 0; i < bills.size(); i++) {
        int bill = bills[i];
        if (bill == 5) fives++;
        else if (bill == 10) {
            if (fives == 0) return "stuck at bill " + to_string(i + 1);
            fives--;
            tens++;
        } else if (tens > 0 && fives > 0) {              // a 20: a 10 and a 5 back keeps the 5s, which more bills need
            tens--;
            fives--;
        } else if (fives >= 3) fives -= 3;
        else return "stuck at bill " + to_string(i + 1);
    }
    return "everyone served, " + to_string(fives) + " fives and " + to_string(tens) + " tens left";
}

int main() {
    cout << change({5, 5, 5, 5, 10, 20, 10, 10}) << "\n";
}

// everyone served, 0 fives and 2 tens left

function change(bills) {                          // every lemonade costs 5; give change from what's in the till
    let fives = 0, tens = 0;
    for (let i = 0; i < bills.length; i++) {
        const bill = bills[i];
        if (bill === 5) fives++;
        else if (bill === 10) {
            if (fives === 0) return `stuck at bill ${i + 1}`;
            fives--;
            tens++;
        } else if (tens > 0 && fives > 0) {           // a 20: a 10 and a 5 back keeps the 5s, which more bills need
            tens--;
            fives--;
        } else if (fives >= 3) fives -= 3;
        else return `stuck at bill ${i + 1}`;
    }
    return `everyone served, ${fives} fives and ${tens} tens left`;
}

console.log(change([5, 5, 5, 5, 10, 20, 10, 10]));

// everyone served, 0 fives and 2 tens left

function change(bills: number[]): string {        // every lemonade costs 5; give change from what's in the till
    let fives = 0, tens = 0;
    for (let i = 0; i < bills.length; i++) {
        const bill = bills[i];
        if (bill === 5) fives++;
        else if (bill === 10) {
            if (fives === 0) return `stuck at bill ${i + 1}`;
            fives--;
            tens++;
        } else if (tens > 0 && fives > 0) {           // a 20: a 10 and a 5 back keeps the 5s, which more bills need
            tens--;
            fives--;
        } else if (fives >= 3) fives -= 3;
        else return `stuck at bill ${i + 1}`;
    }
    return `everyone served, ${fives} fives and ${tens} tens left`;
}

console.log(change([5, 5, 5, 5, 10, 20, 10, 10]));

// everyone served, 0 fives and 2 tens left

using System;

class Program {
    static string Change(int[] bills) {              // every lemonade costs 5; give change from what's in the till
        int fives = 0, tens = 0;
        for (int i = 0; i < bills.Length; i++) {
            int bill = bills[i];
            if (bill == 5) fives++;
            else if (bill == 10) {
                if (fives == 0) return $"stuck at bill {i + 1}";
                fives--;
                tens++;
            } else if (tens > 0 && fives > 0) {      // a 20: a 10 and a 5 back keeps the 5s, which more bills need
                tens--;
                fives--;
            } else if (fives >= 3) fives -= 3;
            else return $"stuck at bill {i + 1}";
        }
        return $"everyone served, {fives} fives and {tens} tens left";
    }

    static void Main() {
        Console.WriteLine(Change(new[] { 5, 5, 5, 5, 10, 20, 10, 10 }));
    }
}

// everyone served, 0 fives and 2 tens left

package main

import "fmt"

func change(bills []int) string { // every lemonade costs 5; give change from what's in the till
	fives, tens := 0, 0
	for i, bill := range bills {
		switch {
		case bill == 5:
			fives++
		case bill == 10:
			if fives == 0 {
				return fmt.Sprintf("stuck at bill %d", i+1)
			}
			fives--
			tens++
		case tens > 0 && fives > 0: // a 20: a 10 and a 5 back keeps the 5s, which more bills need
			tens--
			fives--
		case fives >= 3:
			fives -= 3
		default:
			return fmt.Sprintf("stuck at bill %d", i+1)
		}
	}
	return fmt.Sprintf("everyone served, %d fives and %d tens left", fives, tens)
}

func main() {
	fmt.Println(change([]int{5, 5, 5, 5, 10, 20, 10, 10}))
}

// everyone served, 0 fives and 2 tens left

coins = [1000, 500, 100, 50, 20, 10, 5, 2, 1]   # India's coins and notes, largest first
amount, paid, left = 1988, [], 1988
for c in coins:
    while left >= c:                           # the largest that still fits, as many times as it fits
        paid.append(c)
        left -= c
print(f"{amount}:", " ".join(map(str, paid)), f"({len(paid)} in all)")

# 1988: 1000 500 100 100 100 100 50 20 10 5 2 1 (12 in all)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] coins = {1000, 500, 100, 50, 20, 10, 5, 2, 1};   // India's coins and notes, largest first
        int amount = 1988, left = amount;
        List<String> paid = new ArrayList<>();
        for (int c : coins) {
            while (left >= c) {                      // the largest that still fits, as many times as it fits
                paid.add(String.valueOf(c));
                left -= c;
            }
        }
        System.out.println(amount + ": " + String.join(" ", paid) + " (" + paid.size() + " in all)");
    }
}

// 1988: 1000 500 100 100 100 100 50 20 10 5 2 1 (12 in all)

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> coins = {1000, 500, 100, 50, 20, 10, 5, 2, 1};   // India's coins and notes, largest first
    int amount = 1988, left = amount;
    vector<int> paid;
    for (int c : coins) {
        while (left >= c) {                              // the largest that still fits, as many times as it fits
            paid.push_back(c);
            left -= c;
        }
    }
    cout << amount << ":";
    for (int c : paid) cout << " " << c;
    cout << " (" << paid.size() << " in all)\n";
}

// 1988: 1000 500 100 100 100 100 50 20 10 5 2 1 (12 in all)

const coins = [1000, 500, 100, 50, 20, 10, 5, 2, 1];   // India's coins and notes, largest first
const amount = 1988, paid = [];
let left = amount;
for (const c of coins) {
    while (left >= c) {                           // the largest that still fits, as many times as it fits
        paid.push(c);
        left -= c;
    }
}
console.log(`${amount}: ${paid.join(" ")} (${paid.length} in all)`);

// 1988: 1000 500 100 100 100 100 50 20 10 5 2 1 (12 in all)

const coins: number[] = [1000, 500, 100, 50, 20, 10, 5, 2, 1];   // India's coins and notes, largest first
const amount = 1988, paid: number[] = [];
let left = amount;
for (const c of coins) {
    while (left >= c) {                           // the largest that still fits, as many times as it fits
        paid.push(c);
        left -= c;
    }
}
console.log(`${amount}: ${paid.join(" ")} (${paid.length} in all)`);

// 1988: 1000 500 100 100 100 100 50 20 10 5 2 1 (12 in all)

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] coins = { 1000, 500, 100, 50, 20, 10, 5, 2, 1 };   // India's coins and notes, largest first
        int amount = 1988, left = amount;
        var paid = new List<int>();
        foreach (int c in coins) {
            while (left >= c) {                      // the largest that still fits, as many times as it fits
                paid.Add(c);
                left -= c;
            }
        }
        Console.WriteLine($"{amount}: {string.Join(" ", paid)} ({paid.Count} in all)");
    }
}

// 1988: 1000 500 100 100 100 100 50 20 10 5 2 1 (12 in all)

package main

import (
	"fmt"
	"strings"
)

func main() {
	coins := []int{1000, 500, 100, 50, 20, 10, 5, 2, 1} // India's coins and notes, largest first
	amount, left := 1988, 1988
	var paid []string
	for _, c := range coins {
		for left >= c { // the largest that still fits, as many times as it fits
			paid = append(paid, fmt.Sprint(c))
			left -= c
		}
	}
	fmt.Printf("%d: %s (%d in all)\n", amount, strings.Join(paid, " "), len(paid))
}

// 1988: 1000 500 100 100 100 100 50 20 10 5 2 1 (12 in all)

difficulty, profit, workers = [7, 3, 9, 1, 4, 6], [12, 5, 30, 2, 8, 1], [2, 5, 10, 8, 1]
jobs = sorted(zip(difficulty, profit))         # easiest job first
best, j, earned = 0, 0, []
for w in sorted(workers):                      # weakest worker first
    while j < len(jobs) and jobs[j][0] <= w:
        best = max(best, jobs[j][1])           # the best pay among every job this worker can do
        j += 1
    earned.append(best)
print("workers", " ".join(map(str, sorted(workers))), "earn", " ".join(map(str, earned)) + f": {sum(earned)} in all")

# workers 1 2 5 8 10 earn 2 2 8 12 30: 54 in all

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] difficulty = {7, 3, 9, 1, 4, 6}, profit = {12, 5, 30, 2, 8, 1}, workers = {2, 5, 10, 8, 1};
        int n = difficulty.length;
        int[][] jobs = new int[n][];
        for (int i = 0; i < n; i++) jobs[i] = new int[] {difficulty[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));   // easiest first
        Arrays.sort(workers);                        // weakest worker first
        int best = 0, j = 0, total = 0;
        StringJoiner who = new StringJoiner(" "), earned = new StringJoiner(" ");
        for (int w : workers) {
            while (j < n && jobs[j][0] <= w) best = Math.max(best, jobs[j++][1]);   // the best pay this worker can get
            who.add(String.valueOf(w));
            earned.add(String.valueOf(best));
            total += best;
        }
        System.out.println("workers " + who + " earn " + earned + ": " + total + " in all");
    }
}

// workers 1 2 5 8 10 earn 2 2 8 12 30: 54 in all

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> difficulty = {7, 3, 9, 1, 4, 6}, profit = {12, 5, 30, 2, 8, 1}, workers = {2, 5, 10, 8, 1};
    vector<pair<int, int>> jobs;
    for (size_t i = 0; i < difficulty.size(); i++) jobs.push_back({difficulty[i], profit[i]});
    sort(jobs.begin(), jobs.end());                      // easiest job first
    sort(workers.begin(), workers.end());                // weakest worker first
    int best = 0, total = 0;
    size_t j = 0;
    string who, earned;
    for (int w : workers) {
        while (j < jobs.size() && jobs[j].first <= w) best = max(best, jobs[j++].second);   // the best pay this worker can get
        who += (who.empty() ? "" : " ") + to_string(w);
        earned += (earned.empty() ? "" : " ") + to_string(best);
        total += best;
    }
    cout << "workers " << who << " earn " << earned << ": " << total << " in all\n";
}

// workers 1 2 5 8 10 earn 2 2 8 12 30: 54 in all

const difficulty = [7, 3, 9, 1, 4, 6], profit = [12, 5, 30, 2, 8, 1], workers = [2, 5, 10, 8, 1];
const jobs = difficulty.map((d, i) => [d, profit[i]]).sort((a, b) => a[0] - b[0] || a[1] - b[1]);   // easiest first
workers.sort((a, b) => a - b);                    // weakest worker first
let best = 0, j = 0;
const earned = [];
for (const w of workers) {
    while (j < jobs.length && jobs[j][0] <= w) best = Math.max(best, jobs[j++][1]);   // the best pay this worker can get
    earned.push(best);
}
console.log(`workers ${workers.join(" ")} earn ${earned.join(" ")}: ${earned.reduce((s, x) => s + x, 0)} in all`);

// workers 1 2 5 8 10 earn 2 2 8 12 30: 54 in all

const difficulty = [7, 3, 9, 1, 4, 6], profit = [12, 5, 30, 2, 8, 1], workers = [2, 5, 10, 8, 1];
const jobs: number[][] = difficulty.map((d, i) => [d, profit[i]]).sort((a, b) => a[0] - b[0] || a[1] - b[1]);   // easiest first
workers.sort((a, b) => a - b);                    // weakest worker first
let best = 0, j = 0;
const earned: number[] = [];
for (const w of workers) {
    while (j < jobs.length && jobs[j][0] <= w) best = Math.max(best, jobs[j++][1]);   // the best pay this worker can get
    earned.push(best);
}
console.log(`workers ${workers.join(" ")} earn ${earned.join(" ")}: ${earned.reduce((s, x) => s + x, 0)} in all`);

// workers 1 2 5 8 10 earn 2 2 8 12 30: 54 in all

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static void Main() {
        int[] difficulty = { 7, 3, 9, 1, 4, 6 }, profit = { 12, 5, 30, 2, 8, 1 }, workers = { 2, 5, 10, 8, 1 };
        var jobs = difficulty.Select((d, i) => (d, p: profit[i])).OrderBy(x => x.d).ThenBy(x => x.p).ToList();   // easiest first
        Array.Sort(workers);                         // weakest worker first
        int best = 0, j = 0;
        var earned = new List<int>();
        foreach (int w in workers) {
            while (j < jobs.Count && jobs[j].d <= w) best = Math.Max(best, jobs[j++].p);   // the best pay this worker can get
            earned.Add(best);
        }
        Console.WriteLine($"workers {string.Join(" ", workers)} earn {string.Join(" ", earned)}: {earned.Sum()} in all");
    }
}

// workers 1 2 5 8 10 earn 2 2 8 12 30: 54 in all

package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
	difficulty, profit, workers := []int{7, 3, 9, 1, 4, 6}, []int{12, 5, 30, 2, 8, 1}, []int{2, 5, 10, 8, 1}
	jobs := make([][2]int, len(difficulty))
	for i := range difficulty {
		jobs[i] = [2]int{difficulty[i], profit[i]}
	}
	sort.Slice(jobs, func(a, b int) bool { // easiest job first
		if jobs[a][0] != jobs[b][0] {
			return jobs[a][0] < jobs[b][0]
		}
		return jobs[a][1] < jobs[b][1]
	})
	sort.Ints(workers) // weakest worker first
	best, j, total := 0, 0, 0
	var who, earned []string
	for _, w := range workers {
		for j < len(jobs) && jobs[j][0] <= w { // the best pay this worker can get
			if jobs[j][1] > best {
				best = jobs[j][1]
			}
			j++
		}
		who = append(who, fmt.Sprint(w))
		earned = append(earned, fmt.Sprint(best))
		total += best
	}
	fmt.Printf("workers %s earn %s: %d in all\n", strings.Join(who, " "), strings.Join(earned, " "), total)
}

// workers 1 2 5 8 10 earn 2 2 8 12 30: 54 in all

items, room = [(6, 30), (5, 20), (5, 20)], 10   # (weight, value) and the knapsack's capacity
by_ratio = sorted(items, key=lambda it: it[1] / it[0], reverse=True)

value, left = 0.0, room                        # fractions allowed: best value per weight first, the last one cut
for w, v in by_ratio:
    take = min(w, left)
    value += v * take / w
    left -= take

whole, left = 0, room                          # whole items, the same order: take each that still fits
for w, v in by_ratio:
    if w <= left:
        whole, left = whole + v, left - w

best = [0] * (room + 1)                        # 0/1 knapsack: the most value for every capacity, item by item
for w, v in items:
    for c in range(room, w - 1, -1):
        best[c] = max(best[c], best[c - w] + v)
print(f"fractional, best ratio first: {value:.2f} | whole items, best ratio first: {whole} | whole items, the best: {best[room]}")

# fractional, best ratio first: 46.00 | whole items, best ratio first: 30 | whole items, the best: 40

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] items = {{6, 30}, {5, 20}, {5, 20}};   // {weight, value}
        int room = 10;
        Integer[] order = {0, 1, 2};
        Arrays.sort(order, (a, b) -> Double.compare((double) items[b][1] / items[b][0], (double) items[a][1] / items[a][0]));

        double value = 0;                            // fractions allowed: best value per weight first, the last one cut
        int left = room;
        for (int i : order) {
            int take = Math.min(items[i][0], left);
            value += (double) items[i][1] * take / items[i][0];
            left -= take;
        }

        int whole = 0;                               // whole items, the same order: take each that still fits
        left = room;
        for (int i : order) {
            if (items[i][0] <= left) {
                whole += items[i][1];
                left -= items[i][0];
            }
        }

        int[] best = new int[room + 1];              // 0/1 knapsack: the most value for every capacity, item by item
        for (int[] it : items)
            for (int c = room; c >= it[0]; c--) best[c] = Math.max(best[c], best[c - it[0]] + it[1]);
        System.out.println(String.format(Locale.ROOT, "fractional, best ratio first: %.2f", value)
                + " | whole items, best ratio first: " + whole + " | whole items, the best: " + best[room]);
    }
}

// fractional, best ratio first: 46.00 | whole items, best ratio first: 30 | whole items, the best: 40

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<pair<int, int>> items = {{6, 30}, {5, 20}, {5, 20}};   // (weight, value)
    int room = 10;
    vector<int> order = {0, 1, 2};
    stable_sort(order.begin(), order.end(), [&](int a, int b) {
        return (double) items[a].second / items[a].first > (double) items[b].second / items[b].first;
    });

    double value = 0;                                    // fractions allowed: best value per weight first, the last one cut
    int left = room;
    for (int i : order) {
        int take = min(items[i].first, left);
        value += (double) items[i].second * take / items[i].first;
        left -= take;
    }

    int whole = 0;                                       // whole items, the same order: take each that still fits
    left = room;
    for (int i : order) {
        if (items[i].first <= left) {
            whole += items[i].second;
            left -= items[i].first;
        }
    }

    vector<int> best(room + 1, 0);                       // 0/1 knapsack: the most value for every capacity, item by item
    for (auto [w, v] : items)
        for (int c = room; c >= w; c--) best[c] = max(best[c], best[c - w] + v);
    printf("fractional, best ratio first: %.2f | whole items, best ratio first: %d | whole items, the best: %d\n", value,
           whole, best[room]);
}

// fractional, best ratio first: 46.00 | whole items, best ratio first: 30 | whole items, the best: 40

const items = [[6, 30], [5, 20], [5, 20]], room = 10;   // [weight, value] and the knapsack's capacity
const byRatio = [...items].sort((a, b) => b[1] / b[0] - a[1] / a[0]);

let value = 0, left = room;                       // fractions allowed: best value per weight first, the last one cut
for (const [w, v] of byRatio) {
    const take = Math.min(w, left);
    value += v * take / w;
    left -= take;
}

let whole = 0;                                    // whole items, the same order: take each that still fits
left = room;
for (const [w, v] of byRatio) {
    if (w <= left) {
        whole += v;
        left -= w;
    }
}

const best = new Array(room + 1).fill(0);         // 0/1 knapsack: the most value for every capacity, item by item
for (const [w, v] of items) for (let c = room; c >= w; c--) best[c] = Math.max(best[c], best[c - w] + v);
console.log(`fractional, best ratio first: ${value.toFixed(2)} | whole items, best ratio first: ${whole} | whole items, the best: ${best[room]}`);

// fractional, best ratio first: 46.00 | whole items, best ratio first: 30 | whole items, the best: 40

const items: [number, number][] = [[6, 30], [5, 20], [5, 20]];   // [weight, value]
const room = 10;
const byRatio = [...items].sort((a, b) => b[1] / b[0] - a[1] / a[0]);

let value = 0, left = room;                       // fractions allowed: best value per weight first, the last one cut
for (const [w, v] of byRatio) {
    const take = Math.min(w, left);
    value += v * take / w;
    left -= take;
}

let whole = 0;                                    // whole items, the same order: take each that still fits
left = room;
for (const [w, v] of byRatio) {
    if (w <= left) {
        whole += v;
        left -= w;
    }
}

const best: number[] = new Array(room + 1).fill(0);   // 0/1 knapsack: the most value for every capacity, item by item
for (const [w, v] of items) for (let c = room; c >= w; c--) best[c] = Math.max(best[c], best[c - w] + v);
console.log(`fractional, best ratio first: ${value.toFixed(2)} | whole items, best ratio first: ${whole} | whole items, the best: ${best[room]}`);

// fractional, best ratio first: 46.00 | whole items, best ratio first: 30 | whole items, the best: 40

using System;
using System.Globalization;
using System.Linq;

class Program {
    static void Main() {
        (int w, int v)[] items = { (6, 30), (5, 20), (5, 20) };   // (weight, value)
        int room = 10;
        var byRatio = items.OrderByDescending(it => (double) it.v / it.w).ToArray();

        double value = 0;                            // fractions allowed: best value per weight first, the last one cut
        int left = room;
        foreach (var (w, v) in byRatio) {
            int take = Math.Min(w, left);
            value += (double) v * take / w;
            left -= take;
        }

        int whole = 0;                               // whole items, the same order: take each that still fits
        left = room;
        foreach (var (w, v) in byRatio) {
            if (w <= left) {
                whole += v;
                left -= w;
            }
        }

        var best = new int[room + 1];                // 0/1 knapsack: the most value for every capacity, item by item
        foreach (var (w, v) in items)
            for (int c = room; c >= w; c--) best[c] = Math.Max(best[c], best[c - w] + v);
        Console.WriteLine("fractional, best ratio first: " + value.ToString("F2", CultureInfo.InvariantCulture)
            + $" | whole items, best ratio first: {whole} | whole items, the best: {best[room]}");
    }
}

// fractional, best ratio first: 46.00 | whole items, best ratio first: 30 | whole items, the best: 40

package main

import (
	"fmt"
	"sort"
)

func main() {
	items := [][2]int{{6, 30}, {5, 20}, {5, 20}} // {weight, value}
	room := 10
	byRatio := append([][2]int{}, items...)
	sort.SliceStable(byRatio, func(a, b int) bool {
		return float64(byRatio[a][1])/float64(byRatio[a][0]) > float64(byRatio[b][1])/float64(byRatio[b][0])
	})

	value, left := 0.0, room // fractions allowed: best value per weight first, the last one cut
	for _, it := range byRatio {
		take := it[0]
		if left < take {
			take = left
		}
		value += float64(it[1]*take) / float64(it[0])
		left -= take
	}

	whole := 0 // whole items, the same order: take each that still fits
	left = room
	for _, it := range byRatio {
		if it[0] <= left {
			whole += it[1]
			left -= it[0]
		}
	}

	best := make([]int, room+1) // 0/1 knapsack: the most value for every capacity, item by item
	for _, it := range items {
		for c := room; c >= it[0]; c-- {
			if best[c-it[0]]+it[1] > best[c] {
				best[c] = best[c-it[0]] + it[1]
			}
		}
	}
	fmt.Printf("fractional, best ratio first: %.2f | whole items, best ratio first: %d | whole items, the best: %d\n", value, whole, best[room])
}

// fractional, best ratio first: 46.00 | whole items, best ratio first: 30 | whole items, the best: 40

def fed(greed, cookies, biggest_first):        # Assign Cookies, smallest greed first
    greed, left, count = sorted(greed), sorted(cookies), 0
    for g in greed:
        fits = [c for c in left if c >= g]
        if fits:                               # the mistake hands over the biggest left; the fix, the smallest that's enough
            pick = max(left) if biggest_first else min(fits)
            if pick >= g:
                left.remove(pick)
                count += 1
    return count


def served(bills, three_fives_first):          # Lemonade Change
    fives = tens = 0
    for i, bill in enumerate(bills):
        if bill == 5:
            fives += 1
        elif bill == 10:
            if not fives:
                return f"stuck at bill {i + 1}"
            fives, tens = fives - 1, tens + 1
        elif three_fives_first and fives >= 3:
            fives -= 3
        elif tens and fives:
            tens, fives = tens - 1, fives - 1
        elif fives >= 3:
            fives -= 3
        else:
            return f"stuck at bill {i + 1}"
    return "everyone served"


greed, cookies, bills = [4, 2, 7, 1, 5], [3, 6, 1, 5, 2, 2], [5, 5, 5, 5, 10, 20, 10, 10]
print(f"the biggest cookie first: fed {fed(greed, cookies, True)}, where the smallest that's enough feeds {fed(greed, cookies, False)}")
print(f"three 5s back for a 20: {served(bills, True)}, where a 10 and a 5 first: {served(bills, False)}")

# the biggest cookie first: fed 2, where the smallest that's enough feeds 4
# three 5s back for a 20: stuck at bill 7, where a 10 and a 5 first: everyone served

import java.util.*;

public class Main {
    static int fed(int[] greed, int[] cookies, boolean biggestFirst) {   // Assign Cookies, smallest greed first
        int[] g = greed.clone();
        Arrays.sort(g);
        List<Integer> left = new ArrayList<>();
        for (int c : cookies) left.add(c);
        Collections.sort(left);
        int count = 0;
        for (int x : g) {
            int pick = -1;
            for (int c : left) if (c >= x && (pick < 0 || c < pick)) pick = c;   // the smallest that's enough
            if (pick < 0) continue;
            if (biggestFirst) pick = left.get(left.size() - 1);   // the mistake hands over the biggest left
            if (pick >= x) {
                left.remove(Integer.valueOf(pick));
                count++;
            }
        }
        return count;
    }

    static String served(int[] bills, boolean threeFivesFirst) {   // Lemonade Change
        int fives = 0, tens = 0;
        for (int i = 0; i < bills.length; i++) {
            int bill = bills[i];
            if (bill == 5) fives++;
            else if (bill == 10) {
                if (fives == 0) return "stuck at bill " + (i + 1);
                fives--;
                tens++;
            } else if (threeFivesFirst && fives >= 3) fives -= 3;
            else if (tens > 0 && fives > 0) {
                tens--;
                fives--;
            } else if (fives >= 3) fives -= 3;
            else return "stuck at bill " + (i + 1);
        }
        return "everyone served";
    }

    public static void main(String[] args) {
        int[] greed = {4, 2, 7, 1, 5}, cookies = {3, 6, 1, 5, 2, 2}, bills = {5, 5, 5, 5, 10, 20, 10, 10};
        System.out.println("the biggest cookie first: fed " + fed(greed, cookies, true) + ", where the smallest that's enough feeds "
                + fed(greed, cookies, false));
        System.out.println("three 5s back for a 20: " + served(bills, true) + ", where a 10 and a 5 first: " + served(bills, false));
    }
}

// the biggest cookie first: fed 2, where the smallest that's enough feeds 4
// three 5s back for a 20: stuck at bill 7, where a 10 and a 5 first: everyone served

#include <bits/stdc++.h>
using namespace std;

int fed(vector<int> greed, vector<int> left, bool biggestFirst) {   // Assign Cookies, smallest greed first
    sort(greed.begin(), greed.end());
    sort(left.begin(), left.end());
    int count = 0;
    for (int g : greed) {
        int pick = -1;
        for (int c : left) if (c >= g && (pick < 0 || c < pick)) pick = c;   // the smallest that's enough
        if (pick < 0) continue;
        if (biggestFirst) pick = left.back();                // the mistake hands over the biggest left
        if (pick >= g) {
            left.erase(find(left.begin(), left.end(), pick));
            count++;
        }
    }
    return count;
}

string served(const vector<int>& bills, bool threeFivesFirst) {   // Lemonade Change
    int fives = 0, tens = 0;
    for (size_t i = 0; i < bills.size(); i++) {
        int bill = bills[i];
        if (bill == 5) fives++;
        else if (bill == 10) {
            if (fives == 0) return "stuck at bill " + to_string(i + 1);
            fives--;
            tens++;
        } else if (threeFivesFirst && fives >= 3) fives -= 3;
        else if (tens > 0 && fives > 0) {
            tens--;
            fives--;
        } else if (fives >= 3) fives -= 3;
        else return "stuck at bill " + to_string(i + 1);
    }
    return "everyone served";
}

int main() {
    vector<int> greed = {4, 2, 7, 1, 5}, cookies = {3, 6, 1, 5, 2, 2}, bills = {5, 5, 5, 5, 10, 20, 10, 10};
    cout << "the biggest cookie first: fed " << fed(greed, cookies, true) << ", where the smallest that's enough feeds "
         << fed(greed, cookies, false) << "\n";
    cout << "three 5s back for a 20: " << served(bills, true) << ", where a 10 and a 5 first: " << served(bills, false) << "\n";
}

// the biggest cookie first: fed 2, where the smallest that's enough feeds 4
// three 5s back for a 20: stuck at bill 7, where a 10 and a 5 first: everyone served

function fed(greed, cookies, biggestFirst) {       // Assign Cookies, smallest greed first
    const g = [...greed].sort((a, b) => a - b), left = [...cookies].sort((a, b) => a - b);
    let count = 0;
    for (const x of g) {
        const fits = left.filter((c) => c >= x);
        if (!fits.length) continue;
        const pick = biggestFirst ? left[left.length - 1] : Math.min(...fits);   // the mistake: the biggest left
        if (pick >= x) {
            left.splice(left.indexOf(pick), 1);
            count++;
        }
    }
    return count;
}

function served(bills, threeFivesFirst) {          // Lemonade Change
    let fives = 0, tens = 0;
    for (let i = 0; i < bills.length; i++) {
        const bill = bills[i];
        if (bill === 5) fives++;
        else if (bill === 10) {
            if (fives === 0) return `stuck at bill ${i + 1}`;
            fives--;
            tens++;
        } else if (threeFivesFirst && fives >= 3) fives -= 3;
        else if (tens > 0 && fives > 0) {
            tens--;
            fives--;
        } else if (fives >= 3) fives -= 3;
        else return `stuck at bill ${i + 1}`;
    }
    return "everyone served";
}

const greed = [4, 2, 7, 1, 5], cookies = [3, 6, 1, 5, 2, 2], bills = [5, 5, 5, 5, 10, 20, 10, 10];
console.log(`the biggest cookie first: fed ${fed(greed, cookies, true)}, where the smallest that's enough feeds ${fed(greed, cookies, false)}`);
console.log(`three 5s back for a 20: ${served(bills, true)}, where a 10 and a 5 first: ${served(bills, false)}`);

// the biggest cookie first: fed 2, where the smallest that's enough feeds 4
// three 5s back for a 20: stuck at bill 7, where a 10 and a 5 first: everyone served

function fed(greed: number[], cookies: number[], biggestFirst: boolean): number {   // Assign Cookies, smallest greed first
    const g = [...greed].sort((a, b) => a - b), left = [...cookies].sort((a, b) => a - b);
    let count = 0;
    for (const x of g) {
        const fits = left.filter((c) => c >= x);
        if (!fits.length) continue;
        const pick = biggestFirst ? left[left.length - 1] : Math.min(...fits);   // the mistake: the biggest left
        if (pick >= x) {
            left.splice(left.indexOf(pick), 1);
            count++;
        }
    }
    return count;
}

function served(bills: number[], threeFivesFirst: boolean): string {   // Lemonade Change
    let fives = 0, tens = 0;
    for (let i = 0; i < bills.length; i++) {
        const bill = bills[i];
        if (bill === 5) fives++;
        else if (bill === 10) {
            if (fives === 0) return `stuck at bill ${i + 1}`;
            fives--;
            tens++;
        } else if (threeFivesFirst && fives >= 3) fives -= 3;
        else if (tens > 0 && fives > 0) {
            tens--;
            fives--;
        } else if (fives >= 3) fives -= 3;
        else return `stuck at bill ${i + 1}`;
    }
    return "everyone served";
}

const greed = [4, 2, 7, 1, 5], cookies = [3, 6, 1, 5, 2, 2], bills = [5, 5, 5, 5, 10, 20, 10, 10];
console.log(`the biggest cookie first: fed ${fed(greed, cookies, true)}, where the smallest that's enough feeds ${fed(greed, cookies, false)}`);
console.log(`three 5s back for a 20: ${served(bills, true)}, where a 10 and a 5 first: ${served(bills, false)}`);

// the biggest cookie first: fed 2, where the smallest that's enough feeds 4
// three 5s back for a 20: stuck at bill 7, where a 10 and a 5 first: everyone served

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static int Fed(int[] greed, int[] cookies, bool biggestFirst) {   // Assign Cookies, smallest greed first
        var g = greed.OrderBy(x => x).ToArray();
        var left = cookies.OrderBy(x => x).ToList();
        int count = 0;
        foreach (int x in g) {
            var fits = left.Where(c => c >= x).ToList();
            if (fits.Count == 0) continue;
            int pick = biggestFirst ? left[left.Count - 1] : fits.Min();   // the mistake: the biggest left
            if (pick >= x) {
                left.Remove(pick);
                count++;
            }
        }
        return count;
    }

    static string Served(int[] bills, bool threeFivesFirst) {   // Lemonade Change
        int fives = 0, tens = 0;
        for (int i = 0; i < bills.Length; i++) {
            int bill = bills[i];
            if (bill == 5) fives++;
            else if (bill == 10) {
                if (fives == 0) return $"stuck at bill {i + 1}";
                fives--;
                tens++;
            } else if (threeFivesFirst && fives >= 3) fives -= 3;
            else if (tens > 0 && fives > 0) {
                tens--;
                fives--;
            } else if (fives >= 3) fives -= 3;
            else return $"stuck at bill {i + 1}";
        }
        return "everyone served";
    }

    static void Main() {
        int[] greed = { 4, 2, 7, 1, 5 }, cookies = { 3, 6, 1, 5, 2, 2 }, bills = { 5, 5, 5, 5, 10, 20, 10, 10 };
        Console.WriteLine($"the biggest cookie first: fed {Fed(greed, cookies, true)}, where the smallest that's enough feeds {Fed(greed, cookies, false)}");
        Console.WriteLine($"three 5s back for a 20: {Served(bills, true)}, where a 10 and a 5 first: {Served(bills, false)}");
    }
}

// the biggest cookie first: fed 2, where the smallest that's enough feeds 4
// three 5s back for a 20: stuck at bill 7, where a 10 and a 5 first: everyone served

package main

import (
	"fmt"
	"sort"
)

func fed(greed, cookies []int, biggestFirst bool) int { // Assign Cookies, smallest greed first
	g := append([]int{}, greed...)
	left := append([]int{}, cookies...)
	sort.Ints(g)
	sort.Ints(left)
	count := 0
	for _, x := range g {
		pick := -1
		for _, c := range left {
			if c >= x && (pick < 0 || c < pick) {
				pick = c // the smallest that's enough
			}
		}
		if pick < 0 {
			continue
		}
		if biggestFirst {
			pick = left[len(left)-1] // the mistake hands over the biggest left
		}
		if pick >= x {
			for k, c := range left {
				if c == pick {
					left = append(left[:k], left[k+1:]...)
					break
				}
			}
			count++
		}
	}
	return count
}

func served(bills []int, threeFivesFirst bool) string { // Lemonade Change
	fives, tens := 0, 0
	for i, bill := range bills {
		switch {
		case bill == 5:
			fives++
		case bill == 10:
			if fives == 0 {
				return fmt.Sprintf("stuck at bill %d", i+1)
			}
			fives--
			tens++
		case threeFivesFirst && fives >= 3:
			fives -= 3
		case tens > 0 && fives > 0:
			tens--
			fives--
		case fives >= 3:
			fives -= 3
		default:
			return fmt.Sprintf("stuck at bill %d", i+1)
		}
	}
	return "everyone served"
}

func main() {
	greed, cookies, bills := []int{4, 2, 7, 1, 5}, []int{3, 6, 1, 5, 2, 2}, []int{5, 5, 5, 5, 10, 20, 10, 10}
	fmt.Printf("the biggest cookie first: fed %d, where the smallest that's enough feeds %d\n", fed(greed, cookies, true), fed(greed, cookies, false))
	fmt.Printf("three 5s back for a 20: %s, where a 10 and a 5 first: %s\n", served(bills, true), served(bills, false))
}

// the biggest cookie first: fed 2, where the smallest that's enough feeds 4
// three 5s back for a 20: stuck at bill 7, where a 10 and a 5 first: everyone served