Poj Solution 3134

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

#include <stdio.h>



bool sign[1010];
int a[20];
int ans, best;

int search( int k, int big ) {
    int b = 1000, t, temp, sb;
    
    if( a[k] == ans ) {
        best = k;
        return 0;
    }

    if( k >= best )
        return 1000;
    
    int i;
    for( i=k, sb=big; sb<ans; sb<<=1, i++ )
        ;
    if( i >= best )
        return 1000;

    for( int i=k; i>=k && i>=0; i-- )
    for( int j=i; j>=0; j-- ) {
        if( a[i]+a[j] <= ans && !sign[ a[i]+a[j] ] ) {
            a[k+1] = a[i]+a[j];
        
            sign[ a[k+1] ] = true;
            
            sb = big;
            if( sb < a[k+1] )
                sb = a[k+1];
                
            t = search( k+1, sb );
            if( t < b ) b = t;
            sign[ a[k+1] ] = false;
        }
    }
    
    for( int i=k; i>=k && i>=0; i-- )
    for( int j=i-1; j>=0; j-- ) {
        if( a[i] > a[j] )
            temp = a[i]-a[j];
        else
            temp = a[j]-a[i];
        
        if( !sign[ temp ] ) {
            a[k+1] = temp;
            
            sb = big;
            if( sb < a[k+1] )
                sb = a[k+1];
                
            sign[ temp ] = true;
            t = search( k+1, sb );
            if( t < b ) b = t;
            sign[ temp ] = false;
        }
    }
    return b+1;
}

int main( ) {
    int n, i;

    while( scanf( "%d", &n ) == 1 && n ) {

        for( i=0; i<=n; i++ )
            sign[i] = false;
        ans = n;
        best = 13;
        a[0] = 1;
        search( 0, 1 );
        printf( "%dn", best );
    }
    return 0;
}