2013年11月24日 星期日

UVa 640 - Self Numbers

Problem link

Keyword: ad hoc, search

Algorithm:

Implement function d specified in the problem.
Use a for loop, and if the current one is not marked yet, search through this sequence and mark those who are not self numbers.
After that, use another for loop to print all self numbers.

Code:
#include<cstdio>
bool self[ 1000001 ] = { false };
int d( int i )
{
    int back = i;
    while( i )
        back += i % 10, i /= 10;
    return back;
}

int main()
{
    for( int i = 1; i <= 1000000; ++i )
        if( !self[ i ] )
            for( int tmp = d( i ); tmp <= 1000000 && !self[ tmp ]; tmp = d( tmp ) )
                self[ tmp ] = true;
    for( int i = 1; i <= 1000000; ++i )
        if( !self[ i ] )
            printf( "%d\n", i );
    return 0;
}

沒有留言:

張貼留言