|
|
вернуться в форумDid anybody else solve this problem using backtracking? I used an optimized backtracking algorithm! I'm curious if anybody else found a similar solution. Anybody? i had solved it right now in 0.02 dont backtracking Re: Did anybody else solve this problem using backtracking? this is an exercise in dynamic programming. #include <stdio.h> #include <string.h> #define min(x,y) ( (x)<(y)?(x):(y) ) #define max(x,y) ( (x)>(y)?(x):(y) ) int gcd( int a, int b ){ if ( !a ) return b; return gcd(b%a,a); } int n, b, f; int ways[51][51][51]; int getways( int d, int g, int last ){ if ( d==n ) return 1; if ( ways[d][g][last] < 1000000 ) return ways[d][g][last]; int s=0, i,j; for ( i=last; i<=b; i++ ) if ( (j=gcd(i,g)) > 1 ) s=min( 10000, s+getways(d+1,j,i+1) ); return ways[d][g][last]=s; } int main( void ){ memset( ways, 66, sizeof(ways) ); scanf( "%d %d", &n, &b ); printf( "%d\n", getways(0,0,2) ); return 0; } > I used an optimized backtracking algorithm! I'm curious if anybody > else found a similar solution. Anybody? how did you optimize a backtracking algorithm to be fast enough? Inclusion relation... Hi Just find number of set (with size k) which have a prime common divisor such as for k=2 and prime=3 (s=12): {3, 6} {3, 9} {3,12} {6, 9} {6,12} {9,12} so do it for all prime numbers in range [1..50] then delete sets wich all number in it have 2 prime common divisor together... such delete sets which all have common divisor such as 6 (which is multpy of just 2 prime number) because set (6,12) both counted when prime was 2 and when prime was 3 and etc. and we have no set which its numbers has 3common prime divisor because first 3 primes are 2, 3 and 5 and 2*3*5=30 and at least 2*30>50 so it will get so simple :) Best Aidin_n7@hotmail.com Re: Did anybody else solve this problem using backtracking? Dudes! I know how to solve it!!!! I just asked if anybody else implemented a good enough backtracking to fit into the alloted time! That was all!!!! :D I made a DP exercise into a back optimization exercise! |
|
|