#include "stdafx.h"

#include <fstream>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>

using namespace std;

typedef vector<int> v_int;
typedef stack<int> s_int;

void load_data(v_int &buffer, int &magic, int &level);
void out_result(s_int &pos, v_int &numbers);

int _tmain(int /*argc*/, _TCHAR* /*argv*/[])
{
	int size, magic, max_level;
	v_int numbers, sums;

	load_data(numbers, magic, max_level);
	size = (int)numbers.size();
	max_level--;

	int sum =  0 ;
	// массив отсортирован по возрастанию
	sort(numbers.begin(), numbers.end(), less<int>());
	// нижние границы отсечения
	for(v_int::iterator iter = numbers.begin(); iter != numbers.end(); iter++)
	{
		sum += *iter;
		sums.push_back(sum);
	}

	// явный стек
	s_int rstack;	
	// номер цифры и текущая искомая сумма
	int level =  0 , level_magic = magic;
	// текущее число
	int pos = size -  1 ;
	// прямой или обратный ход рекурсии
	bool mode = true;
	while(true)
	{
		if (mode)
		{
			// переход через верхнюю границу отсечения
			for(;((pos != - 1 ) && (numbers[pos] > level_magic)); pos--);
			if(pos == - 1 )
			{
				level--;
				mode = false;
				continue;
			}

			// проверка завершения
			if (level == max_level)
			{
				if(level_magic == numbers[pos])
				{			
					rstack.push(pos);
					break;
				}
				
				level--;
				mode = false;
				continue;
			}
			else
			{
				if(level_magic == numbers[pos])
				{
					level--;
					mode = false;
				}
				else
				{
					// новый поиск
					level_magic -= numbers[pos];
					level++;
					rstack.push(pos--);
				}
				continue;
			}
		}
		else
		{
			if(level != - 1 )
			{
				// извлечение из стека
				pos = rstack.top();
				rstack.pop();
				level_magic += numbers[pos--];

				if(pos != - 1 )
					if(sums[pos] >= level_magic)
					{
						level_magic -= numbers[pos];
						level++;

						rstack.push(pos--);
						mode = true;
						continue;
					}
			
				level--;
				mode = false;
				continue;
			}
			else
				break;
		}
	}

	out_result(rstack, numbers);

	return  0 ;
}

void load_data(v_int &buffer, int &magic, int &level)
{
	int size;
	ifstream in_file("C:\\numbers.dat");

	if(in_file.is_open())
	{
		in_file >> magic;
		in_file >> level;
		in_file >> size;

		for(int i =  0 ; i < size; i++)
		{
			int elem;
			in_file >> elem;
			buffer.push_back(elem);
		}
	}
}

void out_result(s_int &pos, v_int &numbers)
{
	ofstream out_file("C:\\result.dat");
	while(!pos.empty())
	{
		out_file << numbers[pos.top()] << endl;
		pos.pop();
	}
	out_file.close();
}