==== 소감 ====
{{| 2005/05/02 Accepted 0:00.277 440 |}}

예리한 테스트 케이스에 놀랐다. 신비한 수의 세계를 엿볼 수 있는 문제(?)다. 

==== 코드 ====
{{{~cpp 
// no10090 - Marbles 
#include <iostream> 
using namespace std; 

typedef struct{
	int box1;
	int box2;
} Marble;

const int TYPE1 = 1;
const int TYPE2 = 2;

void show(Marble marble, int cheapest);
Marble find_number_box(int n1, int n2, int n);

int main()
{
	int n;
	int c1, n1;
	int c2, n2;
	int cheapest;
	double n1_efficiency;
	double n2_efficiency;
	Marble marble;
	while (cin >> n)
	{
		if (n == 0)
			break;
		cin >> c1 >> n1;
		cin >> c2 >> n2;
		n1_efficiency = (double) n1 / c1;
		n2_efficiency = (double) n2 / c2;
		cheapest = (n1_efficiency > n2_efficiency) ? TYPE1 : TYPE2;
		if (cheapest == TYPE1)
			marble = find_number_box(n1, n2, n);	
		else 
			marble = find_number_box(n2, n1, n);
		show(marble, cheapest);
	}
	return 0;
}

Marble find_number_box(int n1, int n2, int n)
{
	int firstModulo;
	Marble marble;
	int count = n/n1;		// n1의 개수
	int temp = n - (n1 * count);

	if (n % n1 == 0)
	{
		marble.box1 = count;
		marble.box2 = 0;
		return marble;
	}

	firstModulo = temp % n2;

	while (count >= 0)
	{
		if (temp % n2 == 0)
		{
			marble.box1 = count;
			marble.box2 = temp / n2;
			return marble;
		}
		temp += n1;
		count--;
		if (firstModulo == temp % n2)
			break;
	}
	marble.box1 = -1;	// failed
	return marble;
}

void show(Marble marble, int cheapest)
{
	if (marble.box1 == -1)
		cout << "failed\n";
	else if (cheapest == TYPE1)
		cout << marble.box1 << " " << marble.box2 << endl;
	else
		cout << marble.box2 << " " << marble.box1 << endl;
}
}}}
----
[Marbles] [AOI]