시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cclxuXHRhXHVjNjQwIGJcdWIyOTQgXHVjNmQwXHVjNmM1XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjZDk0XHVjNzU4IFx1YmIzNFx1YWM4Y1x1Yzc3NFx1YWNlMCwgZFx1YjI5NCBcdWM3YWNcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YzU3ZFx1Yzc1OCBcdWM1OTFcdWM3NzRcdWIyZTQuIGFcdWM2NDAgYlx1YjI5NCBcdWFjMTlcdWM5YzAgXHVjNTRhXHVhY2UwLCBcdWI0NTAgXHVjMjE4IFx1YmFhOFx1YjQ1MCAxMCwwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC4gZFx1YjI5NCA1MCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgYSwgYiwgZFx1YWMwMCAwXHVjNzdjIFx1YjU0YyBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiXHJcbjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgeFx1YzY0MCB5XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4geFx1YzY0MCB5XHViMjk0IFx1YjJlNFx1Yzc0YyBcdWMxMzhcdWFjMDBcdWM5YzAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDEuIGFtZ1x1Y2Q5NCB4XHVhYzFjXHVjNjQwIGJtZ1x1Y2Q5NCB5XHVhYzFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBkbWdcdWM3NTggXHVjNTdkXHVjNzQ0IFx1YzgwMFx1YzZiOFx1Yjg1YyBcdWM3YjQgXHVjMjE4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDIuIDFcdWJjODggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVjMGFjXHVjNmE5XHVkNTVjIFx1Y2Q5NFx1Yzc1OCBcdWFjMWNcdWMyMTgoeCt5KVx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDMuIDJcdWJjODggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVjZDk0XHVjNzU4IFx1Y2QxZCBcdWM5YzhcdWI3YzkoYXgrYnkpXHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEJhbGFuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPk1zLiBJeW8gS2lmZmEtQXVzdHJhbGlzIGhhcyBhIGJhbGFuY2UgYW5kIG9ubHkgdHdvIGtpbmRzIG9mIHdlaWdodHMgdG8gbWVhc3VyZSBhIGRvc2Ugb2YgbWVkaWNpbmU8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRvIG1lYXN1cmUgMjAwbWcgb2YgYXNwaXJpbiB1c2luZyAzMDBtZyB3ZWlnaHRzIGFuZCA3MDBtZyB3ZWlnaHRzLCBzaGUgY2FuIHB1dCBvbmUgNzAwbWcgd2VpZ2h0IG9uIHRoZSBzaWRlIG9mIHRoZSBtZWRpY2luZSBhbmQgdGhyZWUgMzAwbWcgd2VpZ2h0cyBvbiB0aGUgb3Bwb3NpdGUgc2lkZSAoRmlndXJlIDEpLiBBbHRob3VnaCBzaGUgY291bGQgcHV0IGZvdXIgMzAwbWcgd2VpZ2h0cyBvbiB0aGUgbWVkaWNpbmUgc2lkZSBhbmQgdHdvIDcwMG1nIHdlaWdodHMgb24gdGhlIG90aGVyIChGaWd1cmUgMiksIHNoZSB3b3VsZCBub3QgY2hvb3NlIHRoaXMgc29sdXRpb24gYmVjYXVzZSBpdCBpcyBsZXNzIGNvbnZlbmllbnQgdG8gdXNlIG1vcmUgd2VpZ2h0cy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBhc2tlZCB0byBoZWxwIGhlciBieSBjYWxjdWxhdGluZyBob3cgbWFueSB3ZWlnaHRzIGFyZSByZXF1aXJlZC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTlweDsgd2lkdGg6NDI3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDE6IFRvIG1lYXN1cmUgMjAwbWcgb2YgYXNwaXJpbiB1c2luZyB0aHJlZSAzMDBtZyB3ZWlnaHRzIGFuZCBvbmUgNzAwbWcgd2VpZ2h0PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYjIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTM0cHg7IHdpZHRoOjQyNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAyOiBUbyBtZWFzdXJlIDIwMG1nIG9mIGFzcGlyaW4gdXNpbmcgZm91ciAzMDBtZyB3ZWlnaHRzIGFuZCB0d28gNzAwbWcgd2VpZ2h0czxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2VxdWVuY2Ugb2YgZGF0YXNldHMuIEEgZGF0YXNldCBpcyBhIGxpbmUgY29udGFpbmluZyB0aHJlZSBwb3NpdGl2ZSBpbnRlZ2VycyBhLCBiLCBhbmQgZCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gVGhlIGZvbGxvd2luZyByZWxhdGlvbnMgaG9sZDogYSAmbmU7IGIsIGEgJmxlOyAxMDAwMCwgYiAmbGU7IDEwMDAwLCBhbmQgZCAmbGU7IDUwMDAwLiBZb3UgbWF5IGFzc3VtZSB0aGF0IGl0IGlzIHBvc3NpYmxlIHRvIG1lYXN1cmUgZCBtZyB1c2luZyBhIGNvbWJpbmF0aW9uIG9mIGEgbWcgYW5kIGIgbWcgd2VpZ2h0cy4gSW4gb3RoZXIgd29yZHMsIHlvdSBuZWVkIG5vdCBjb25zaWRlciAmcXVvdDtubyBzb2x1dGlvbiZxdW90OyBjYXNlcy48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHRocmVlIHplcm9zIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBJdCBpcyBub3QgYSBkYXRhc2V0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGJlIGNvbXBvc2VkIG9mIGxpbmVzLCBlYWNoIGNvcnJlc3BvbmRpbmcgdG8gYW4gaW5wdXQgZGF0YXNldCAoYSwgYiwgZCkuIEFuIG91dHB1dCBsaW5lIHNob3VsZCBjb250YWluIHR3byBub25uZWdhdGl2ZSBpbnRlZ2VycyB4IGFuZCB5IHNlcGFyYXRlZCBieSBhIHNwYWNlLiBUaGV5IHNob3VsZCBzYXRpc2Z5IHRoZSBmb2xsb3dpbmcgdGhyZWUgY29uZGl0aW9ucy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Zb3UgY2FuIG1lYXN1cmUgZCBtZyB1c2luZyB4IG1hbnkgYSBtZyB3ZWlnaHRzIGFuZCB5IG1hbnkgYiBtZyB3ZWlnaHMuPFwvbGk+XHJcblx0PGxpPlRoZSB0b3RhbCBudW1iZXIgb2Ygd2VpZ2h0cyAoeCArIHkpIGlzIHRoZSBzbWFsbGVzdCBhbW9uZyB0aG9zZSBwYWlycyBvZiBub25uZWdhdGl2ZSBpbnRlZ2VycyBzYXRpc2Z5aW5nIHRoZSBwcmV2aW91cyBjb25kaXRpb24uPFwvbGk+XHJcblx0PGxpPlRoZSB0b3RhbCBtYXNzIG9mIHdlaWdodHMgKGF4ICsgYnkpIGlzIHRoZSBzbWFsbGVzdCBhbW9uZyB0aG9zZSBwYWlycyBvZiBub25uZWdhdGl2ZSBpbnRlZ2VycyBzYXRpc2Z5aW5nIHRoZSBwcmV2aW91cyB0d28gY29uZGl0aW9ucy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5ObyBleHRyYSBjaGFyYWN0ZXJzIChlLmcuIGV4dHJhIHNwYWNlcykgc2hvdWxkIGFwcGVhciBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==