Wednesday, June 17, 2015

UVa 10183 - How Many Fibs?

// UVa 10183 - How Many Fibs?

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		BigInteger lim = BigInteger.valueOf(10).pow(100);

		int n = 1;
		ArrayList<BigInteger> fib = new ArrayList<BigInteger>();
		fib.add(BigInteger.ONE);
		fib.add(BigInteger.valueOf(2));
		while (true) {
			n++;
			fib.add(fib.get(n - 1).add(fib.get(n - 2)));
			if (fib.get(n).compareTo(lim) > 0)
				break;
		}

		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextBigInteger()) {
			BigInteger a = scanner.nextBigInteger();
			BigInteger b = scanner.nextBigInteger();
			if (a.compareTo(b) == 0 && a.compareTo(BigInteger.ZERO) == 0)
				break;
			int i = 0;
			while (fib.get(i).compareTo(a) < 0)
				i++;
			int j = i;
			while (fib.get(j).compareTo(b) <= 0)
				j++;
			System.out.println(j - i);
		}
	}

}

No comments:

Post a Comment