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

```
This entry was posted in poj. Bookmark the permalink.