#include <iostream>
#include <conio.h>
#include <fstream>
#include <string>
#include <vector>

#include "AKB4.h"

using namespace std;

void wczytaj(int &wielkosc, vector<int> &zbior);
bool spr(int c,int wielkosc);
void mapuj(vector<Skladowa> &rozwiazanie, vector<int> &zbior, int liczbaciec, int wielkosczbioru, int start, bool jest,int suma);
int ZnajdzSubMaxWartosc(int maxi, int c, vector<int> tab);
int ZnajdzMaxWartosc(int c, vector<int> tab);

int maximum;
int main()
{
	int LiczbaCiec = 0, WielkosZbioru = 0;
	vector<Skladowa> rozwiazanie;
	vector<int> zbior;
	bool jest = false;
	cout << "podaj ilosc ciec: " << endl;
	cin >> LiczbaCiec;
	rozwiazanie.reserve(LiczbaCiec+1);
	cout << endl;
	wczytaj(WielkosZbioru, zbior);
	if (spr(LiczbaCiec,WielkosZbioru))//sprawdzamy czy podany zbior jest poprawny
	{
		cout << " dane wejsiowe poprawne" << endl;
		//inicializujemy 1 liczbe do rozwiazania
		Skladowa pierwsza;
		maximum = ZnajdzMaxWartosc(WielkosZbioru, zbior);
		pierwsza.value = ZnajdzMaxWartosc(WielkosZbioru, zbior) - ZnajdzSubMaxWartosc(ZnajdzMaxWartosc(WielkosZbioru, zbior), WielkosZbioru, zbior);
		pierwsza.sum = pierwsza.value;
		rozwiazanie.push_back(pierwsza);
		//szukamy i wyrzucamy nasza 1 wartosc ze zbioru
		for (int i = 0; i <= WielkosZbioru;i++)
			if (pierwsza.value == zbior.at(i))
			{
				pierwsza.fromV = i;
				pierwsza.fromSum = i;
				zbior.at(i) = 0;
				break;
			}
		//=====================================================		wypelniamy rozwiazanie
		Skladowa nowy;
		nowy.value = 0;
		for (int i = 1; i<=LiczbaCiec; i++)
			rozwiazanie.push_back(nowy);
		//=====================================================		wypisanie 1 znalezionego elementu
		cout << "\n\n";
		for (int x = 0; x < rozwiazanie.size(); x++)
			cout << rozwiazanie.at(x).value << " ";
		cout << "\n";
		for (int x = 0; x <zbior.size(); x++)
			cout << zbior.at(x) << " ";
		mapuj(rozwiazanie,zbior,LiczbaCiec,WielkosZbioru,1,jest, rozwiazanie.at(0).sum);
		//===================================================		wypisanie calkowitego rozwiazania
		if (jest)
		{
			cout << "\n\n";
			for (int x = 0; x < rozwiazanie.size(); x++)
				cout << rozwiazanie.at(x).value << " ";
			cout << "\n";
			for (int x = 0; x < rozwiazanie.size(); x++)
				cout << zbior.at(x) << " ";
		}
		else cout << "brak roziwazania";

	}
	else cout << "dane wejesciowe nie poprawne";


	_getch();

	return 0;
}

bool spr(int c, int wielksoc)
{
	double s1 = 1, s2 = 1;

	for (int i = 1; i <= c; i++)
		s1 *= i;
	for (int i = 1; i <= c + 2; i++)
		s2 *= i;
	cout << s1 << " " << s2 << " " << wielksoc+1 << " " << s2 / (2 * s1) << endl;
	if (wielksoc+1 == s2 / (2 * s1))
		return true;
	else return false;
}
int ZnajdzMaxWartosc(int c, vector<int> tab)
{
	int maxi = 0;
	for (int i = 0; i <= c; i++)
	{
		if (maxi<tab[i])
			maxi = tab[i];

	}
	return maxi;
}
int ZnajdzSubMaxWartosc(int maxi, int c, vector<int> tab)
{
	int semimaxi = 0;
	for (int j = 0; j<c; j++)
	{
		if (tab[j]>semimaxi && semimaxi < maxi)
			semimaxi = tab[j];
	}
	return semimaxi;
}
void wczytaj(int &wielkosc, vector<int> &zbior)
{
	fstream plik;
	string dane;
	int j = 0;
	//===========================		preload
	plik.open("test.txt", ios::in);
	while (!plik.eof())
	{
		getline(plik, dane, ' ');
		wielkosc++;
	}
	zbior.reserve(wielkosc);

	plik.clear();
	plik.seekg(0, ios::beg);
	//=========================		load
	for (int i = 1; i <= wielkosc; i++)
	{
		getline(plik, dane, ' ');
		zbior.push_back(atoi(dane.c_str()));
	}
	plik.close();
	wielkosc -= 1;
}

void mapuj(vector<Skladowa> &rozwiazanie, vector<int> &zbior, int liczbaciec, int wielkosczbioru, int start, bool jest,int suma)
{
	if (suma == maximum && start == liczbaciec)
		jest = true;
	else if (!jest)
	{
		if (start > liczbaciec || suma >  maximum)
			return;
		else
			for (int i = start; i <= liczbaciec; i++)
			{
				for (int j = 0; j < wielkosczbioru; j++)
				{
					while (zbior.at(j) == 0)//pomijamy 0
						j++;
					//	if (zbior.at(j) == zbior.at(j - 1))//pomijamy ta sama wartosc
					//		j++;
					if (rozwiazanie.at(i - 1).sum + zbior.at(j) > maximum)//pomijamy wartosc gdy po dodaniu do smumy wieksza od max wartosci
						continue;
					rozwiazanie.at(i).value = zbior.at(j);
					rozwiazanie.at(i).fromV = j;
					zbior.at(j) = 0;
					if (rozwiazanie.at(i).value == 0)//jesli w tym momencie jest zerem to przeskakujemy na nastepne j
						continue;
					for (int s = 0; s < wielkosczbioru; s++)
						if (rozwiazanie.at(i).value == 0) //jesli w tym momencie jest zerem to przestajemy szukac wyniku dla pary
							break;
						else
							if (rozwiazanie.at(i).value + rozwiazanie.at(i - 1).value == zbior.at(s)) // jesli suma pary znajduje sie w zbiorze przystepujemy do szukania sumy calego rozwiazania
							{
								cout << "\n\n";
								for (int x = 0; x < rozwiazanie.size(); x++)
									cout << rozwiazanie.at(x).value << " ";
								int sumaPary = rozwiazanie.at(i).value + rozwiazanie.at(i - 1).value;
								int indeksSumyPar = s;
								if (i - 1 != 1)
								{
									zbior.at(s) = 0;
									rozwiazanie.at(i).sum = rozwiazanie.at(i).value + rozwiazanie.at(i - 1).sum;
								} //zapisujemy wartosc sumy}
									for (int ss = 0; ss < wielkosczbioru; ss++)
									if (rozwiazanie.at(i).sum == 0) //jesli w tym momencie jest zerem to przestajemy szukac wyniku dla sumy calosci
										break;
									else
										if (rozwiazanie.at(i).sum == zbior.at(ss)) //szukamy wartosci dla sumy wszystkiego
										{
											rozwiazanie.at(i).fromSum = ss; //zapisujemy skad usunelismy sume
											zbior.at(ss) = 0;//usuwamy sume ze zbioru
											cout << "\n\n";
											for (int x = 0; x < rozwiazanie.size(); x++)
												cout << rozwiazanie.at(x).value << " ";
											cout << "\n";
											for (int x = 0; x < zbior.size(); x++)
												cout << zbior.at(x) << " ";
											if (suma == maximum && start == liczbaciec)
												jest = true;
											if (i + 1 <= liczbaciec)
												mapuj(rozwiazanie, zbior, liczbaciec, wielkosczbioru, ++i, jest, rozwiazanie.at(start).sum);//szukamy dalej
											//wyszlismy czyli zwracamy wartosc sumy; zwracamy wartosc dodanego elementu; zwracamy sume pary
											cout << "\n\n";
											for (int x = 0; x < rozwiazanie.size(); x++)
												cout << rozwiazanie.at(x).value << " ";
											cout << "\n";
											for (int x = 0; x < zbior.size(); x++)
												cout << zbior.at(x) << " ";
											zbior.at(ss) = rozwiazanie.at(i).sum;
											rozwiazanie.at(i).sum = 0;
											rozwiazanie.at(i).fromSum = 0;


										}
								zbior.at(indeksSumyPar) = sumaPary;
							}
					if (rozwiazanie.at(i).value != 0)
					{
						zbior.at(rozwiazanie.at(i).fromV) = rozwiazanie.at(i).value;
						rozwiazanie.at(i).value = 0;
					}
				}
				if (jest)
					return;
			}
	}
}