## 2013年10月18日 星期五

### UVa 962 - Taxicab Numbers

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;}`