sgx和路飞

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

众所周知,sgx是个海贼迷。每个礼拜更新的海贼王他都不会放过。

这天晚上,他码完代码结果迷迷糊糊困得睡着了。梦中,他见到了偶像路飞。路飞碰巧没吃东西,想要去sgx家吃东西。

大家都知道,路飞是个大胃王。让他敞开吃的话sgx家就被吃穷了。但是又不能不让他吃。所以sgx就出了个题目给他:

在所有自然数集合中,给出区间[A, B],求在此区间内各位数字之和为 的最小数。

你们都是热心的海贼迷,可不能看着路飞饿肚子,而路飞又不懂代码,所以这个艰巨的任务就交给你们完成了。

Input

输入包含三个整数A, B, S (1 ≤ A ≤ B ≤ 10^18, 1 ≤ S ≤ 162).

Output

满足上述条件的最小元素数值。数据保证答案一定存在。

Sample Input

1 100 10

Sample Output

19

Hint

在1到100之间满足各位数字之和相加等于10的数字最小是19.

Source

sgx

Manager

Information
Solved Number147
Submit Number560
Problem Tags
binary search
dp
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel