#include <iostream>
#include <cstdio>

using namespace std;

class Naczynie {
    protected:
        double Pojemnosc;

    public:
        Naczynie (double _Pojemnosc) {
            Pojemnosc = _Pojemnosc;
        }

};

class Garnek : public Naczynie {
    protected:
        char Uszy;
        bool Pokrywka;

    public:
        double GetPojemnosc () {
            return Pojemnosc;
        }

        bool GetPokrywka () {
            return Pokrywka;
        }

        Garnek (double _Pojemnosc, char _Uszy, bool _Pokrywka): Naczynie (_Pojemnosc) {
            Uszy = _Uszy;
            Pokrywka = _Pokrywka;
        }

        // Domyślny konstruktor, bo g++ chciał go dla użycia `new Garnek[n]`
        Garnek (): Garnek (0, '0', false) { }

        // Wypisuje atrybuty garnka
        void Print () {
            cout << "Garnek: " << Pojemnosc << "mL, Pokrywka: " << (Pokrywka ? "Tak" : "Nie") << ", Uszy: " << Uszy << endl;
        }

};

class Przepis {
    friend bool SprawdzPrzepis (Garnek*, int, Przepis&);
    protected:
        Garnek *Garnki;
        int IloscGarnkow;

    public:

        Przepis (Garnek *_Garnki, int _IloscGarnkow) {
            Garnki = _Garnki;
            IloscGarnkow = _IloscGarnkow;
        }

};

bool SprawdzPrzepis (Garnek *garnki, int iloscGarnkow, Przepis &przepis) {
    bool *uzyteGarnki = new bool[iloscGarnkow];
    for (int i = 0; i < iloscGarnkow; ++i) {
        uzyteGarnki[i] = false;
    }

    // Dla każdego garnka z przepisu znajdź najmniejszy garnek który ma
    // wystarczającą objętość.

    // Najpierw dobierz garnki z przepisu wymagające pokrywki
    for (int i = 0; i < przepis.IloscGarnkow; ++i) {
        if (!przepis.Garnki[i].GetPokrywka ()) {
            continue;
        }

        // Znajdź najmniejszy pasujący, nieużyty garnek z listy
        double lowestVol = 0;
        int lowestVolIndex = -1;
        for (int j = 0; j < iloscGarnkow; ++j) {
            // Garnek wymaga pokrywki
            if (!garnki[j].GetPokrywka ()) {
                continue;
            }

            // Nie sprawdzaj już użytych garnków
            if (uzyteGarnki[j]) {
                continue;
            }

            double thisVol = garnki[j].GetPojemnosc ();

            // Jeżeli pierwszy pasujący garnek lub mniejszy pasujący garnek, wpisz go
            if ((thisVol < lowestVol || lowestVolIndex < 0) && thisVol >= przepis.Garnki[i].GetPojemnosc ()) {
                lowestVol = thisVol;
                lowestVolIndex = j;
            }
        }

        if (lowestVolIndex < 0) {
            // Nie znaleziono pasującego garnka
            return false;
        } else {
            // Znaleziono pasujący garnek. Oznacz go jako użytego
            uzyteGarnki[lowestVolIndex] = true;
        }
    }

    // Następnie pozostałe wymagane garnki, bez pokrywek
    for (int i = 0; i < przepis.IloscGarnkow; ++i) {
        if (przepis.Garnki[i].GetPokrywka ()) {
            continue;
        }

        // Znajdź najmniejszy pasujący, nieużyty garnek z listy
        double lowestVol = 0;
        int lowestVolIndex = -1;
        for (int j = 0; j < iloscGarnkow; ++j) {
            // Nie sprawdzaj już użytych garnków
            if (uzyteGarnki[j]) {
                continue;
            }

            double thisVol = garnki[j].GetPojemnosc ();

            // Jeżeli pierwszy garnek bez pokrywki lub mniejszy pasujący garnek, wpisz go
            if ((thisVol < lowestVol || lowestVolIndex < 0) && thisVol >= przepis.Garnki[i].GetPojemnosc ()) {
                lowestVol = thisVol;
                lowestVolIndex = j;
            }
        }

        if (lowestVolIndex < 0) {
            // Nie znaleziono pasującego garnka
            return false;
        } else {
            // Znaleziono pasujący garnek. Oznacz go jako użytego
            uzyteGarnki[lowestVolIndex] = true;
        }
    }

    // Jeżeli do tego punktu nie natrafiono na `return false`, to znaczy że
    // znaleziono wszystkie wymagane garnki

    delete uzyteGarnki;
    return true;
}

int main () {
    srand (time (NULL));

    const int ILOSC_GARNKOW_PRZEPIS = 3;
    Garnek *garnkiPrzepis = new Garnek[ILOSC_GARNKOW_PRZEPIS] {
        Garnek { 1000, 'U', false },
        Garnek {  600, 'U', false },
        Garnek {  800, 'U',  true }
    };

    Przepis przepis = Przepis { garnkiPrzepis, ILOSC_GARNKOW_PRZEPIS };

    // Losowa ilość garnków w przedziale <2, 4>
    int iloscGarnkow = (rand () % 3) + 2;

    Garnek *garnki = new Garnek[iloscGarnkow];
    for (int i = 0; i < iloscGarnkow; ++i) {
        // Losowy garnek o pojemności <100, 1400>. 50% szans na pokrywkę
        garnki[i] = Garnek { (double) ((rand () % 1301) + 100), 'U', rand () & 1 };
    }

    cout << endl;
    cout << "==== Przepis wymaga garnkow: ====" << endl;
    for (int i = 0; i < ILOSC_GARNKOW_PRZEPIS; ++i) {
        garnkiPrzepis[i].Print ();
    }

    cout << endl;
    cout << "==== Posiadane garnki: ====" << endl;


    for (int i = 0; i < iloscGarnkow; ++i) {
        garnki[i].Print ();
    }

    cout << endl;
    if (SprawdzPrzepis (garnki, iloscGarnkow, przepis)) {
        cout << "Przepis ten da sie wykonac" << endl;
    } else {
        cout << "Przepisu tego nie da sie wykonac" << endl;
    }
    cout << endl;


    delete[] garnki, garnkiPrzepis;
}