UVa 846 - Steps

Problem link

Keyword: math

Algorithm:

Um... this problem's solution explanation seem to be a little difficult.
The basic idea is that the longest distance a sequence of steps can travel is 1, 2, 3, 4, ..., 4, 3, 2, 1.
For 1 step, the longest distance = 1.
For 2, it's 1 + 1 = 2.
For 3, it's 1+2+1=4.
For 4, it's 1+2+2+1=6.
For 5, it's 1+2+3+2+1=9.
After examine this pattern, you'll be able to find out a formula for this.

Code:

#include<cstdio>
#include<cmath>

int main()
{
    long long int x, y, t;
    scanf( "%lld", &t );

    while( t-- )
    {
        scanf( "%lld %lld", &x, &y ); 
        long long int dist = y-x, tmp = ceil( ( sqrt( dist*4 + 1 ) - 1 ) / 2 );
        if( tmp * tmp < dist && tmp * tmp + tmp >= dist || !tmp )
            printf( "%lld\n", tmp*2 );
        else
            printf( "%lld\n", tmp*2 - 1 );
    }

    return 0;
}