AOJ 1016 Fibonacci Sets
問題
f(i) = f(i-1) + f(i-2)
フィボナッチ数です。で、1001で割って。 i...Vのノードがあって、iとjが
| F(i) - F(j) | < d
ならiとjは同じ集団に属している。 集団の数はいくつか
解法
Union_Find木を使うと解けます。 蟻本の出番。
コード
int par[N], rank[N]; void init(int n){ rep(i, n){ par[i] = i; rank[i] = 0; } } int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } 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]++; } } bool same(int x, int y){ return find(x) == find(y); } int V, d; int f[N]; int main(){ f[0] = 1; f[1] = 2; REP(i, 2, N) f[i] = (f[i-1] + f[i-2])%1001; while(~scanf("%d%d", &V, &d)){ init(V+1); REP(i, 1, V+1){ REP(j, i+1, V+1){ if(abs(f[j]-f[i]) < d) unite(i, j); } } int res = 0; REP(i, 1, V+1) if(par[i] == i) res++; printf("%d\n", res); } return 0; }