#include<iostream.h>

bool abc(int, int[], int[], int, int&);

void main()
{

	int valueList[ 4 ];
	int stepList[ 4 ];
	int targetValue =  8505 ;
	int Miss =  8505 ;
	int N =  4 ;
	
	valueList[ 0 ] =  20 ;
	valueList[ 1 ] =  70 ;
	valueList[ 2 ] =  130 ;
	valueList[ 3 ] =  260 ;

	for(int i =  0 ; i < N; i++)
		stepList[i] =  0 ;

	abc( 3 , valueList, stepList, targetValue, Miss);

	for(i =  0 ; i < N; i++)
		cout << "stepList[" << i << "] = " << stepList[i] << endl;
}

bool abc(int level, int valueList[], int stepList[], int distance, int& miss)
{
	int nSteps = static_cast<int>(distance / valueList[level]);

	if(nSteps * valueList[level] == distance)
	{
		//hit
		stepList[level] = nSteps;
		miss =  0 ;
		return true;
	}
	else
	{
		//miss
		bool underflow_gt_overflow = distance - nSteps * valueList[level] > (nSteps +  1 ) * valueList[level] - distance;
		int delta = underflow_gt_overflow ? (nSteps +  1 ) * valueList[level] - distance : distance - nSteps * valueList[level];
		if(delta < miss)
		{
			miss = delta;
			stepList[level] = underflow_gt_overflow ? nSteps +  1  : nSteps;
		}
		
		if(level ==  0 )
			return false;
		else
		{
			bool retVal;
			int distance_left;
			for(int i = nSteps; i >=  0 ; i--)
			{
				delta = miss;
				distance_left = distance - i * valueList[level]; 
				retVal = abc(level -  1 , valueList, stepList, distance_left, miss);
				
				if(delta > miss)
					stepList[level] = i;

				if(retVal)
					return true;
			}

			return false;
		}
	}
}