HDU 4956 Poor Hanamichi(BestCoder Round #5)

Problem Description:

Hanamichi is taking part in a programming contest, and he is assigned to solve a special problem as follow: Given a range [l, r] (including l and r), find out how many numbers in this range have the property: the sum of its odd digits is smaller than the sum of its even digits and the difference is 3.

A integer X can be represented in decimal as:
X=An×10n+An−1×10n−1+…+A2×102+A1×101+A0
The odd dights are A1,A3,A5… and A0,A2,A4… are even digits.

Hanamichi comes up with a solution, He notices that:
102k+1 mod 11 = -1 (or 10), 102k mod 11 = 1, 
So X mod 11 
= (An×10n+An−1×10n−1+…+A2×102+A1×101+A0)mod11
= An×(−1)n+An−1×(−1)n−1+…+A2−A1+A0
= sum_of_even_digits – sum_of_odd_digits
So he claimed that the answer is the number of numbers X in the range which satisfy the function: X mod 11 = 3. He calculate the answer in this way : 
Answer = (r + 8) / 11 – (l – 1 + 8) / 11.

Rukaw heard of Hanamichi’s solution from you and he proved there is something wrong with Hanamichi’s solution. So he decided to change the test data so that Hanamichi’s solution can not pass any single test. And he asks you to do that for him.

 

Input:

You are given a integer T (1 ≤ T ≤ 100), which tells how many single tests the final test data has. And for the following T lines, each line contains two integers l and r, which are the original test data. (1 ≤ l ≤ r ≤ 1018)

 

Output:

You are only allowed to change the value of r to a integer R which is not greater than the original r (and R ≥ l should be satisfied) and make Hanamichi’s solution fails this test data. If you can do that, output a single number each line, which is the smallest R you find. If not, just output -1 instead.

 

Sample Input:

3

3 4

2 50

7 83

 

Sample Output:

-1

-1

80

 

题意：这道题绝对存在着赤裸裸的误导，题目长不说，废话一堆。。。。就是给你两个数l和r，判断这两个数之间的数有多少数的偶数位和比奇数位和大3，有一个人想了一种方法计算这种结果：Answer = (r + 8) / 11 – (l – 1 + 8) / 11，现在另一个人质疑他的做法，现在他想改变r的值（必须保证改过的r还是>=l且<=之前的r），改变之后让之前的方法判断失误，找到最小的r，那么我们就可以拿直接判断的值和那个人的做法比较，不满足的时候就是可以 找到这种r了。。。。

看完题之后感觉题意就是这样，然后就想怎么做呢，想了暴力，发现l和r是10e18，顿时。。。。然后发现第三个样例80就不满足了，那么根本不会循环很多次，break就好了，感觉很对，但是提交wa，又看题发现数位数时是从0开始的，改完之后连样例都不对了。。。然后就搜了题解，发现这道题竟然是从右往前数，顿时疯了。。。。（但是到现在也没有发现题中哪里说了这句话）

#include<stdio.h>
#define min(a, b) (a < b ? a : b)

const int INF=0x3f3f3f3f;

int Judge(__int64 a)
{
    __int64 A, B, C;

    A = B = C = 0;

    while (a > 0)
    {
        C++;
        if (C % 2 != 0) B += a % 10;
        else A += a % 10;
        a /= 10;
    }

    if (B - A == 3) return 1;
    else return 0;
}

int main ()
{
    int T;
    __int64 l, r, X, x, i, ans;

    scanf("%d", &T);

    while (T--)
    {
        x = 0;
        ans = -1;

        scanf("%I64d %I64d", &l, &r);

        for (i = l; i <= r; i++)
        {
            X = (i+8)/11 - (l-1+8)/11;

            if (Judge(i))
                x++;

            if (x != X)
            {
                ans = i;
                break;
            }
        }

        printf("%I64d
", ans);
    }

    return 0;
}