#include <iostream>
#include <vector>
#include <tuple>
#include <limits>
#include <algorithm>
#include <cstdint>
#include <cmath>
#include <iomanip>

typedef std::tuple<std::uint64_t, double> Coin;
typedef std::vector<Coin> Coins;
typedef std::vector<std::uint64_t> DType;
typedef std::vector<DType> RType;

bool DoubleEqual(double a, double b,double Epsilon){
	return std::abs(a - b) <= Epsilon;
}

bool AddVector(DType& D, DType& L){
	bool Carry = false;
	D[0]++;
	for (std::size_t i = 0; i < D.size(); i++)
	{
		if (Carry == true){
			D[i]++;
		}
		Carry = false;
		if (D[i] > L[i]){
			D[i] = 0;
			Carry = true;
		}

	}
	return true;
}

bool CheckWeight(const double& Weight, Coins& C, DType& D){

	double Total = 0;

	for (std::size_t i = 0; i < C.size(); i++){
		Total += std::get<1>(C[i]) * D[i];
	}

	return DoubleEqual(Weight, Total,0.000000001);
}


RType MakeHoge(double Weight, Coins C){
	DType L;
	DType D(C.size());
	bool F = false;
	RType R;
	for (auto& o : C){
		L.push_back(static_cast<std::uint64_t>(std::ceil(Weight / std::get<1>(o))));
	}

	while (F == false){
		if (CheckWeight(Weight, C, D) == true){
			R.push_back(D);
		}

		AddVector(D, L);

		F = true;
		for (std::size_t i = 0; i < D.size(); i++)
		{
			if (D[i] != L[i]){
				F = false;
				break;
			}

		}
	}

	return R;
}

bool Show(const double& Weight, RType R, Coins C){
	double Total = 0;

	std::cout << "input Weight:" << Weight <<"g"<< std::endl;
	std::cout << "have the " << R.size()<<" Lists"<< std::endl;
	std::cout << std::setw(10)<<"amount|";
	for (auto& o : C){
		std::cout << std::setw(5)<<std::get<0>(o);
	}

	std::cout<<std::endl;

	std::sort(R.begin(), R.end(), [&](DType& A, DType& B){
		double TotalA = 0;
		double TotalB = 0;
		for (std::size_t i = 0; i < A.size(); i++)
		{
			TotalA += A[i] * std::get<0>(C[i]);
		}
		for (std::size_t i = 0; i < B.size(); i++)
		{
			TotalB += B[i] * std::get<0>(C[i]);
		}
		return TotalA < TotalB;
	});

	for (auto& oo : R){
		for (std::size_t i = 0; i < oo.size(); i++)
		{
			Total += oo[i] * std::get<0>(C[i]);
		}
		std::cout << std::setw(9) << Total<<"|";
		for (auto& o : oo){
			std::cout << std::setw(5) << o;
		}
		std::cout<<std::endl;
		Total = 0;
	}


	return true;
}


int main(){
	Coins C{ std::make_tuple(1, 1.0), std::make_tuple(5, 3.7), std::make_tuple(10, 4.5), std::make_tuple(50, 4.0), std::make_tuple(100, 4.8), std::make_tuple(500, 7.0), };
	double W = 0;
	RType R;

	W = 23.7;
	R = MakeHoge(W, C);
	Show(W, R, C);

	return 0;

}