U E D R , A S I H C RSS

How Many Fibs?/문보창

소감

2006-01-06 Accepted 0.008 Minimum

코드

~cpp
// 10183 - How many Fibs?
#include <iostream>
using namespace std;
#include <vector>
#include <cstring>

#define BIG 1
#define SMALL 2
#define TIE 3
    
class BigInteger
{
public:
	char digit[103];
	int len;
public:
	void nextBigInteger()
	{
		char temp[105];
		cin >> temp;
		len = strlen(temp);
		for (int i = 0; i < len; i++)
			digit[i] = temp[len-i-1] - 48;
	}
	void findPibNum(BigInteger& a, BigInteger& b)
	{
		int carry = 0;
		len = 0;
		while (len < a.len || len < b.len)
		{
			if (len > a.len)
			{
				digit[len] = (b.digit[len] + carry) % 10;
				carry = (b.digit[len] + carry) / 10;
			}
			else if (len > b.len)
			{
				digit[len] = (a.digit[len] + carry) % 10;
				carry = (a.digit[len] + carry) / 10;
			}
			else
			{
				digit[len] = (a.digit[len] + b.digit[len] + carry) % 10;
				carry = (a.digit[len] + b.digit[len] + carry) / 10;
			}
			len++;
		}
		if (carry > 0)
			digit[len++] = carry;
	}
	int isBigThan(BigInteger& a)
	{
		if (len > a.len)
			return BIG;
		else if (len < a.len)
			return SMALL;
		for (int i = len - 1; i >= 0; i--)
		{
			if (digit[i] > a.digit[i])
				return BIG;
			else if (digit[i] < a.digit[i])
				return SMALL;
		}
		return TIE;
	}
};

static BigInteger inA, inB;
static BigInteger pib[481];

void preProcess()
{
	pib[1].digit[0] = 1, pib[1].len = 1;
	pib[2].digit[0] = 2, pib[2].len = 1;

	for (int i = 3; i <= 480; i++)
		pib[i].findPibNum(pib[i-1], pib[i-2]);
}

bool input()
{
	inA.nextBigInteger();
	inB.nextBigInteger();
	if (inA.len == 1 && inB.len == 1 && inA.digit[0] == 0 && inB.digit[0] == 0)
		return false;
	return true;
}

void process()
{
	int i, count = 0;
	int response;
	for (i = 1; i <= 480; i++)
	{
		response = inA.isBigThan(pib[i]);
		if (response != BIG)
			break;
	}
	for (; i <= 480; i++)
	{
		response = inB.isBigThan(pib[i]);
		if (response == SMALL)
			break;
		count++;
	}
	cout << count << endl;
}

int main()
{
	preProcess();
	while (input())
		process();
	return 0;
}
----
HowManyFibs?
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:25
Processing time 0.0116 sec