[SGU390]售票

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file sgu390_tickets.in Output file sgu390_tickets.out

【题目描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

40 218 57

【样例输出】

29

【来源】

SGU 390 Tickets