#ifndef SHIPWRECK_HH
#define SHIPWRECK_HH

#include <algorithm>
#include <cassert>
#include <ostream>
#include <tuple>

using number_t = unsigned int;

template <number_t Cannon, number_t Mast, number_t Oar>
struct ShipGear {
    static const number_t cannon = Cannon;
    static const number_t mast = Mast;
    static const number_t oar = Oar;
};

using Cannon = ShipGear<1, 0, 0>;
using Mast = ShipGear<0, 1, 0>;
using Oar = ShipGear<0, 0, 1>;

template <typename G1, typename G2>
struct add_gear {
    using type = ShipGear<G1::cannon + G2::cannon, G1::mast + G2::mast, G1::oar + G2::oar>;
};

constexpr number_t substract(number_t A, number_t B) {
    return (B > A) ? 0 : A - B;
}

template <typename G1, typename G2>
struct remove_gear {
    using type = ShipGear< substract(G1::cannon, G2::cannon), substract(G1::mast, G2::mast), substract(G1::oar, G2::oar) >;
};

template <typename G1, unsigned int N>
struct multiply_gear {
    using type = ShipGear< G1::cannon * N, G1::mast * N, G1::oar * N>;
};

template <typename G1, unsigned int N>
struct split_gear {
    static_assert(N != 0, "N must not be zero");

    using type = ShipGear< G1::cannon / N, G1::mast / N, G1::oar / N>;
};

template <typename Gear>
class Squad {
    public:
        using gear_type = Gear;

        Squad(): Squad(1) {}
        explicit Squad(const unsigned int count): count(count) {}

        unsigned int get_count() const {
            return count;
        }

        static gear_type gear;

        Squad& operator += (const Squad& other) {
            count += other.get_count();
            return *this;
        }

        Squad& operator -= (const Squad& other) {
            if(other.get_count() > count) {
                count = 0;
            } else {
                count -= other.get_count();
            }
            return *this;
        }

        Squad& operator *= (const unsigned int value) {
            count *= value;

            return *this;
        }

        Squad& operator /= (const unsigned int value) {
            assert(value != 0);

            count /= value;

            return *this;
        }

    private:
        unsigned int count;
};

template <typename Gear>
const Squad<Gear> operator + (Squad<Gear> S1, const Squad<Gear>& S2) {
    return S1 += S2;
}

template <typename Gear>
const Squad<Gear> operator - (Squad<Gear> S1, const Squad<Gear>& S2) {
    return S1 -= S2;
}

template <typename Gear>
const Squad<Gear> operator * (Squad<Gear> S, const unsigned int value) {
    return S *= value;
}

template <typename Gear>
const Squad<Gear> operator / (Squad<Gear> S, const unsigned int value) {
    return S /= value;
}

template <typename G1, typename G2>
bool operator == (const Squad<G1>& S1, const Squad<G2>& S2) {
    return G1::cannon == G2::cannon &&
           G1::mast == G2::mast &&
           G1::oar == G2::oar &&
           S1.get_count() == S2.get_count();
}

template <typename G1, typename G2>
bool operator != (const Squad<G1>& S1, const Squad<G2>& S2) {
    return ! (S1 == S2);
}

template <typename G1, typename G2>
bool operator < (const Squad<G1>& S1, const Squad<G2>& S2) {
    if(G1::cannon == G2::cannon && G1::mast == G2::mast && G1::oar == G2::oar)
        return S1.get_count() < S2.get_count();
    return G1::cannon < G2::cannon;
}

template <typename G1, typename G2>
bool operator > (const Squad<G1>& S1, const Squad<G2>& S2) {
    return S2 < S1;
}

template <typename G1, typename G2>
bool operator <= (const Squad<G1>& S1, const Squad<G2>& S2) {
    return !(S1 > S2);
}
template <typename G1, typename G2>
bool operator >= (const Squad<G1>& S1, const Squad<G2>& S2) {
    return S2 <= S1;
}

template <typename Gear>
std::ostream& operator << (std::ostream& out, const Squad<Gear>& S) {
    return out << "Ships: " << S.get_count() << "; Ship gear: Cannons: " << Gear::cannon << ", Masts: " << Gear::mast << ", Oars: " << Gear::oar;
}

template <typename Gear, typename OtherGear>
auto join_ships(const Squad<Gear>& S1, const Squad<OtherGear>& S2) -> const Squad<typename add_gear<Gear, OtherGear>::type > {
    using result_type = typename add_gear<Gear, OtherGear>::type;

    unsigned int total_cannons = Gear::cannon * S1.get_count() + OtherGear::cannon * S2.get_count();
    unsigned int total_masts = Gear::mast * S1.get_count() + OtherGear::mast * S2.get_count();
    unsigned int total_oars = Gear::oar * S1.get_count() + OtherGear::oar * S2.get_count();

    std::vector<unsigned int> min_candidates;
    if(result_type::cannon != 0) min_candidates.emplace_back(total_cannons / result_type::cannon);
    if(result_type::mast != 0) min_candidates.emplace_back(total_masts / result_type::mast);
    if(result_type::oar != 0) min_candidates.emplace_back(total_oars / result_type::oar);
    min_candidates.emplace_back(S1.get_count() + S2.get_count());

    unsigned int ship_number = *min_element(min_candidates.begin(), min_candidates.end());

    return Squad<result_type>{ship_number};
}

template <typename Gear>
auto split_ships(const Squad<Gear>& S) -> const Squad<typename split_gear<Gear, 2>::type > {
    using result_type = typename split_gear<Gear, 2>::type;

    return Squad<result_type>(S.get_count());
}

template <typename G1, typename G2>
constexpr int do_compare() {
    return
        (G1::cannon < G2::cannon) ? -1 :
        (G1::cannon > G2::cannon) ? +1 :
        (G1::mast < G2::mast) ? -1 :
        (G1::mast > G2::mast) ? +1 :
        (G1::oar < G2::oar) ? -1 :
        (G1::oar > G2::oar) ? +1 :
        0;
}

template <typename G1, typename G2>
struct compare {
    static const int value = do_compare<G1, G2>();
};

template <typename G1, typename G2, int = compare<G1, G2>::value>
struct expected_booty_impl {
    using result_type = Squad<G1>;
    static const Squad<G1> expected_booty(const Squad<G1>& S1, const Squad<G2>&) {
        return S1;
    }
};

template <typename G1>
struct expected_booty_impl<G1, G1, 0> {
    using result_type = Squad<G1>;
    static const Squad<G1> expected_booty(const Squad<G1>& S1, const Squad<G1>& S2) {
        if(S1.get_count() < S2.get_count())
            return S1;
        else
            return S2;
    }
};

template <typename G1, typename G2>
struct expected_booty_impl<G1, G2, 1> {
    using result_type = Squad<G2>;
    static const Squad<G2> expected_booty(const Squad<G1>&, const Squad<G2>& S2) {
        return S2;
    }
};

template <typename G1, typename G2>
auto expected_booty(const Squad<G1>& S1, const Squad<G2>& S2) -> const typename expected_booty_impl<G1, G2>::result_type {
    return expected_booty_impl<G1, G2>::expected_booty(S1, S2);
}

#endif /* SHIPWRECK_HH */