763 - Fibinary Numbers

[outsbook]

Try this
Input:

Code: Select all

100000001010001010001010001000101000101000101000010000000101000101000101000100010100010100010100001
100000001010001010001010001000101000101000101000010000000101000101000101000100010100010100010100001

Output:

Code: Select all

1001000100001001001001001000100100100100100100010100100010000100100100100100010010010010010010001010

[Yusif]

I'm getting RE
Can anybody help?

Code: Select all

ac

[brianfry713]

From uhunt:
Siegrift> in your while loop when i = 199 and the first if statement is TRUE you want to index the S array with index 200

[Yusif]

I changed that to 198 and then to 140 yet the same result!

[brianfry713]

Try input:

Code: Select all

0
0

[Yusif]

Got it; thank you!

[darksk4]

What's wrong with this code?

Code: Select all

AC

The Input and the output is correct @_@. hmm... any suggestion why I'm getting WA.

[brianfry713]

The output may have more than 100 digits, it is less than 106 digits.

[darksk4]

thanks haha I see @_@ I thought it's my algorithm thanks

[rafid059]

Getting wrong answer Don't bother with the package name and the class name

Code: Select all

Silly mistakes  :P  Thanks BrianFry  :)

[brianfry713]

Don't use a package, use class Main. Post the code you'd actually submit.

[brianfry713]

Input:

Code: Select all

1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010

AC output:

Code: Select all

100010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101001

[rafid059]

I get the same output

[brianfry713]

The code you posted does not, see http://ideone.com/xZxG9d

[RookiE3]

Why am I getting RE?? The code uses a BigInteger class made by myself

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;

#define MODDER 1000000000
#define DIGITSIZE 9
//#define MODDER 10000
//#define DIGITSIZE 4
#define INT32 int
#define INT64 long long

class BigInteger
{
	vector<int> digit;
	short signum;
	static bool CHECK;
	int setSignum(INT64&);
	BigInteger add(const BigInteger &) const;
	BigInteger subtract(const BigInteger &) const;
	char* trim(char *);
public:
	BigInteger() { signum = 0; }
	BigInteger(INT64);
	BigInteger(char*);
	BigInteger(string&);
	BigInteger(const BigInteger&);
	BigInteger operator = (INT64);
	BigInteger operator = (char *);
	BigInteger operator = (string &);
	BigInteger operator = (BigInteger);
	BigInteger operator + (const BigInteger&) const;
	BigInteger operator - (const BigInteger&) const;
	bool operator == (const BigInteger&) const;
	bool operator < (const BigInteger&) const;
	bool operator <= (const BigInteger&) const;
	void setCheck(bool check);
	string toString();
	void printDigit();
};

bool BigInteger::CHECK;

inline int BigInteger::setSignum(INT64 &n)
{
	if (n == 0)
		signum = 0;
	else if (n > 0)
		signum = 1;
	else
	{
		signum = -1;
		n = -n;
	}
	return signum;
}

BigInteger BigInteger::add(const BigInteger &b) const
{
	BigInteger temp;
	int i;
	int len1 = digit.size();
	int len2 = b.digit.size();
	int minLen = len1 < len2 ? len1 : len2;
	int digitSum = 0, carry = 0;
	for (i = 0; i < minLen; i++)
	{
		digitSum = carry + digit[i] + b.digit[i];
		temp.digit.push_back(digitSum % MODDER);
		carry = digitSum / MODDER;
	}
	if (len1 == len2 && carry)
		temp.digit.push_back(carry);
	else if (len1 > len2)
	{
		while (i < len1)
		{
			digitSum = carry + digit[i++];
			temp.digit.push_back(digitSum % MODDER);
			carry = digitSum / MODDER;
		}
		if (carry)
			temp.digit.push_back(carry);
	}
	else
	{
		while (i < len2)
		{
			digitSum = carry + b.digit[i++];
			temp.digit.push_back(digitSum % MODDER);
			carry = digitSum / MODDER;
		}
		if (carry)
			temp.digit.push_back(carry);
	}
	temp.signum = 1;
	return temp;
}

BigInteger BigInteger::subtract(const BigInteger &b) const
{
	BigInteger temp;
	int size = b.digit.size();
	int borrow = 0, prevBorrow = 0, i;
	for (i = 0; i < size; i++)
	{
		borrow = (digit[i] - prevBorrow) < b.digit[i] ? 1 : 0;
		temp.digit.push_back((digit[i] - prevBorrow) + borrow*MODDER - b.digit[i]);
		prevBorrow = borrow ? 1 : 0;
	}
	int biggerSize = digit.size();
	while (i < biggerSize)
	{
		temp.digit.push_back(digit[i] - prevBorrow);
		i++;
		prevBorrow = 0;
	}
	i--;
	while (temp.digit[i] == 0)
	{
		temp.digit.pop_back();
		i--;
	}
	temp.signum = 1;
	return temp;
}

char* BigInteger::trim(char *n)
{
	int len = strlen(n);
	int index = 0, i;
	char *nnew = new char[len];

	if (n[0] == '-' || n[0] == '+')
	{
		nnew[0] = n[0];
		index++;
	}
	for (i = index; n[i] == '0'; i++);
	if (i == len)
		return "0";
	if (i != index)
	{
		while (i != len)
			nnew[index++] = n[i++];
	}
	nnew[index] = NULL;
	return nnew;
}

BigInteger::BigInteger(INT64 n)
{
	setSignum(n);
	while (n)
	{
		digit.push_back(n % MODDER);
		n /= MODDER;
	}
}

BigInteger::BigInteger(char *n)
{
	if (((n[0] == '+' || n[0] == '-') && n[1] == '0') || n[0] == '0')
		n = trim(n);

	int length, msb;
	char tempDigit[DIGITSIZE + 1];
	for (length = msb = 0; n[length] != 0; length++)
	{
		if (n[length] == '0')
			msb++;
	}
	if (msb == length)
	{
		signum = 0;
		return;
	}

	if (n[0] == '-')
	{
		signum = -1;
		length--;
		msb = 1;
	}
	else if (n[0] == '+')
	{
		signum = 1;
		length--;
		msb = 1;
	}
	else
	{
		signum = 1;
		msb = 0;
	}

	if (length <= DIGITSIZE)
	{
		memcpy(tempDigit, n + msb, length);
		tempDigit[length] = '\0';
		digit.push_back(stoll(tempDigit));
	}
	else
	{
		int k = length, chunkLen;
		while (k != 0)
		{
			k -= DIGITSIZE;
			chunkLen = k >= 0 ? DIGITSIZE : k + DIGITSIZE;
			k = k < 0 ? 0 : k;

			memcpy(tempDigit, n + msb + k, chunkLen);
			tempDigit[chunkLen] = '\0';
			digit.push_back(stoll(tempDigit));
		}
	}
}

BigInteger::BigInteger(string &n)
{
	int l = n.length();
	char *num = new char[l + 1];
	for (int i = 0; i < l; i++)
		num[i] = n[i];
	num[l] = NULL;
	(*this) = num;
}

BigInteger::BigInteger(const BigInteger &n)
{
	digit = n.digit;
	signum = n.signum;
}

BigInteger BigInteger::operator=(INT64 n)
{
	digit.clear();
	if (setSignum(n) == 0)
		return "0";
	while (n)
	{
		digit.push_back(n % MODDER);
		n /= MODDER;
	}
	return *this;
}

BigInteger BigInteger::operator=(char *n)
{
	BigInteger temp(n);
	(*this) = temp;
	return *this;
}

BigInteger BigInteger::operator=(string &n)
{
	BigInteger temp(n);
	(*this) = temp;
	return *this;
}

BigInteger BigInteger::operator=(BigInteger b)
{
	digit = b.digit;
	signum = b.signum;
	return *this;
}

BigInteger BigInteger::operator+(const BigInteger &b) const
{
	if (b.signum == 0)
		return *this;
	if (signum == 0)
		return b;

	if (signum == 1 && b.signum == 1)
		return (*this).add(b);
	if (signum == 1 && b.signum == -1)
		return (*this).subtract(b);
	if (signum == -1 && b.signum == 1)
		return b.subtract(*this);
	BigInteger temp = (*this).add(b);
	if (temp.signum == 1)
		temp.signum = -1;
	return temp;
}

BigInteger BigInteger::operator-(const BigInteger &b) const
{
	if ((*this) == b)
		return "0";
	if (signum == 1 && b.signum == 1)
	{
		if (*this < b)
		{
			BigInteger temp = b.subtract((*this));
			temp.signum = -1;
			return temp;
		}
		else
			return (*this).subtract(b);
	}
	if (signum == 1 && b.signum == -1)
		return (*this).add(b);
	if (signum == -1 && b.signum == 1)
	{
		BigInteger temp = (*this).add(b);
		temp.signum = -1;
		return temp;
	}
	if (*this < b)
	{
		BigInteger temp = (*this).subtract(b);
		temp.signum = -1;
		return temp;
	}
	return b.subtract((*this));
}

bool BigInteger::operator==(const BigInteger &b) const
{
	if (signum != b.signum)
		return false;
	if (signum == 0)
		return true;
	int size1 = digit.size();
	int size2 = b.digit.size();
	if (size1 == size2)
	{
		int i = 0;
		while (i < size1)
		{
			if (digit[i] == b.digit[i])
				i++;
			else
				return false;
		}
		if (i == size1)
			return true;
	}
	return false;
}

bool BigInteger::operator<(const BigInteger &b) const
{
	if (signum != b.signum)
		return signum < b.signum;
	int size1 = digit.size();
	int size2 = b.digit.size();
	switch (signum)
	{
	case 1:
		if (size1 == size2)
		{
			int i = size1 - 1;
			while (i >= 0)
			{
				if (digit[i] == b.digit[i])
					i--;
				else
					return digit[i] < b.digit[i];
			}
			if (i == size1)
				return false;
		}
		return size1 < size2;
	case -1:
		if (size1 == size2)
		{
			int i = size1 - 1;
			while (i >= 0)
			{
				if (digit[i] == b.digit[i])
					i--;
				else
					return digit[i] > b.digit[i];
			}
			if (i == size1)
				return false;
		}
		return size1 > size2;
	}
}

bool BigInteger::operator<=(const BigInteger &b) const
{
	if (*this < b || *this == b)
		return true;
	return false;
}

inline void BigInteger::setCheck(bool check)
{
	CHECK = check;
}

string BigInteger::toString()
{
	if (signum == 0)
		return "0";

	int length = digit.size();
	string number, temp;
	int len;

	number = to_string(digit[length - 1]);

	for (int i = length - 2; i >= 0; i--)
	{
		temp = to_string(digit[i]);
		len = temp.length();
		if (len != DIGITSIZE)
			temp.insert(0, DIGITSIZE - len, '0');
		number += temp;
	}
	if (signum == -1)
		return "-" + number;
	return number;
}

void BigInteger::printDigit()
{
	for (int i = 0; i < digit.size(); i++)
		printf("digit %d: %d\n", i, digit[i]);
}

BigInteger fib[120];

string toFibinary(BigInteger &b)
{
	vector<int> chosenFibs;
	int i = 1, length;
	while (fib[i] <= b)
	{
		i++;
	}
	length = i - 1;
	i -= 2;
	chosenFibs.push_back(length);

	b = b - fib[length];
	BigInteger zero;
	while (!(b == zero))
	{
		while (b < fib[i])
			i--;
		b = b - fib[i];
		chosenFibs.push_back(i);
	}
	char *fibinary = new char[length];
	memset(fibinary, '0', length);
	for (int i = 0; i < chosenFibs.size(); i++)
		fibinary[length - chosenFibs[i]] = '1';
	fibinary[length] = NULL;
	return fibinary;
}

int main()
{
	fib[1] = 1;
	fib[2] = 2;
	for (int i = 3; i < 120; i++)
		fib[i] = fib[i - 1] + fib[i - 2];

	string n1, n2;
	BigInteger sum;
	int len, i;
	while (cin >> n1 >> n2)
	{
		if (n1 == "0" && n2 == "0")
		{
			printf("0\n\n");
			continue;
		}
		len = n1.length();
		for (i = 0; i < len; i++)
		{
			if (n1[i] == '1')
				sum = sum + fib[len - i];
		}
		len = n2.length();
		for (i = 0; i < len; i++)
		{
			if (n2[i] == '1')
				sum = sum + fib[len - i];
		}
		cout << toFibinary(sum) << endl << endl;
		sum = "0";
	}
	return 0;
}