구간의 자리수 합
시간 제한1초메모리 제한128 MB
A와 B 사이의 정수 중 각 자리수의 합이 S인 수의 개수를 구하고 그 중 가장 작은 수를 출력합니다.
문제
정수의 각 자리의 합이란 10진수로 썼을 때 나타나는 모든 자리 숫자의 합입니다.
정수 A, B, S가 주어졌을 때, 구간 [A, B]에 속하는 정수 x 중 각 자리의 합이 S인 수가 몇 개인지 구하세요. 또한 그 조건을 만족하는 수 중 가장 작은 수를 구하세요.
입력은 조건을 만족하는 수가 적어도 하나 존재하도록 주어집니다.
입력
첫째 줄에 세 정수 A, B, S가 공백으로 구분되어 주어집니다.
- 1 ≤ A ≤ B < 10^15
- 1 ≤ S ≤ 135
출력
첫째 줄에 구간 [A, B]에 속하는 정수 중 각 자리의 합이 S인 수의 개수를 출력합니다.
둘째 줄에 그 조건을 만족하는 수 중 가장 작은 수를 출력합니다.