AOJ - Problem 1016 : Fibonacci Sets
整数v, dが与えられます。
v個のノードがあり番号が1..vまで付けられています。ノードiとノードjについて|(f(i)-f(j)) mod 1001| < d のときノードiとノードjは同じ集合に属します。
異なる集合の数を求めます。Union-Findを使うと良さそうな問題でした。
#include <iostream> #include <algorithm> using namespace std; const int MAX_N = 1001; int f[MAX_N+1] = {2,3}; int par[MAX_N]; int rank[MAX_N]; // フィボナッチ数列の計算 void fib_init(){ for(int i = 2 ; i < MAX_N+1 ; i++ ){ f[i] = (f[i-1] + f[i-2]) % MAX_N; } } // 初期化 void init(int n){ for(int i=0 ; i < n ; i++ ){ par[i] = i; rank[i] = 0; } } // x の root を求める int find(int x){ if( par[x] == x ){ return x; }else{ return par[x] = find( par[x] ); } } // x と y の属する集合の併合 void unite(int x, int y){ x = find(x); y = find(y); if( x == y ) return ; if( rank[x] < rank[y] ){ par[x] = y; }else{ par[y] = x; if( rank[x] == rank[y] ) rank[x]++; } } // x と y が同じ集合に属するかどうか bool same(int x, int y){ return find(x) == find(y); } int main(){ fib_init(); int v, d; while( cin >> v >> d ){ init( v ); int memo[MAX_N+1] = {0}; // |f(i) - f(j)| < d となるとき i と j は同じ集合に属する for(int i=0 ; i < v ; i++ ){ for(int j=i+1 ; j < v ; j++ ){ if( abs( f[i] - f[j] ) < d ){ unite( i , j ); } } } // 集合の個数を数える int ans=0; for(int i=0 ; i < v ; i++ ){ int root = find(i); if( memo[root] == 0 ){ memo[root] = 1; ans++; } } // 出力 cout << ans << endl; } }