시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16 5 5 71.429%

문제

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

예를 들어, 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+XHJcblxyXG48cD5cclxuXHRhXHVjNjQwIGJcdWIyOTQgXHVjNmQwXHVjNmM1XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjZDk0XHVjNzU4IFx1YmIzNFx1YWM4Y1x1Yzc3NFx1YWNlMCwgZFx1YjI5NCBcdWM3YWNcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YzU3ZFx1Yzc1OCBcdWM1OTFcdWM3NzRcdWIyZTQuIGFcdWM2NDAgYlx1YjI5NCBcdWFjMTlcdWM5YzAgXHVjNTRhXHVhY2UwLCBcdWI0NTAgXHVjMjE4IFx1YmFhOFx1YjQ1MCAxMCwwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC4gZFx1YjI5NCA1MCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgYSwgYiwgZFx1YWMwMCAwXHVjNzdjIFx1YjU0YyBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiXHJcbjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgeFx1YzY0MCB5XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4geFx1YzY0MCB5XHViMjk0IFx1YjJlNFx1Yzc0YyBcdWMxMzhcdWFjMDBcdWM5YzAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDEuIGFtZ1x1Y2Q5NCB4XHVhYzFjXHVjNjQwIGJtZ1x1Y2Q5NCB5XHVhYzFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBkbWdcdWM3NTggXHVjNTdkXHVjNzQ0IFx1YzgwMFx1YzZiOFx1Yjg1YyBcdWM3YjQgXHVjMjE4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDIuIDFcdWJjODggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0LCBcdWMwYWNcdWM2YTlcdWQ1NWMgXHVjZDk0XHVjNzU4IFx1YWMxY1x1YzIxOCh4K3kpXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0My4gMlx1YmM4OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1Y2Q5NFx1Yzc1OCBcdWNkMWQgXHVjOWM4XHViN2M5KGF4K2J5KVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzkyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBCYWxhbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5Ncy4gSXlvIEtpZmZhLUF1c3RyYWxpcyBoYXMgYSBiYWxhbmNlIGFuZCBvbmx5IHR3byBraW5kcyBvZiB3ZWlnaHRzIHRvIG1lYXN1cmUgYSBkb3NlIG9mIG1lZGljaW5lPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0byBtZWFzdXJlIDIwMG1nIG9mIGFzcGlyaW4gdXNpbmcgMzAwbWcgd2VpZ2h0cyBhbmQgNzAwbWcgd2VpZ2h0cywgc2hlIGNhbiBwdXQgb25lIDcwMG1nIHdlaWdodCBvbiB0aGUgc2lkZSBvZiB0aGUgbWVkaWNpbmUgYW5kIHRocmVlIDMwMG1nIHdlaWdodHMgb24gdGhlIG9wcG9zaXRlIHNpZGUgKEZpZ3VyZSAxKS4gQWx0aG91Z2ggc2hlIGNvdWxkIHB1dCBmb3VyIDMwMG1nIHdlaWdodHMgb24gdGhlIG1lZGljaW5lIHNpZGUgYW5kIHR3byA3MDBtZyB3ZWlnaHRzIG9uIHRoZSBvdGhlciAoRmlndXJlIDIpLCBzaGUgd291bGQgbm90IGNob29zZSB0aGlzIHNvbHV0aW9uIGJlY2F1c2UgaXQgaXMgbGVzcyBjb252ZW5pZW50IHRvIHVzZSBtb3JlIHdlaWdodHMuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgYXNrZWQgdG8gaGVscCBoZXIgYnkgY2FsY3VsYXRpbmcgaG93IG1hbnkgd2VpZ2h0cyBhcmUgcmVxdWlyZWQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYjEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTE5cHg7IHdpZHRoOjQyN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBUbyBtZWFzdXJlIDIwMG1nIG9mIGFzcGlyaW4gdXNpbmcgdGhyZWUgMzAwbWcgd2VpZ2h0cyBhbmQgb25lIDcwMG1nIHdlaWdodDxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2IyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzNHB4OyB3aWR0aDo0MjZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMjogVG8gbWVhc3VyZSAyMDBtZyBvZiBhc3BpcmluIHVzaW5nIGZvdXIgMzAwbWcgd2VpZ2h0cyBhbmQgdHdvIDcwMG1nIHdlaWdodHM8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBhIHNlcXVlbmNlIG9mIGRhdGFzZXRzLiBBIGRhdGFzZXQgaXMgYSBsaW5lIGNvbnRhaW5pbmcgdGhyZWUgcG9zaXRpdmUgaW50ZWdlcnMgYSwgYiwgYW5kIGQgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZSBmb2xsb3dpbmcgcmVsYXRpb25zIGhvbGQ6IGEgJm5lOyBiLCBhICZsZTsgMTAwMDAsIGIgJmxlOyAxMDAwMCwgYW5kIGQgJmxlOyA1MDAwMC4gWW91IG1heSBhc3N1bWUgdGhhdCBpdCBpcyBwb3NzaWJsZSB0byBtZWFzdXJlIGQgbWcgdXNpbmcgYSBjb21iaW5hdGlvbiBvZiBhIG1nIGFuZCBiIG1nIHdlaWdodHMuIEluIG90aGVyIHdvcmRzLCB5b3UgbmVlZCBub3QgY29uc2lkZXIgJnF1b3Q7bm8gc29sdXRpb24mcXVvdDsgY2FzZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBlbmQgb2YgdGhlIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyB0aHJlZSB6ZXJvcyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gSXQgaXMgbm90IGEgZGF0YXNldC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBiZSBjb21wb3NlZCBvZiBsaW5lcywgZWFjaCBjb3JyZXNwb25kaW5nIHRvIGFuIGlucHV0IGRhdGFzZXQgKGEsIGIsIGQpLiBBbiBvdXRwdXQgbGluZSBzaG91bGQgY29udGFpbiB0d28gbm9ubmVnYXRpdmUgaW50ZWdlcnMgeCBhbmQgeSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gVGhleSBzaG91bGQgc2F0aXNmeSB0aGUgZm9sbG93aW5nIHRocmVlIGNvbmRpdGlvbnMuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+WW91IGNhbiBtZWFzdXJlIGQgbWcgdXNpbmcgeCBtYW55IGEgbWcgd2VpZ2h0cyBhbmQgeSBtYW55IGIgbWcgd2VpZ2hzLjxcL2xpPlxyXG5cdDxsaT5UaGUgdG90YWwgbnVtYmVyIG9mIHdlaWdodHMgKHggKyB5KSBpcyB0aGUgc21hbGxlc3QgYW1vbmcgdGhvc2UgcGFpcnMgb2Ygbm9ubmVnYXRpdmUgaW50ZWdlcnMgc2F0aXNmeWluZyB0aGUgcHJldmlvdXMgY29uZGl0aW9uLjxcL2xpPlxyXG5cdDxsaT5UaGUgdG90YWwgbWFzcyBvZiB3ZWlnaHRzIChheCArIGJ5KSBpcyB0aGUgc21hbGxlc3QgYW1vbmcgdGhvc2UgcGFpcnMgb2Ygbm9ubmVnYXRpdmUgaW50ZWdlcnMgc2F0aXNmeWluZyB0aGUgcHJldmlvdXMgdHdvIGNvbmRpdGlvbnMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm8gZXh0cmEgY2hhcmFjdGVycyAoZS5nLiBleHRyYSBzcGFjZXMpIHNob3VsZCBhcHBlYXIgaW4gdGhlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=