Poj Solution 2011

http://poj.org/problem?id=2011

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int ans[20], an;
int temp[20];

int get( int num, int s, int &r ) {
    int g = 0, tg=1, tr=1;
    bool key = true;
    r = 0;
    while( num ) {
        if( s & 1 ) {
            key = num%10;
            g += num%10*tg;
            tg *= 10;
        }
        else {
            r += num%10*tr;
            tr *= 10;
        }
        num /= 10;
        s >>= 1;
    }
    if( !key )
        return -1;
    else
        return g;
}

void search( int s, int k ) {
    temp[k++] = s;

    int m, t=s, i, r;
    for( m=0; t; m++, t/=10 )
        ;
    for( i=1; i<(1<<m)-1; i++ ) {
        t = get( s, i, r );
        if( t > 1 && s%t == 0 )
            search( r, k );
    }

    if( k > an || k == an && !std::lexicographical_compare( ans, ans+an, temp, temp+an ) ) {
        std::copy( temp, temp+k, ans );
        an = k;
    }
    return;
}

int main( ) {
    int n, i;
    while( scanf( "%d", &n ) == 1 && n ) {
        an = 0;
        search( n, 0 );
        for( i=0; i<an; i++ ) {
            if( i ) printf( " " );
            printf( "%d", ans[i] );
        }
        printf( "n" );
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *