Problem:


Problem H: Fibonacci Sets

Fibonacci number f(i) appear in a variety of puzzles in nature and math, including packing problems, family trees or Pythagorean triangles. They obey the rule f(i) = f(i - 1) + f(i - 2), where we set f(0) = 1 = f(-1).

V and d be two certain positive integers and be N &equiv; 1001 a constant. Consider a set of V nodes, each node i having a Fibonacci label (f(i) mod N) assigned for i = 1,..., V ≤ N. If |f(i) - f(j)| < d, then the nodes i and j are connected.

-->

Let V and d be two certain positive integers and be N &equiv; 1001 a constant. Consider a set of V nodes, each node i having a Fibonacci label F[i] = (f(i) mod N) assigned for i = 1,..., V ≤ N. If |F(i) - F(j)| < d, then the nodes i and j are connected.

Given V and d, how many connected subsets of nodes will you obtain?

Figure 1: There are 4 connected subsets for V = 20 and d = 100.

Input

Each data set is defined as one line with two integers as follows:

Line 1: Number of nodes V and the distance d.

Input includes several data sets (i.e., several lines). The number of dat sets is less than or equal to 50.

Constraints

1 ≤ V ≤ 1000

1 ≤ d ≤ 150

Output

Output line contains one integer - the number of connected subsets - for each input line.

Sample Input

5 5
50 1
13 13

Output for the Sample Input

2
50
8



Sample input:
5 5
50 1
13 13


Sample output:
2
50
8

Submission status: Wrong Answer

Solution code:
while 1:
    try:
        v,d=map(int,input().split())
        f=[0]*(v+1)
        f[0],f[1]=1,2
        for i in range(2,v+1):
            f[i]=f[i-1]+f[i-2]
        f.sort()
        c=1
        for i in range(2,v+1):
            if f[i]-f[i-1]>=d: c+=1
        print(c)
    except:break

Submission status: Accepted

Solution code:
while 1:
    try:
        v,d=map(int,input().split())
        f=[0]*(v+1)
        f[0],f[1]=1,2
        for i in range(2,v+1):
            f[i]=(f[i-1]+f[i-2])%1001
        f.sort()
        c=1
        for i in range(2,v+1):
            if f[i]-f[i-1]>=d: c+=1
        print(c)
    except:break

Submission status: Accepted

Solution code:
while(1):
    try:
        [v,d]=map(int,raw_input().split())
    except:
        break
    fib=[1 for x in range(v+2)]
    for i in range (2,v+2):
        fib[i]=fib[i-1]+fib[i-2]
    fib.pop(0)
    fib.pop(0)
    fibm=sorted([x%1001 for x in fib])
    ans=1
    for i in range(v-1):
        if fibm[i+1]-fibm[i]>=d:    ans+=1
    print ans

Submission status: Accepted

Solution code:
# AOJ 1016: Fibonacci Sets
# Python3 2018.7.4 bal4u

f = [0]*1001
f[0], f[1] = 2, 3
for i in range(2, 1001): f[i] = (f[i-1]+f[i-2])%1001
while True:
	try: V, d = map(int, input().split())
	except: break
	ans, a = 1, sorted(f[:V])
	for i in range(1, V):
		if a[i]-a[i-1] >= d: ans += 1
	print(ans)

Submission status: Accepted

Solution code:
import os
import sys

for line in sys.stdin:
    v, d = [int(item) for item in line.split()]

    fib = [1,1]

    for i in xrange(v):
        fib.append((fib[-1]+fib[-2])%1001)

    fib = sorted(fib[2:])

    count = 1
    for i in xrange(len(fib)-1):
        if fib[i+1]-fib[i] >= d: count += 1

    print count

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 1001
INF = 10 ** 15

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1]*n

    def find(self,x): #根を見つける、繋ぎ直す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def unite(self,x,y): #x,yの含むグループを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x,y = y,x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self,x,y):#xとyが同じグループにいるか判定
        return self.find(x) == self.find(y)
    
    def members(self,x):#xと同じグループのメンバーを列挙
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def size(self,x):#xが属するグループのメンバーの数
        return -self.parents[self.find(x)]
    
    def roots(self):#ufの根を列挙
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):#グループの数を数える
        return len(self.roots())

def solve(V,d,fib):
    uf  = UnionFind(V)
    for i in range(V):
        for j in range(i + 1,V):
            if abs(fib[i] - fib[j]) < d:
                uf.unite(i,j)
    ans = uf.group_count()
    print(ans)

def main():
    fib = [0] * 1005
    fib[0] = 2; fib[1] = 3
    for i in range(2,1005):
        fib[i] = fib[i - 1] + fib[i - 2]
        fib[i] %= MOD
    
    while True:
        try:
            V,d = map(int,input().split())
            solve(V,d,fib)
        except:
            return
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def initSets(N):
    return [ x for x in range(N) ]

def getRoot(arr, n):
    while arr[n] != n:
        arr[n] = arr[arr[n]]
        n = arr[n]
    return n

def union(arr, n, m):
    a = getRoot(arr, n)
    b = getRoot(arr, m)
    if a != b:
        arr[a] = b

def isSameSet(arr, n, m):
    return getRoot(arr, n) == getRoot(arr, m)

def getFibs():
    fibs = []
    a = 1
    b = 1
    while len(fibs) < 1000:
        c = (a + b) % 1001
        a = b
        b = c
        fibs.append(c)
    return fibs
        
if __name__ == '__main__':
    try:
        FIBS = getFibs()
        while True:
            V, d = list(map(int, input().strip().split()))

            fibs = FIBS[:V]
            arr = initSets(V)

            for i in range(V):
                for j in range(i + 1, V):
                    if abs(fibs[i] - fibs[j]) < d:
                        union(arr, i, j)
            
            subsets = {}
            for i in range(V):
                root = getRoot(arr, i)
                if root in subsets:
                    subsets[root].append(fibs[i])
                else:
                    subsets[root] = [fibs[i]]

            print(len(subsets))

    except EOFError:
        pass

Submission status: Accepted

Solution code:
from collections import deque
try:
    while 1:
        V, d = map(int, input().split())
        F = [0]*V
        a = b = 1
        for v in range(V):
            a, b = (a+b) % 1001, a
            F[v] = a
        G = [[] for i in range(V)]
        for i in range(V):
            for j in range(i+1, V):
                if abs(F[i] - F[j]) < d:
                    G[i].append(j)
                    G[j].append(i)
        L = [0]*V
        ans = 0
        for i in range(V):
            if L[i]:
                continue
            ans += 1
            que = deque([i])
            L[i] = 1
            while que:
                v = que.popleft()
                for w in G[v]:
                    if L[w]:
                        continue
                    que.append(w)
                    L[w] = 1
        print(ans)
except:
    ...

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

for line in sys.stdin:
    V, d = map(int, line.split())
    N = [False for i in range(2000)]
    p = pp = 1
    for i in range(V):
        num = (p + pp) % 1001
        N[num] = True
        p = pp
        pp = num
    ans = 0
    p = -10000
    for i in range(2000):
        if N[i]:
            if i - p >= d:
                ans += 1
            p = i
    print ans