시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 7 7 77.778%

문제

원웅이는 두 종류의 추와 저울을 이용해서 아스피린의 양을 재려고 한다. 원웅이는 추를 무수히 많이 가지고 있고, 약은 가루로 가지고 있다.

예를 들어, 300mg 추와 700mg 추가 있을 때, 200mg의 아스피린을 재려면, 300mg 추 3개를 왼편에 놓고, 700mg의 추 1개를 반대편에 놓은 뒤, 평형을 이루도록 약을 놓으면 된다. 

또는, 왼쪽에 700mg 추 2개를 놓고, 오른쪽에 300mg추 4개를 놓으면, 오른쪽에 약을 저울이 평형을 이루도록 놓으면 된다.

원웅이가 가지고 있는 추의 종류와 재려고 하는 아스피린의 양이 주어졌을 때, 각각 추를 몇 개 사용하면 아스피린의 양을 잴 수 있는지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, a, b, d가 공백으로 구분되어 주어진다.

a와 b는 원웅이가 가지고 있는 추의 무게이고, d는 재려고 하는 약의 양이다. a와 b는 같지 않고, 두 수 모두 10,00보다 작거나 같은 자연수이다. d는 50,000보다 작거나 같은 자연수이다.

정답이 존재하지 않는 경우는 없다.

테스트 케이스는 a, b, d가 0일 때 끝난다.

출력

각 테스트 케이스에 대해서, x와 y를 출력한다. x와 y는 다음 세가지 조건을 만족해야 한다.

1. amg추 x개와 bmg추 y개를 이용해서 dmg의 약을 저울로 잴 수 있어야 한다.

2. 1번 조건을 만족하는 경우가 여러 가지라면, 사용한 추의 개수(x+y)가 가장 작은 것을 출력한다.

3. 2번 조건을 만족하는 경우도 여러 가지라면, 추의 총 질량(ax+by)이 가장 작은 것을 출력한다.

예제 입력 1

700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0

예제 출력 1

1 3
1 1
1 0
0 3
1 1
49 74
3333 1
W3sicHJvYmxlbV9pZCI6IjM5MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDBcdWM2YjgiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzZkMFx1YzZjNVx1Yzc3NFx1YjI5NCBcdWI0NTAgXHVjODg1XHViOTU4XHVjNzU4IFx1Y2Q5NFx1YzY0MCBcdWM4MDBcdWM2YjhcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzU0NFx1YzJhNFx1ZDUzY1x1YjliMFx1Yzc1OCBcdWM1OTFcdWM3NDQgXHVjN2FjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNmQwXHVjNmM1XHVjNzc0XHViMjk0IFx1Y2Q5NFx1Yjk3YyBcdWJiMzRcdWMyMThcdWQ3ODggXHViOWNlXHVjNzc0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YzU3ZFx1Yzc0MCBcdWFjMDBcdWI4ZThcdWI4NWMgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMzAwbWcgXHVjZDk0XHVjNjQwIDcwMG1nIFx1Y2Q5NFx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCAyMDBtZ1x1Yzc1OCBcdWM1NDRcdWMyYTRcdWQ1M2NcdWI5YjBcdWM3NDQgXHVjN2FjXHViODI0XHViYTc0LCAzMDBtZyBcdWNkOTQgM1x1YWMxY1x1Yjk3YyBcdWM2N2NcdWQzYjhcdWM1ZDAgXHViMTkzXHVhY2UwLCA3MDBtZ1x1Yzc1OCBcdWNkOTQgMVx1YWMxY1x1Yjk3YyBcdWJjMThcdWIzMDBcdWQzYjhcdWM1ZDAgXHViMTkzXHVjNzQwIFx1YjRhNCwgXHVkM2M5XHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjNjNFx1Yjg1ZCBcdWM1N2RcdWM3NDQgXHViMTkzXHVjNzNjXHViYTc0IFx1YjQxY1x1YjJlNC4mbmJzcDs8XC9wPlxyXG48cD5cclxuXHRcdWI2MTBcdWIyOTQsIFx1YzY3Y1x1Y2FiZFx1YzVkMCA3MDBtZyBcdWNkOTQgMlx1YWMxY1x1Yjk3YyBcdWIxOTNcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCAzMDBtZ1x1Y2Q5NCA0XHVhYzFjXHViOTdjIFx1YjE5M1x1YzczY1x1YmE3NCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1YzU3ZFx1Yzc0NCBcdWM4MDBcdWM2YjhcdWM3NzQgXHVkM2M5XHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjNjNFx1Yjg1ZCBcdWIxOTNcdWM3M2NcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2ZDBcdWM2YzVcdWM3NzRcdWFjMDAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWNkOTRcdWM3NTggXHVjODg1XHViOTU4XHVjNjQwIFx1YzdhY1x1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHVjNTQ0XHVjMmE0XHVkNTNjXHViOWIwXHVjNzU4IFx1YzU5MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDFcdWFjMDEgXHVjZDk0XHViOTdjIFx1YmE4NyBcdWFjMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHViYTc0IFx1YzU0NFx1YzJhNFx1ZDUzY1x1YjliMFx1Yzc1OCBcdWM1OTFcdWM3NDQgXHVjN2I0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYjEucG5nXCIgc3R5bGU9XCJ3aWR0aDogNDI3cHg7IGhlaWdodDogMTE5cHg7XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iMi5wbmdcIiBzdHlsZT1cIndpZHRoOiA0MjZweDsgaGVpZ2h0OiAxMzRweDtcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBhLCBiLCBkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRhXHVjNjQwIGJcdWIyOTQgXHVjNmQwXHVjNmM1XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjZDk0XHVjNzU4IFx1YmIzNFx1YWM4Y1x1Yzc3NFx1YWNlMCwgZFx1YjI5NCBcdWM3YWNcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YzU3ZFx1Yzc1OCBcdWM1OTFcdWM3NzRcdWIyZTQuIGFcdWM2NDAgYlx1YjI5NCBcdWFjMTlcdWM5YzAgXHVjNTRhXHVhY2UwLCBcdWI0NTAgXHVjMjE4IFx1YmFhOFx1YjQ1MCAxMCwwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC4gZFx1YjI5NCA1MCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgYSwgYiwgZFx1YWMwMCAwXHVjNzdjIFx1YjU0YyBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiXHJcbjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgeFx1YzY0MCB5XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4geFx1YzY0MCB5XHViMjk0IFx1YjJlNFx1Yzc0YyBcdWMxMzhcdWFjMDBcdWM5YzAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDEuIGFtZ1x1Y2Q5NCB4XHVhYzFjXHVjNjQwIGJtZ1x1Y2Q5NCB5XHVhYzFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBkbWdcdWM3NTggXHVjNTdkXHVjNzQ0IFx1YzgwMFx1YzZiOFx1Yjg1YyBcdWM3YjQgXHVjMjE4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDIuIDFcdWJjODggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVjMGFjXHVjNmE5XHVkNTVjIFx1Y2Q5NFx1Yzc1OCBcdWFjMWNcdWMyMTgoeCt5KVx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDMuIDJcdWJjODggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVjZDk0XHVjNzU4IFx1Y2QxZCBcdWM5YzhcdWI3YzkoYXgrYnkpXHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5MjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgQmFsYW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+TXMuIEl5byBLaWZmYS1BdXN0cmFsaXMgaGFzIGEgYmFsYW5jZSBhbmQgb25seSB0d28ga2luZHMgb2Ygd2VpZ2h0cyB0byBtZWFzdXJlIGEgZG9zZSBvZiBtZWRpY2luZTxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdG8gbWVhc3VyZSAyMDBtZyBvZiBhc3BpcmluIHVzaW5nIDMwMG1nIHdlaWdodHMgYW5kIDcwMG1nIHdlaWdodHMsIHNoZSBjYW4gcHV0IG9uZSA3MDBtZyB3ZWlnaHQgb24gdGhlIHNpZGUgb2YgdGhlIG1lZGljaW5lIGFuZCB0aHJlZSAzMDBtZyB3ZWlnaHRzIG9uIHRoZSBvcHBvc2l0ZSBzaWRlIChGaWd1cmUgMSkuIEFsdGhvdWdoIHNoZSBjb3VsZCBwdXQgZm91ciAzMDBtZyB3ZWlnaHRzIG9uIHRoZSBtZWRpY2luZSBzaWRlIGFuZCB0d28gNzAwbWcgd2VpZ2h0cyBvbiB0aGUgb3RoZXIgKEZpZ3VyZSAyKSwgc2hlIHdvdWxkIG5vdCBjaG9vc2UgdGhpcyBzb2x1dGlvbiBiZWNhdXNlIGl0IGlzIGxlc3MgY29udmVuaWVudCB0byB1c2UgbW9yZSB3ZWlnaHRzLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGFza2VkIHRvIGhlbHAgaGVyIGJ5IGNhbGN1bGF0aW5nIGhvdyBtYW55IHdlaWdodHMgYXJlIHJlcXVpcmVkLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2IxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExOXB4OyB3aWR0aDo0MjdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMTogVG8gbWVhc3VyZSAyMDBtZyBvZiBhc3BpcmluIHVzaW5nIHRocmVlIDMwMG1nIHdlaWdodHMgYW5kIG9uZSA3MDBtZyB3ZWlnaHQ8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzRweDsgd2lkdGg6NDI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDI6IFRvIG1lYXN1cmUgMjAwbWcgb2YgYXNwaXJpbiB1c2luZyBmb3VyIDMwMG1nIHdlaWdodHMgYW5kIHR3byA3MDBtZyB3ZWlnaHRzPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgYSBzZXF1ZW5jZSBvZiBkYXRhc2V0cy4gQSBkYXRhc2V0IGlzIGEgbGluZSBjb250YWluaW5nIHRocmVlIHBvc2l0aXZlIGludGVnZXJzIGEsIGIsIGFuZCBkIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBUaGUgZm9sbG93aW5nIHJlbGF0aW9ucyBob2xkOiBhICZuZTsgYiwgYSAmbGU7IDEwMDAwLCBiICZsZTsgMTAwMDAsIGFuZCBkICZsZTsgNTAwMDAuIFlvdSBtYXkgYXNzdW1lIHRoYXQgaXQgaXMgcG9zc2libGUgdG8gbWVhc3VyZSBkIG1nIHVzaW5nIGEgY29tYmluYXRpb24gb2YgYSBtZyBhbmQgYiBtZyB3ZWlnaHRzLiBJbiBvdGhlciB3b3JkcywgeW91IG5lZWQgbm90IGNvbnNpZGVyICZxdW90O25vIHNvbHV0aW9uJnF1b3Q7IGNhc2VzLjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdGhyZWUgemVyb3Mgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIEl0IGlzIG5vdCBhIGRhdGFzZXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgYmUgY29tcG9zZWQgb2YgbGluZXMsIGVhY2ggY29ycmVzcG9uZGluZyB0byBhbiBpbnB1dCBkYXRhc2V0IChhLCBiLCBkKS4gQW4gb3V0cHV0IGxpbmUgc2hvdWxkIGNvbnRhaW4gdHdvIG5vbm5lZ2F0aXZlIGludGVnZXJzIHggYW5kIHkgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZXkgc2hvdWxkIHNhdGlzZnkgdGhlIGZvbGxvd2luZyB0aHJlZSBjb25kaXRpb25zLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPllvdSBjYW4gbWVhc3VyZSBkIG1nIHVzaW5nIHggbWFueSBhIG1nIHdlaWdodHMgYW5kIHkgbWFueSBiIG1nIHdlaWdocy48XC9saT5cclxuXHQ8bGk+VGhlIHRvdGFsIG51bWJlciBvZiB3ZWlnaHRzICh4ICsgeSkgaXMgdGhlIHNtYWxsZXN0IGFtb25nIHRob3NlIHBhaXJzIG9mIG5vbm5lZ2F0aXZlIGludGVnZXJzIHNhdGlzZnlpbmcgdGhlIHByZXZpb3VzIGNvbmRpdGlvbi48XC9saT5cclxuXHQ8bGk+VGhlIHRvdGFsIG1hc3Mgb2Ygd2VpZ2h0cyAoYXggKyBieSkgaXMgdGhlIHNtYWxsZXN0IGFtb25nIHRob3NlIHBhaXJzIG9mIG5vbm5lZ2F0aXZlIGludGVnZXJzIHNhdGlzZnlpbmcgdGhlIHByZXZpb3VzIHR3byBjb25kaXRpb25zLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk5vIGV4dHJhIGNoYXJhY3RlcnMgKGUuZy4gZXh0cmEgc3BhY2VzKSBzaG91bGQgYXBwZWFyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=