UVa 962 - Taxicab Numbers

Problem link

Keyword: binary search, linear search, sort, pre-generation

Algorithm:

First you have to generate all results of sum of two cubic numbers.
Next, sort them in ascending order.
Last, use linear search to check if such a number exists.
Please note that because the upper bound may be greater than 1E9, you have to generate up to maybe 1005, not just 1000.

Code:

#include<cstdio>
#include<algorithm>
using namespace std;
int allcube[ 1005 ], taxicab[ 505520 ] = { 0 };

int main()
{
    int low, range, all = 0;
    for( int i = 1; i <= 1005; ++i )
        allcube[ i-1 ] = i*i*i;
    for( int i = 0; i < 1005; ++i )
        for( int j = i; j < 1005; ++j )
            taxicab[ all++ ] = allcube[ i ] + allcube[ j ];
    sort( taxicab, taxicab+all );

    while( scanf( "%d %d", &low, &range ) != EOF )
    {
        bool out = false;
        int *begin = lower_bound( taxicab, taxicab+all, low ), *end = upper_bound( taxicab, taxicab+all, low+range );
        for( int *ptr = begin; ptr != end; ++ptr )
            if( ( ptr == taxicab || *ptr != *( ptr-1 ) ) && *ptr == *( ptr+1 ) )
                out = true, printf( "%d\n", *ptr );
        if( !out )
            puts( "None" );
    }

    return 0;
}