OI题库

【题目描述】

售票员是一个相当无聊的职业，因为你需要做的仅仅是把票卖给乘客。难怪很久很久以前，在一个遥远的星系中，一名售票员决定丰富他的职业生涯。现在这位售票员每次给一位乘客卖若干张票。更准确地，他按编号从小到大连续给一位乘客车票，直到他给这位乘客的所有车票编号的数码之和不小于一个整数k。然后再对下一位乘客重复这一过程。最初售票员有一沓编号从l到r（含l,r）的车票。这种售票方法颇受欢迎，因为乘客们很高兴只花一张车票钱就能得到数张票。但还有一个坏处。因为每位乘客都能拿到若干张票，售票员有可能无法给所有乘客服务。你的任务是在这种困难的情况下帮助售票员。你要计算出售票员能服务多少名乘客。

【输入格式】

输入一行三个整数l,r,k(1<=l<=r<=10^18,1<=k<=1000)。

【输出格式】

输出一行一个整数，即售票员最多能买票给多少名乘客。

【样例输入】

40 218 57

【样例输出】

29

【来源】

SGU 390 Tickets