首页 > 代码库 > poj 2719 Faulty Odometer

poj 2719 Faulty Odometer

题意:

     有辆车的里程表坏了,会跳过数字4,比如 3 接下来直接到5,再比如39 - 50  13 -15 239-259 39999-50000(好吧,该换车了)。如果车的里程表显示走了n公里,求实际走了多少。

打标找到了规律前10个少了1, 100少了19, 1000少了19×9+100=271, 10000中少了271*9+1000 = 2439 ............. 规律很明显了吧!!  

遇题多思考,像这种题,看到数据量就知道暴力是不可能的,所以就不需要再尝试了,浪费时间,尤其是在正式比赛的时候。

以下是本人的拙代码

#include <stdio.h>

int main()
{
    int n;
    while (scanf("%d", &n) && n)
    {
        int ans = n;
        int x = n/10;
        int dec = 1;
        int mul = 10;
        while (x)
        {
            int mod = x%10;
            if (mod >= 4)
                ans -= (mod-1)*dec + mul;
            else 
                ans -= mod*dec;
            dec = dec*9 + mul;
            mul *= 10;
            x /= 10;
        }
        if (n%10 >= 4)
            ans--;
        printf("%d: %d\n", n, ans);
    }
    return 0;
}