시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 65 21 21 52.500%

문제

상근이는 매일 친구들에게 이상한 문제를 낸다.

오늘은 "각 자리의 합이 S가 되는 숫자가 구간 [A,B]에는 몇 개가 있을까? 또, 그러한 숫자 중에서 가장 작은 수는 뭘까?"

창영이는 이 질문의 답을 찾느라 3일 연속으로 밤을 샜다. 창영이가 잠을 잘 수 있게 대신 상근이 질문의 정답을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, S가 주어진다. (1 ≤ A ≤ B < 1015, 1 ≤ S ≤ 135)

출력

첫째 줄에는 구간 [A,B]에 속하는 숫자 중 각 자리의 합이 S가 되는 수의 개수를 출력한다. 이 값이 적어도 1인 구간과 S만 입력으로 주어진다.

둘째 줄에는 그러한 수 중에서 가장 작은 수를 출력한다.

예제 입력 1

1 9 5

예제 출력 1

1
5
W3sicHJvYmxlbV9pZCI6IjMwMDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWMwYzFcdWQ1NWMgXHViYjM4XHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViOWU0XHVjNzdjIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWM3NzRcdWMwYzFcdWQ1NWMgXHViYjM4XHVjODFjXHViOTdjIFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViMjk4XHVjNzQwICZxdW90O1x1YWMwMSBcdWM3OTBcdWI5YWNcdWM3NTggXHVkNTY5XHVjNzc0IFNcdWFjMDAgXHViNDE4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFkNmNcdWFjMDQgW0EsQl1cdWM1ZDBcdWIyOTQgXHViYTg3IFx1YWMxY1x1YWMwMCBcdWM3ODhcdWM3NDRcdWFlNGM/IFx1YjYxMCwgXHVhZGY4XHViN2VjXHVkNTVjIFx1YzIyYlx1Yzc5MCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWIyOTQgXHViYjU4XHVhZTRjPyZxdW90OzxcL3A+XHJcblxyXG48cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YzljOFx1YmIzOFx1Yzc1OCBcdWIyZjVcdWM3NDQgXHVjYzNlXHViMjkwXHViNzdjIDNcdWM3N2MgXHVjNWYwXHVjMThkXHVjNzNjXHViODVjIFx1YmMyNFx1Yzc0NCBcdWMwZGNcdWIyZTQuIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWM3YTBcdWM3NDQgXHVjNzk4IFx1YzIxOCBcdWM3ODhcdWFjOGMgXHViMzAwXHVjMmUwIFx1YzBjMVx1YWRmY1x1Yzc3NCBcdWM5YzhcdWJiMzhcdWM3NTggXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBBLCBCLCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBICZsZTsgQiAmbHQ7IDEwPHN1cD4xNTxcL3N1cD4sIDEgJmxlOyBTICZsZTsgMTM1KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZDZjXHVhYzA0IFtBLEJdXHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWMyMmJcdWM3OTAgXHVjOTExIFx1YWMwMSBcdWM3OTBcdWI5YWNcdWM3NTggXHVkNTY5XHVjNzc0IFNcdWFjMDAgXHViNDE4XHViMjk0IFx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzc0IFx1YzgwMVx1YzViNFx1YjNjNCAxXHVjNzc4IFx1YWQ2Y1x1YWMwNFx1YWNmYyBTXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4XHViN2VjXHVkNTVjIFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwMDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDVURBSyIsImRlc2NyaXB0aW9uIjoiPHA+Qm9cdTAxN2VvIGlzIGEgc3RyYW5nZSBsaXR0bGUgYm95LiBFdmVyeSBkYXkgaGUgdGlyZXMgaGlzIGZyaWVuZHMgd2l0aCBzdHJhbmdlIHF1ZXN0aW9ucy4gVG9kYXkmIzM5O3MgcXVlc3Rpb24gaXM6IGhvdyBtYW55IGludGVnZXJzIGluIHRoZSBpbnRlcnZhbCBbQSwgQl0gYXJlIHRoZXJlIHN1Y2ggdGhhdCB0aGUgc3VtIG9mIHRoZWlyIGRpZ2l0cyBpcyBTLCBhbmQgd2hpY2ggaXMgdGhlIHNtYWxsZXN0IHN1Y2ggbnVtYmVyPyZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBhbnN3ZXJzIEJvXHUwMTdlbyYjMzk7cyBxdWVzdGlvbiBzbyB0aGF0IGhlIGNhbiBnZXQgc29tZSBzbGVlcC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBBLCBCIGFuZCBTICgxICZsZTsgQSAmbGU7IEIgJmx0OyAxMDE1LCAxICZsZTsgUyAmbGU7IDEzNSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgaW50ZWdlcnMgaW4gdGhlIGludGVydmFsIHdpdGggdGhlIGRpZ2l0IHN1bSBlcXVhbCB0byBTLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIHNtYWxsZXN0IHN1Y2ggaW50ZWdlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IGRhdGEgd2lsbCBndWFyYW50ZWUgdGhhdCB0aGUgZmlyc3QgbnVtYmVyIGlzIGF0IGxlYXN0IDEuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #3 5번