763 - Fibinary Numbers

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 763 - Fibinary Numbers

Post by brianfry713 »

That code won't compile.

In case that two or more test cases had to be solved, it must be a blank line between two consecutive, both in input and output files.
Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!
Top
RookiE3
New poster
Posts: 16
Joined: Tue Feb 18, 2014 7:59 pm

Re: 763 - Fibinary Numbers

Post by RookiE3 »

The code complies on my machine (both in VS13 and CodeBlocks13 with their respective default compilers) and gives correct output for all the inputs I found on this website. But the judge says Runtime error. Please help. I can't find the spot where it might go wrong and give runtime error
N.B. i used some features of C++11

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 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)
    {
        strcpy(nnew, "0");
        return nnew;
    }
	if (i != index)
	{
		while (i != len)
			nnew[index++] = n[i++];
	}
	nnew[index] = 0;
	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(stoi(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(stoi(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] = 0;
	(*this) = num;
}

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

BigInteger BigInteger::operator=(INT64 n)
{
	digit.clear();
	if (setSignum(n) == 0)
    {
        char ret[] = "0";
        return ret;
    }

	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)
    {
        char ret[] = "0";
        return ret;
    }
	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);
	int size = chosenFibs.size();
	for (int i = 0; i < size; i++)
		fibinary[length - chosenFibs[i]] = '1';
	fibinary[length] = 0;
	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;
	bool firsttime = true;
	while (cin >> n1 >> n2)
	{
	    if(!firsttime)
            printf("\n");
		if (n1 == "0" && n2 == "0")
		{
			printf("0\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;
		sum = "0";
		firsttime = false;
	}
	return 0;
}
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 763 - Fibinary Numbers

Post by brianfry713 »

Try input:

Code: Select all

100101000010100010101001010100
1010100101010001010101010001010000010101001001010010001010100100100100010010000001001010101010000001

101010010010010100100000100101001001001010
1010101010100100001010101010010100010010101001010100100001010010100100010

1010101001010101010100100100000000100101010010101010000001010100
10010010101000100010101000101010100101001010001001010010010001001010100010000101010001010

10101010000
1000100101000010010001010100010010001010101001010000010101010001010101000000100101010

1000100000010101000000101010010100101010010010100101010
10101010000100

10101
1010010001001000001001001000010101000000101000010100101010101000001001010010000000100000

100010010000100010010010000100101
10100101010100101010000010100101001010101010100000000101010101010010101010100010101010000

1001000000010010010101010
1000101001000101001010010101010101001000010101000101010001001010100000001

10100101010101010001010100001001010101000100010010100100100101
10010010010100010010101010100101010000010010100000010100001001

1010000100100101000101001000101001
10100010100100101

10101000101000101010000001010
101001010001010000010100101001010101001010001010101001001010100010010010001010

100001010101010100100101000101010100001001010100101010101000101000010101001010100010010101010
101001000010100000010010010101010101010000101001000000000100010

10101010100
1001010010100100101000000010000010100001000000100101000100010000001

1010101000000100010100101010000100010001000010101010101010010001001001010101010100101010101001000101
100100101010101010

1010100001010000101010100010010001010000000101
10001001000100010101010100

10100100001000100100101000100001000010101010101001
10010010000010100010001010010100101010100000100010100101001

101010101001001010100101010001000100001010001001000101010101010001000000010100101001000100
10101010100001010010010001000101

10100010100100000010100000100101010101001001010100100101
101010101010101010101010100101000010001010101010010010101010010010010101000101010101001

10000101010100
101001000000001010010100100101010101001001010100100000010100101010101010010

1001010000010010010
10100100001010000010010101010000000000

1001010010000010101010010100001010001000100010010010
1001010000101010100010010101010100010100

1000100100010100101000010010100001010
1010100000001000101010

1010010100010010001001001000100000010001010101010101001010101001010101001000100010000101000000101
100100100010010000

10100101010100100100101001010100100001001010100101
100100010100010100000101001000101010100000001001

100000100101000001001000101000100100010101001010101000101010
1010100101010100000101000101010100100

1001010010100100101010100010100100010010010000001001010100
1001010100010101

10100010100100101000001000010
10010101000101010000000101010100000001000010100001000001000000010101010010100010000001000

101010010101
1010101010100100101000100010001001010100000101000010101010001010101001

1000000010101010010010000010100010001001010101010101010101001010101001001010
1010100101010010001010100001010001010101000001001001010000001

101001010101000100000100010101010
10100101010101010010010010001001010001010010101000100100100010100010101

1010101000000001010
10001000001000010101

100000101001000000101010101
101010100100010101000000010001000100100100101010100101010101

100101001001010101010010101010010010101000010101000010100100001010100000101001001001000101
10100101010101001010101010010101010000100101001010101000100001010001010100010101001010010000010010

100010001010100001010010010010100100010001001010101010101
10101001010000101010000010001010001010100100001010101001010010101001010101010

10100010000100100001010100100001010100010101000001010010101010101001
101001010101010000001010101001010100100101010001010101000010101010101001010100010

1000101000001010100000001010
10100101010001000000100101001001001010101010101001000010100100010010

1010101
1010010100001000101000101000001010010101010100000010100010001010100100101001

1010010001010101010101010000000010101010010010100010010100010100001001000100001010101010101000100100
1010000000010010100101001010100001010001001010001000100100101010100000101000

1001010101001010101010010001010010010000010100101010101000000101010100101000001001010101
1001001001001001000101000001010001001001010101010100100000001

10100101010
10100101001010010010010010101010010100010010101000101010100100101010100101000010100100010

1000100010101000100001010100000010010101
1000100000000100000100001001000101001001010010010101010

1010100100
1001000100000001010101000

100010101001000100000100000010001010100100010000100000000000100001001010100100000010001
10010010001000001000010101001000100101010101001000010000010000100001010000010010001

100000010010101000100100010
1010100101010010000000010101010000000010000101010101010101001010010100100100010001010010001010010010

101001010100100100100101001000010100101010010010100010100101010101010101010010001001000
100010100001010001010000100100100101000100100101000001010100100100010010

100100001000100101010010
101010100101010100101010100

1010101010101001000101001000010100
1

10101000010
1000101

101001010010101001000
10

1010010001010010001000100000101000010000010100000010101010
10100010100010010010010001001001010001010100000101000000000010010000010100010010010000

10101000100010000001001000010010000100010001010010001001000100101010101000010100100001000010101
1010100010010101001010010100000100101001000101001001010100100100100101010

10101010101000000001010000
1010101001010001001010100000100000001010010100100100001010101010

10001000100101001000010001001010101000101010001000000100101001010101001010100
101010010101000100010001000001001001000100010010000

101000000100101001010001010010000001001010101010010010100010101
1000000001001010010

100101010010001010101010101010101010100101000101010101010001010001001
1000010101001001010010100010000100001000101010101001001000010101010010101

10101001010010000101010100100010100100010100001
1000010100000010000010101000100010101

101010101010010010101010101010101010010010100010000100101010001010101000001010101010100
100100101001010010101001010010010100101001010100010101001001001010000100100001

10010101010000010101
100100101010010100010000010100100000010010001001010000010101010101010101010000100010010000010010100

10101001001001001001010010000010100101000010100010100010100010101010010010001010010010100100
10001010010101010

10000100001000010010100010100101
1001001001001000010100100001010000010100101010010001000100000

10100101001001010101000001010101010000001000100100000010010101
10101010101000010001010010100000100010100100101010000101001000001010100

1010100100100
100000101010

10010010010100
100100100100101001000000010100000001001010

1010101010010000001
10010100001000100010100100001001010100000010010101010101010100010000101010101

1010001000100001010100100001000000101
1001000010

10101000010101000101010101001001000010000001010100101010100001001001010000010
10010001001010100001001000100101000101001010000010010000100000001000010

1010100000101001010001010001000000001000101000001000000010100100101001010010100
1000101000100001010101010100010101000101010100010100101010101010010101000001000100101000100101

1001010000101010100100101001010101001010101010010100010101010
10101001000010101010000001010010000100

10101010001010000100100100100101000001001
10010010100101010100101010100100000101010010101000100

10010100001010000
10100101010100010100000010100101010010000101000010010101010100000000101001001010010101010000001010

1000101001010101001001010001010000101001010100100010010101000010010
10010

1000100
101001010101001000101010000010001010010001001000000101010010100001010101010010101

1010101010000000000010010001010000
1000101010010010010101

1001000100010100001001010101
10001001010000101001000000010100101001001010101010000101001001000101001010

1010010100010101010000000001001010100100101010010000001010000000010001000010001
1010001000000010001001001010101000100010010010001000100100000100000101010101010001010001010

10001000101001000000000010101001010101
100010100001001000000100010001010101010

1001
10010000100000100010100010000101010001010100101010010101010101010010101001000000101010100

101010000100001010100101000100010
1001001000000101010000001001000

10001010101001010100010000001010010
10010

100101010101010000100001000100101001
100

10
1001010100001000000100101000101010100010101010010101000101010010101010100100100

100100101010000001010101001001010100010100001001010101000010001001000100
10101001010100101001010100001010100010010001

101001001010101001000010101010101000000010100101000101000001010101010100001
1000000001000010000101000100100100000010100101

10
10010100001000100101000101010

1010101010100000010000100010101000101010100100100100100101001010001001010010010001010010
10000100101010100000000101010

1010101010101001010101010100010101001001010010100000100100100101010101010001010
1000010010000010100100000100101000010100000001001000101000010100101001001000001010010101010100100

1000100010100101010
1001010010100000101010100100100010101010100100101001

10101000100000101010101
10010010010101010001010000100010

100101000101010010010101010001010101000101000100100100010010101010010010101010100001010100010010
10101

10101001001010
1010010010101010

10
101010100101000001010101010100101

1010000101010001000010010001000100100101000001000010
1010000000000010101010010100001000100010000100000000100100001001001010

100100101010010100101010101010100001000100000101010100100000101010000100101000101001000100101010001
1010

1001010100100010000001010001010101000001010100101010010010100010001001001010
100100

10100001010001000
1000100001010101001000001000000101001001010010100001001001000010001010000

100101000101000010001010001
101001000101001010010010100100010001010100010100100000001001010010101001010010010010010000100101

10010100010101000010000101010010000001010100010
1010000001000

10101000010100101
1010000101010010101010010100101001010101010100010101010101001010100100000001001010000010101

101010100000010100000000000010100101000000101010101010100000000010100101001001
1010101010101000010010100101000000101010001010000100100100000001010000000010100000101

100100001010010100101010010010100100101001010010010100
101001001000100101001010100

101001000010101010001001001001000001010000010010101010010010
1010101010010101010010100100001000001010100101000010010000101010101000010000000101010010101010101010

10101010101010100010000010010100010000100001010000100100100000101010010010000001010010100010
10010001010000010101010010001010000100101

10100
10101010101010101010000101001010100010001010100100000001010101000100001001001001010010010100101001

1001010100010010100100101010010010101010100100001010010001001001010010
1010000100100010100010001001000101010010010010101010101000

101000000010101010010101000100101000010010100100101000000101
100100100000010100101001001000101010101010101001000000

1010010101000010001010010010101010000101010100101010010000
1001010010010100100

100101000001000010101010101010101000101000001010101001010010
1010

10100100
1001001001000010

1000101010100100
10010101010010010000010101010101010010

1000010010100100101010100100101010101001001001000000010100
10101000001010100010101001000010001000101010010101000101001001010000100100101010100010010000101

1001
1010100101010101010000010101001010100100010101001010100010101000101010

10101001010000
100101000100100100101000100100

100101010100010101001000010100010100000101010010100001010100001010101010100010010010010101000
100101000001000101010010001001000010010010101001001000100100001001

10010010001001010101001000010100100
10100101001000101000001001000100101001001000001001000010100010000010100100100010100

1010010010101000010100100000010010000001010100
10101010101001010000010010101010010001000000100100001010000100010000101000000010100101010100101001

100100100010010101001010100010101010000100101000100000001001001000101001001001010010000100101
10101001010101010001001000001001000000000

1010100010101010001010101001010101001000000010010010010101001001010100100001
1001010010101001000000010100000100010100101001010100010101010010101010101010101010100010010000001010

101
10100001010100101010001010101010101001010010001001

10100101010001010100101010010010010101010010100010100010101000101010100100101
1001010100100001000000010010001010100100010001010100

1001000000100101001010010010001010001001000101000101010010000100100000010010
10101010100101010000010100010010010010101010100000101010010001000100100010101001001001000

1000100101010100
1010101010000000101001010101010101001010101000001010100101010101010101010100

10010101010101000100101001000010101000101010000001000010100101010100001010000101001001001001010
100100001000101010100101010101010001010100000101010101010

10101001001010101000001010
1000010100101010000100101010100101010000101000000100100001010

1001000101010000
1010001010101001000000010000100000101010101010101010100100010100100010

101000010001001010100001010000100
10000100010001010001000010101010100101001010100101001000101

101001010101010101000001001000010100000101001001001000010101000101000101010010010010000101010
1000000001010010010101010001000001000010101010101010010001010000001010010001000101010100001000

10010100000100010101010010000010101001000100000010001001001001000000000101001000101000100000
10000010010001000100100

1010101010101010100101010101010101010100010001010101000010101000
10101010000100100100101000001010001000010000010101010010000

1010001010010100010010101
1010101010100010100010010100101010

1000000100101
100001010010101000101000000010001000100001000100100001010010101001000100000100

101000101
100010100100010010001010001000100101000000101000010010100000001000101001000101001010010101010101010

1010001000001000101000100100
10100100100000101010101000100010010010100000100101010

10001000
1010100101000001001010010001001010100100010001000001010010101

100000100000001001001000101001010100010000100101000001000100100000010100100101001010
10100000010010001010001000100001010

100
1001001010010100000

1001001010100010100101010010
1010010101001000000010101000101010100010001001010101000010010100101001000101010000001

10001001001001001010100100101010010010001001010010000001010
1001010100100100100010101010100000000000010100101010010000100

1010100100101000100010100101001001001001
100010010010101000100001000010101010010001000101000101001000100101010100101000100101010000001

1001010100010010101000010001001010001000
1000100001010010000010

1000100010101001010101001010001
10000101010101010100101010010010010010010101000100

100010100001010101010010
10101001000101010001000101000101001010101010100100101010100010101000101001010010101001000010

10101001001010100100100010100010100001010101010101001000010010000101001010010101
1010100001010101001001000000000101010100100

10010010100010010001001010010100010101
10001010100100100101000100001

1010010101010100000010101000001010100
1000

1000010100001010101000001010010100100100101001001010100010010101000100001000010010
1000101000101010010100100101010

10010001000101010101010100010010101000100010101000100001000001010100000000
10

10010100100100101001000000000000001000101001010101000010101010010100010
100100001001010100101010010001001001000101001

1001001000001010101001000001010001001010100100101010001000000101000010000101000101010000010010100100
101001001010101001000101010100010001000101

1000101010100010101000000101010101
10010010100

1010010101001010010010001001000010100101010001001000010000100101001010100010010101
100000010100101001010101001010101001

1001000010101001000010100101000010101010000101
101010001010101010101001001010

10010101010100010000
10001000010101010001010100001000010100100010100101010101001001001001001

10101001010000010101000100101010010000010010
1010101010100000100100101001010100101010101010010010101000000

100000100000100101010000101000
1001010010100100010010001010001010100101001001010010101010000010

10101010000100000100100001010
10100100010001010010100101000101001000101001000

101000100010010101000101010101000100101010
10000001000010010100000010010101001010000100010001010100100010100100100101010001001

1000010001010101001000010100101010101000101001001000010100
1001010010001010101001010100100100010

10101010100010001000000101000010101010101001010100100000001010
10

101010100000001000010100010010001001010000
1010

1000000010101010101000100
10101010000100010000000010000101

100010100100101001010001001000100101010001001010100100101010101001000101
10001000010101010100

101010010100000101001000
101000101010101001000010101000010000001010101010100

1000101010010010101001000101001010001010100100010001010101010010000010101000101010101010
10010101010101010000101010100101000010000

1001010100
100100001010101000101010100101001010001010010010100100010100100101000001001010

10000010100001010010000100101000100010000100101001000010010000001010100010100
1010101000001010100010010100101000101010000101001001000101010000100101010010101001

101001010000010100010101000100100100101000001010100010001
1000100001000010100000000000101001000001000000

1010101010010001000100101000000101
101000101000010101001000101000010101010100010101010010101001010000010100101000100100001000101

1001010001010000001000010000101001001010000010101010100010
100001001001010010001010000010000101010100100000101000101010000010100000100101000010010

101010001000001000100010001010101000100001010001000000001010
1010

10100010101000100010
10001000000010010100001010101010000001000100101

1010000010101000100100100101010
1010101010000010100010100001010000010010101000000101001010000101000100010100101000101010000000

101001
1001001

1001000101010100010010101010101010101010010000100100101001001010010
1010101000010000101001010010010000100100100000101010001010010010000101010000001010

101000
101001001010000000001000000000010101010010

101
101010000101001010010010100101001000010010101000101001000010010010101000101000

100001000100010101010010101000010101001001000100000100000001001001010100101010010101010
10101001010010000101001000000101000101000010100000101001010101000101000010010000101

101010001000001
10101010010101010010101010010100100100101010101010101010100010010000010101010010000101000

1010100
1001000001001010000010101010010000101010000010101010101010001010010100010100101000101010010101010100

10
101000100100100010010

10000001001001010101001000000101010100
101010000010010100101000010100010000101010

10010000001001010101010001010000000000101010000000001000100100010010100
101010010100101010101010101010101

10101001000010010010101001010101000010101000101000010000001010100010100001
10000101001001000

101010101010
101010001001000010

10010001010001010101000101010010010100000100000010000010101000101000010
101010010100101010101010010100010010001001000101010100010100001010010100000010101001010001010100001

1000100100101010010001
100000101001001001001001010001010000010100101001010010101000010101010010010100010

1001010101010100100100001001010100010010101010010010101001001000000000001010010010101000001001010010
1000010

10010101010101010101001000010010100101010100100101010010010010100001
10100101010100

101001001001010100010000001000100100000100010100100010101000010001000101010010010101010010101000000
100101001000000010101010

1000101010100101001010101010100010010100101000100101000101010010010101010000101000101010100101000
10010100001010100010101010010101001001010100000000101000001010

10100101001001000000101001000100101010101010100101010
10100100100101010101001010010010101000010001010101000100100000

10101000100101010000100101
10100000010

1010010
10001010010001010010100001010001000010000010

1000101000010101010101010101001
1010001001010101010010100010101010000101010010000010001010100000001010

1000101
1000101010100

10100010100001000100010010001010010100010101010101001001010010001001010101010101001
10001001010010010100100101010010000101010010101000100010010101010001010010

1010100101000
10010101001010100100000100010100100001001

101010101000000101001000100101000100101010101010010
1010010010100101001000101000100001010100001000010010101010000010000100000

100101001010010100101010000100101000100101001010100001000100100100100000001
10100101

1000010100101001
10100010100101010101010101000101000100010101000100000010101000010101010010101010101001001001

101000100010101000100100100101000010001000101000100101001001010000001001000000010100100101010010010
1010

100100010000001010010100000100100101010000101000100101010001010101
10010100100

1001001000101010010000101
10101000010100

1000100101010100010101001000100010101001001001010010010
1010010001010100101000010010010001010000101000101010

10101010010100010000001010010101010101001001001000101010100010010101001010101010000101010
1

101010010100001010101010101000100100100010010001010100100100001001010100010101010
10100101010100010010100010000000101

1010100000101000001000100100101010100101001001001001000101010101
10100101010001010010000100010100010100100100001010100100010010101010101001010100001010000000010101

100
10000010101010000010100100100101001010010100101

101010010101010010100100101000100100000010100000000101010010101010001000101000100010000100101
101000010

1010000100101000000100101001010101001
10101001000010010000100101001000010101010010101010100100101010000000101010010100010010101010001

10101000
1010100101000101010101000001001001010010010101010100100001010000101000100010001

1010001010100100000100100100001000100100010101001001010101000000100010100100100000100100000100100010
100100001

10100000001
1010010010100100101010100101010010101000100000101010010000100010101

1001001000101010101001010000101001010
10100101010000101000100100100101001000101010000

10001010100010101010101010101001010010001010100100000
1010100101010010100001010100010

10010100001000100101001001001001010000010000010100101000000010100010010000101001010100101
100001000001000

101010100100101000010010001000100101001010001010100000100100001010000
101000100100101010101000000001000010010001000100001000010

101001001010010100010010101010100010100010100101010010101010001000100101010100001000
101000001001001001001001010010101000010010010100010001000

1001001010101010010010100101010001010
1001000101000100100010101000100100010100100100101010000100010100101010001001010010

101010100101000010001001001000010100100101010100001000010010101010001010001000010101010000101010
1001010100100100101001001010101001010101001010100001010100010100010100100000

100010101001000000010101010100010101010
10010101010101010100010100

10000010100010000101010001001001000000010101010101001010010000001000101000100010000001001001
101001010001010001000010010101010101010010

1001001000001000010000000101000010010001000001000100100010100001000010010101010101010010100000001
1001010100101010001010001001001000101001000100101001010

1010010001010010010101010100100101010101001010010010101010010010000010000100101010001010000000
101010101001001010010001001010100101000010010100101010100010

10000100010100101010100000010010
10101010001010100100000

10010010010001000010101000010001010010100010001010100001000101001001010000001000101001000
100000010100101010100100101001001010010010010100

101001000010101000000010101010100010100
10101000101000101001001010010000100100101001000100101001010010010010101010010100100001001

101010001010010010001010010101001001
10101001000001000101010101000100000101010100000101001000100101000101000100101001010101010010

10010001010010100000101010101010100000010101000000001000101001010001001001010101
1010100000001001010010010000101010010010010010010101010101010000100000100010101000010100010010010010

101000001
10010010100101001010000101010100100000100101010010100101010

10000101000101010001010010101000001001000101001010010100101010100010101000101
1010100010000100001001000010010100100101000010101010100100000001010100100

1010101010010101001010101000010001
1000100100000100001000000010101001010101000000100101000000001000000001010010010001001001010101001

100101001010101001010010000010010010000100101010010101000101010100010100101000010010
1010101010100010010100

1001001010001001001010001010001010100100101010010100010100010100
101010100010100100101000100000101010010001001010001000101001000010100010010100000

1010001010010101
1000001010010010101000000000

10100001000010100100001010101001001010010101010101010101010001001010101010101000101010000100100
100100100010

1000010101000100010100010000010000100101000100101000100100010101010001000000001
10100100101010101010000000100101001001010010100101010100101000010001000

10010001001010100101010100001010001000000010001000101000000101010010000100100
10100100000000010101001010000001001010

101001000100000000101000000100010010000101010000000000001010101001010001001001010010100101
10101001010010101

10100101000100010001010000010101000101010010101010010101010100010100100
100100001010

100100101010001001001010101010101010010000010100000100100000100010010010
101001000100001010001001001000100100000100101000000000000001001010101010100

101000100100101000100010100101001000100
100100001010001010100010010001010000000010001000000100000100010100101010001000

1001001010010100101010100101010100000100101000100001001000000101010010001000
1000100100

10100101000010100101010000001001010001001
1010001

1010000010101000000000101010010000100101000100101001001000100010101000010101010
101010

1010010100100101000000101010100010000101000101010010101010001000100010010010100000010000101010101000
1010010100010100100000100010101010101001010100100000010100100000101000100100010010101001010010100

10100001000101010010
100010000010101000001000101001010100010101010010100000000100000010

100001001000101010101010000000010
101010010100100101000101001010000100010

100000101010010101000101010101010101000101000100010001001
10101000000010010010010100100010100100010000001000001001010101000101000010101010100

1000010000101001000
10100010010001001010010001000101000010

1001010100010010100101010010000001010000000010101000100101010010101010100101000101010100101000100100
101010100100001010100

10101001000010010100100001010100010100100010100100010100101
1010101000100100100101000010000001000100100101000

1001010000001010010100010000000100101000100010100010000101000100001
10010101001001010101001

1010100101001000101010010101000010100010100000010101010010010
1001001010000000

101001010101010010101010100100010100001010001000101001001000001001001000100100101000
100010010010101000100

100100100
10100001010100101000010010100000010001010101010001010000100101001010100000000000010101001001001010

10101010000010100100010001000100101000101010010010
101010010101010100101010101000101001000101000101000100010101000100100101001010100

10010100010000100101000000101000101010100010
1010

1001010000010101000101001010100000101010000101001001010101000010000101001000100000000010
1000000101001001010010101010

100010001000001
1001000100101000101010100010001001

100100101000001000100100010101010001010000010000010100100101
10100101001001010101010101010101010010101

1010000010101001001010100001001001001001000101010010
10000010

101010010001010010000100100010101001000000
1010101000010000010010010101001001000

10001010101000010010010100100000
101010001010000100100100001010001010101

101001000101001010100100101010101001010101
10100100001001010001000010010101001001

101000001010101010100100010101010101001000
10010000100000101010000010100001010100100010010

10010010100100100101000010100101000000010
10000010010010100010000001010010001001

100010
100100101

10100001000100010101010010001010101010010101010010010101
100101010101000001010010010010010010010101000101001001010101010101010010

10101000100101010101001010100010100001010001010100100101000010
1010101

1
1001000

1010000
100010101001001000

1010010101000100000001001010101010001010101001010100100101001000101001
1001001001010101000010001010000010010010101010001001010000100010010100010101010100

100001010000100100010001001000100001010100001001000100000101010010100000010001000000
1010000010001010100000100010001000000101

1000100010101000010100101010101001010100100
10010100100101001001010010010100001010101000100010010100010010101010100000100000010101000000100

100001000101010010100010001010000100010010100101010101010100101000000101010001010010101000010
1010101000100001000100101010010101000001010010000100010100101010101010000

10010100010000100100010100
10101000010000000101000100101001010001001001

1010010010001010010101001001010101010100101010010101001010101001010100101000101001010000100001
1010010101000010010000100101001

10101001000101010100100010100100010010100100101001001010001010100
10101010100000001010100101010001010100010010010101010010010100100100100001010000101010

10010001010001010000101000101000100101000010101010
101

10
1001010000010100101010101010010100101000001001010000100101000001010001

10100010010100101000101001010101001010010001000010100000100101
10101000101010000100010000010010001010101010000101010100

100010001010101010101001001010000101001010100000101000100100100001001
10101010101000010010100010101001000010001001010010101000010100010001001010101001001000

1010010100001000
1010100000000101010101010100101001010100010010100101000100010

1
10010010101001

1010100100010100010000001010001010010000100100010010100010000100010010010100010100101000
1

100101010101010001001000001010100100100010100101010101000010100100000010101000101
100101010010010010001000001010001001001010100

1010101000100100001
1001010000100010101010000100001000001010100000101001010000101010010010001000

101000010100101001001001010010010100101010101000100100010101001000001001001010
1000101010010010100100010101001000000101010000000100100100100000010101010100101001001000101

1001000100101010101010101000010100001010100010010000100101
100100100100101010010101

10000100010100100101010100
1000100100100100100101010101000101010001010101001010010010000010000101010100101000000

10101010000010010101001000100001010100010001000010100101010000101001010
1000101010000010000101000010000000010101000100100010

10010100101010000101001
1001010000100010101010100010101010101010101010001010101000

1001010101000100101000101010000101010010010000100001010100100
10000010100100001000100010000000000010000000101000101010101010010101001000000000101

1010100010001
10100000001000100010010101010000010000000000000100010010101001001001010010100010

100000010100100101010100000100100010010001001000100
100100010101001000100000001001010101010010101010100100001010100101000

100010010010010001010100101000100000101010101010010100100001
10101000001010101001001010100100100100010100101010000010100001001010000100100100

1010000010100100010101010100101010010100101001000010001001000001
101000100100101000010100010000001001001010000000101001001010101000

100010
10010000100100010001010100101010000010010100100100010001010010010000100100101

101010001010001010000100100010101010101001001010000100001010010010101001000101010100001001001010
1010000101010100100100001010000101010100100001001000101010000010100100100

100101010001010101010010001001000000100100001000010
1001001001001000

101001
10101001000000101001010101010101001010001

10010101
10001000000010010101000101010101000100101010000100101001010100

101010001001010101000101000101
101010100000001001001010100100100101000100001010100

101010100101010100001010001000101
1010010001010010101000101010100101000010010101000001010010010100010010000100001000010010001000010000

10100000101001001010100010010101010001001001010000001010100101000010001001
10100001010100000001010100010101000010000100100010000100010010010010100101001010001001000010101

101001010001010010100001010000
1000010010101001010101000100101010001010000001000101001001010000101001010000101

1000100010010010010100100101010100010101010101010001001001000001010100100100100101000001001000100
1000

1010001001010001010010101000101001010101010101001010000100001001000101010100100101010010101000010
100001000010010100010010101000101000010010101010010

10101010100100001010000100000000100101000101010010001000100100000100000001001001010100
1000101001010100100101001001000100100001010100101000101000010010010

10010101010101010010000101001010101000100101000100101010010
10100100101000100

100101010100010101010
1001000001000100001000001001001000010101010100010010010100010001001010

10000010101010001010101001010101000100010010101000100100001010010001
10000101001000101010000101001000100101

10010010100101010001000010101000010010100101010010101001000
1

10010010100101000100000010010
10101010001010100

10100101010010010101001010010101010010010101000010000010101000010010010001000
1

1010100000100101010100001000100000010010100101000100010101001001010010010
1001000100101010001

10010100010010101010100100000
10101010010001010001001000101000101010010100010100100

10101001001010001000010000100101010010100001001000100001010010101010010100010010100000
1001010001010000101000010100010100010101010000100100010001000101001010

1010100001001000100010100001000101001001010001010100100101010101000101010001010010010
10100000001000001010

1001000010001010101010101000101010101010010100100101000101010010
100010101000010101000010000010000001010100

1010010010000010101010000000101001001010100101010010001
100101000010000100000

101000
10100101010100101010000100101010100100000010100100010101010101000100010100010

1001010
1010101000001000100100101001001001000010000000101000001

10100000101010101001010010100
1010001001010010101010100100001001001010100101010

10100010000101000010100010001001010001000001010010000010100101
10101000100100010000000001010101010101010000101010010000100000000100101010000100

100001001000100010001000101010010010100010100100010100101010001010000001010100101010010101010
101010000010101010101001010001001010000100010010010001

101010100010101000100010010100101010100100000
10

1000000101000100100010010001010100100100010100010001010101010001000000010100010101001010001001000101
10010100001000100100001001001000000100

1001010100010000010101001010010101010100101001000101010000010010010010001010100
10010000100101000000000001001010101000

1010001010001010000100101001010101010010100100010101001001010010
1010101000010010010101000001010010010100100100100101010101010010001010101000101010100100101

1001010101000010101010101010010101010100001010101001000000100010000101010101
100010100010101000101000100001001010010010101

1010100100010101000101010010100101010010000100100010010001010010100001000010100010101
10100010000010010101010001000010010001001001010101010000001001001000101010000010000000010101010

10101000010101000100100010000010010
10010000100000010101000101001000000101010100001010010001010010001000010010100000101000

10000100100010101001010101010001010010100100101010001001
1010100

100101010000100100010101010100001000000010101000010101010000101000010101010100010
10101001000000101010010100100101000010100010010010001010010100010000101010000

100000001010010000101001010101001000010100101010010100010
1010101010010101010000100101000010000100000001010100010101

101010101010010001010010100101001010010010101000010101
10101001000101010100001010010010010010000001001001010101010100100010001010101001000100101010

10010010010010010101001010010010010100001001001000
100100100101010010100001001001010010101000101001000100101000001000100010100100001010010001010

1010000100100100010001010
10100010101001010010001000000010010001000010

10001010101000000001001010101000101001000101000100001010010101
1010101000010100100001

1000100
10001010100101010000010000100010001001010000101000000101010010

100100010001010100010101010101010001000001010001001000001
10100010101000001010010

1001010100101001010001001010101010000001000001010001
10001000000100101010001001000000010101010100100100

1010010101010001001000000010100001010000010000010100101000101001010101010001001010101010010
1001001010101000100101000010100100101

1001001010101010010010
101010010101000100101001010000010000101001010010100001001010010101000

10100101000100100010101010001010001001010101001010100100101000010
1000101000101010000010101001001000001001010

1001001001010000100010000100010001001000010000010101001001010010010101000100010100001001010
1000010101001001001001010101010010101010100100000100

1001010100101010100100100100010100010010100101000100101010100010100010010001010010101
10000000010010010100100101000101010010000010001000

1000100010101000101010100101010100101001000010001001000101010010101010100100100101010001000101010100
1000010010

101010000101000101001010001001001001010101010010001010010101010100000101001000010010010010001000
10010101000100101000100010100

10101000100001000100100001010000100101001
10101010001000100100000000010100100

100101000101001000000001
1001000101001001000000101001000000000001001001010000100101010100101010100100000001010100100100101

1
100100100010101000100010010100001000101001001000

101000101010001010000010100
100010010100010101001000101010010100010001010100010010101000

1001010010100001010101010100101000000001010
1001010010000100010101000010101001010101010101010001

100101001010010101001001010100100100100001010010001010100000100101010100010010101000100001000
101010001001010101010000100101000100000010101010000000010101000100100100010101010101

100001010010001000101010100001010101010000100100000101000100101000101001010000101010100100
101000100100010000100

1001
10100101010010010100101010101001000101001010010000

1000010100001010
10001010101001010100000010001000000101001

10010100000101010100010100100010000010010
10010000101010010

101001010000010101010101010100100010101000010100010
100101010101010100001001

100010101000100001010010010010010101001000100101001001010101001001010101001000100100001000000001000
10101010101000010000010010100100001

100101010101001001000100000000101010010101001
1001010100000101010101001010101001010100100001001010000000010

10100100101000001001001010010
100

1010001000010100001010100101010100100
10000100010010101010101001010

101010001010100010
10001000010101010000100001010100010000100000001010100001010001010010

101010010101010101000100
100101010010100100010101010101000101010100100010001001001010001010010010101

100100100000101000100101001001010010000010101001000100010010001
1010001000010010000001000100001010101000001010000000010001

10010100100100001001010010101000100001001010001010001010100101000
100010101010010000010010010010000101010010001000101001000010001001010001000100100101010100

10100010010100001000101010101001010101010100010000101000
1000000100000101

1010101000001001010101000101010101010101000000100101010010100100100100100010
1010001001010010001001001001000101010100101001001010010001010001001010010001

1000
1001001001010000100010101001010010000100100101001

100010101000101001001010000101001001001010
10101000001010

1010101001010100010100000000001010101010101010001000100100100010100101001000100
10010101000100000010100100010101010100000000001010010101000100010100000010101

1001010001010010001001000100001000100101010010000
10100001010010100010001010001000

101010000001010101010100100100001010010001010010001000101000000010010100100001001010010000
10010001010101001010000100000001000001000100101001000010010100010100101001010101010101001010010

101010010100010010100000101000101010000101001000010010101
1001010010100101001010100101001001010101001000

1010100001001000010010101010010101010
101010101000101010101010100101000100010100010100000101000000101010010000100010010010100

10001001000101001010100010100100010010010101001000010101010100010101001
10101000100101010101001010101001001001000010101010101000

100101010001010001010101010100100000101000010000010101001001010000101010010101
101010001001000100010100100001010100001010000101010001001010100010101010000101010010100100010001

100101000010001000000010101010101000100100000010101010100
10010

1000000010010010100000000010010010100101001010001000001
1010101001010010010000010101010010010100010010000101010100100101010010100010101010

10010100101010010100000001001001010100010101010100100101010000101
10010001010010101000100010010000010101000101010010100

100010101000
100001001010010100000001000101000100010001000100100100001000001000100100010101010010010100101001000

100000001000001000100100000010101001000101
1010101010001001010010010101010000010101000100100101000

1000001
100101010010100101000010000101010001001010010100001001010100001000

1001010001010010000100101000101000101010101001
10010010000100000010100010010100001010100100101000100010101010101001000100010100101010

1001010001000001010001010
1010001000101010100000010100100100010100101010100010010100

1001010010100100001001010100010010010000010010100001001010101010100000101
10010000000010010010000010101

10101001010000100101001010001010010
1010101010

1001000010010101010100101010
10001001001001001000001010010000101010101000010000100000100010001010

1010001001010100010010010100
10100001000010010000100

1010101010010
10001010010101001010100100100101000000010101010010010

101010010000010010101010101010101
1010101000000010000010100101000010

1000010100100100000100100010101000101010101010101010101010
10100101000100101010101000000001010101000000101010100010010010010100

10100000010000001000010000010001000101001001010010001000001001000100010100101
10001001001000100000100100100010100100010010001010001000010100101010000100001010100

10000001000101001010100010010100100100001010001000001001001010101010010000100010100100100010
101010101001

10010010010101010101000
10101010010000101010010000100101001001001010010101000100010001010101

1010010000100010000100100010010100010010101010101010010101010010001010100010001010100101001
1000101010000101000001010101010010100

10100000100010101
1010000101001010001010010101010100101

100000100010100001010010001010010101010001000000000001000100000101010
10010010010000000010100101010010100101000010101000101000100010101010000101010101001

1000001010101010010100001001001
10010010010010101010101010010100010100010010101010100100001010100001010100

1
10100101010

101001000010
100010000101000101010100101010100001010100101000000100100000

10001010010010010010010010101010101000001000101001010001010
100100000001010101000100101010

1001000010010010010100101001000010101000101010100100100000101001001010100010001001000100100101001000
101001000001001000000001000001001010001000010100101001010010100101000010001001010101010001010100

100001010001000010010001010000100000101010
100100010100100101010010000101000000000

101010101001001010010101000100010001000100010000101001010101010010
100100000100010101010010101001010100100101010010100100100010100

1001010101000001000
1010

10000
10010101010010100000010101010101010001001010001001010100

100100010100101010010010001010101000000010100000101000001010
10100001000001000

1010000000001010101010100101010100000000101010100101001010100100100010000100101000000010101001010100
1001000100010

10001000010001001001001000010010010100010000100101000000001001001010001001
101001010010100010010100010001000100100010100001

101001010010101010101010
10001000101000100010001010101010001001010100010100100010101010010100010010000100010000

1000100000101000001010010001000101010001000
1000001001001010010100010100100000010000010001001001000010100010010010010100101010100010100100001010

10100100010100001010101010001010010010101001001
1000100101010010001010100010

10100100001000100100001
10100010100001010010101010100100010010000000101010101010010101000101010001000101010100101001010

10000101010100000100000010100001010000010010100000100000101001010101010001001010001001
10010001001010010010000010010100010101

10101001
100000100101010101001010101010100010100001001010100101001001010100000100101

1001010100100101000010000101000000000000101000100100001000010100100101000100000000100100101010101010
101010100010100000000100101001010001010100100100100101

100010010010100010101010100010101010100100010101000101010001010100100100100101
1001010010000101010010101010101

100001000101000100100101010010101010101000010101001
10001001010100010100100101010100000100001000010100101010001000001001000000001001

101
10010010101010

10101001010101001010010101000101000100100100101010001000010100
10101000010001001010101010100101010010101010001010010010101010101000101

10100000101000101010010101010100100000100010101000101010100010
101010000101010100101001010101010010001010100100100001000000101000000010101010001001010001010101000

100000010001000101001000100001010100001000101010101010001000010000001001001001010010101010000010100
10100010001000100100000100100100101000101010010001

10010010100100010101
1010000010100101010101001010101000101001000010101010010100100

101001001001001
101010101001000100101010010010010000010101010010001001000

1001001001001001000000100
10010001010001000100000101010000100010101001

1001010000100101000100100
10010001010000101010101010000001001000010010100101001001010001010100100010000100101001010

1000101010100010001010001010010010100010001
10101001001010001010

10100
101000001010100100

101000101010100001000010
100101010101001001010001010010101001000100010100010010100000101010010

1010101000
100100100101010010101000000100001

10100000010010010010010000010000010100101010100010100000100101010100010001010010101
100010100101010

10101000010101001010000010101000000101001010100101000100100010101
10010010010010001

1001001010000001010101010101001010010001001010
1010010000100010101000001010

1010001000010101000001010010
10010010001010000100101010100100101001010000010100010010101000001001010100101000001

10010000101000101010010100010010000101
1

10101000101000101010101001010000100101001010000010101010010001010001
1000000101010010100010010100010100001010101010001001010100100001000010101010000000101000001010

100100
10000010100100001001010010001000100101010100101001000

101001010000010101001010101010100100100010000001010000100010101
100101010010000000010001000010101010010101010100100100001

100101010001001001001001010000101010100101010010
101

101001010000100101001001010101000100100100000100101
1010100101000001

101000100000100101010010001000010010
100101010000001000101000010100101010010100101010101000000100000100101

10001001001010001010100010010100100001010101000100001000010010101001001001010
10010100001010010010000010010101001000101000000010100100000

10100101000101010100010010001010001001010101010101000101010
1010101000101010100101000100101010101000000101010010010010101000000100000001010100101000010101000001

101010010100001010010100000101001001010100101000100100100000101010001000100101010
100000100101010100100100

10101010001
1001000101000001

1001010100000101001001010101000001001000100100101010000100001001001001010
10101010010010

1010101000010100100101000101001001001010100100000100101001010100010100101
1010001010000100000001000101010001000001000000101010100010001001010101000000000010

10010
1001000010010100100001010101010010000001001001010101010001010

10100001010100101000100010101000101010100101
1000000001010100000101010101001010000101000001000101001000000101010001010000000100000

101010100001000101000001001000101001010101001001001000100101001001010010000100
10000100

101010000101000100100100100001010001010001010010101010101000000000100101001001010010001
100101010000010100101001010101000010101001000010100001010101010001010101010000

100010100101001010010100100100100001001001000100100000101001000010101010001010010
100010100101010010101

100010101001001010010101001001000010101000010101001010010000
101010100001000000

10101010010101000000010001010101001010001000101001000100100000000100010
101000101010101010000010100010010100100001000000010100001010010010101010100100101001010010001

100010100100101000101010010100010100101010100100100010100101000001010001010101010
1001001010010001000000010001010100100100100100010100010100100101010100100010101010100100000010010001

10010000101010100100001010100010001001001010000000100000101010101001001010
101010000

1001010100010000001000001010001010101001010
101010100100010001001001010010101001001010100100001010

100000100101010010010100100000010001000100010000000101010100010100010
1000000101001000100000100001000100100010100101010

10100001010010101010100101000100101010101000000101010100100100100100101010010100001010
10100010000101010101010010100010101010000001010000001000101000101001001000010101

101001001010010100010000100100101001000100
1000100000101000100000100101010010000000101001000101000000100101000001010000010001010101

10001010010101001010100010000001000000100100010000101000101010010101001000101001010
1010001001001010100010000

100101001000100101010001000001001001010100101001010001010010100000001001
1010

101001010001010100000001010100100101001
10100100101000000100101001010101010010101010010100100010010010100101010100100001010

10100100101010101010100001001010000100100010101000010100010010010100101001001010010000100100
10001010001010010101000010010101001000

10101000100001010010101010000000100100101010001010100101000101010
10100000010010101010101010010100

100001010010001010101010100100000001010101000010001010100101000010101001001001010010010
101000101001001000010001010000101010100

101010010101010101001000010101001010010100101010001
1

1000101010000010100001010010000
101010100101001010010000001000010000100101010101000001000010101001000101010101001010001

100010100001010010010010101010010010010100010001000100101000001
101000101010100001010101000100000100100010001

101010100001
10010000100100010000000010000100100001001010101010001010010010001000010000001001010101001001

10010010010101010100101
1010010100100

1000010010001
101010010101000101000101000000010001001000101000100000001

100101010010100100100000100000010101010101010100
1001001010101001010101010010100101001001001001010010001001001000010010100000101010100010

101010010001010000010000001000
101001001010000101010001010100010010001000101010001010000001

10000010010100101010100010010010000100001010101010101010010001010100010100000100100010000101010
100101000000100001010010001001010010100101010

10101001000100000100000100100100101010100100100101000100
101010000000101010000010100010100101000100101000000000101000100001010001

10000001010100101010
1001010001000000000001010010101010000101010001010100000010101010101001001010101000100001010010100101

101010000100100000100100010010100
10101000101010100010101010100101010001010101010

100010101001010100000100
1001000010100000100100010101010000100100100000101001000000010010101001001010100010

1000100101010010100101010010000010010000100001010100100101000000
1010000000001000101001010100010000100101010100010001000100101010001000100000101010100001

101000101000101
10000101001000101010000001001010101001000101010001001010001010100000000100

101000101010100010000101010101010010100100
1010001001010000100001010010001010100001001010100000010100000000

1010001001010010100101000100010000010001000101001001001000101000100001010101010101
1001010000000010010000100001010

100010101010100
10010100010001000100010100001010010100100100000010100101000100101001010010100010101010010000

10100000101001010010000100100010000100100101000
1000101010101001001010

10001010001000010100010100010001010100010
101000100100101010101

10000010100010000010000010100010101000001000101010100101010
1010100010010101001010100000100101001001001010100100010

1010101010010010101001010101010010010100001001010001001010101001001000001010100101010
10101000101

100100001010100010101000101010010010000100010101
1001010010

1010100100101000000001001010010101010001001001010100100010101
100100010100

101000010101010010000100010000010100010001000010000101000000000010101010100010100101010101010001010
1010101010100010000101010000101000010010001010101000000001010000010100100101010100

100010001010010100100010
10101010100010010010010010100010010010100100001010100001010101001000001010101010

10101000100010000100101010000010100101010000100101001000000001001000100010101010010010
1010010010000000100000010010101010100010101001001000000010

100001001
10101001001001001001001010100101

10001000101010000101010000010001010010010100010001001001000101001000100
10010101001001001010010101001000100100101010101000001010010000001010

10001000101000100101010101010100010001
1000001010010001001010010100010101000101010101010010100

10000100000010101010101000
1000010010010100001

10010100010100001010100101000100101000010001010010101001001010101000000100001
10010100010100101010010101010000100101001000101010010001

101001000001001000101001001010
1000010100000101000000010100010100010100010100101010001000101001010101000000101000000101001001

1001001001000001010010100010001000101010101010100000100010100100010010000001001010
1000100101000101001001000001001010001001001000010100000

1010101010100101001010000000100000001010001000010101010000010101000100000
1010100100100000100000100010100100010100100101010010000010010001000010101001000

10101010010010000101001000001010010101001010101010010100100010101010000100000101
101010010010101010100010000

1010100101001010101010001010101010101001001010010100100001010101000010
1010000100101010100101010100101010101010010001000101010101000101010010101001000001

101000000000101000000010000100000000100010001000100100010100010001001010100010001000001000101010
10010010000001000101001010010010001010000010100001

100100100101010010010100100000100010010100101010010000101010000
10100101001010001001

101
10010100101001010101010010101001001001000100100001001000010100100100001

10010100100010100000101010010101010010010001001010000010101010
1010100001010101000010100010010101001001001001000001000010101001010100101010100010100100000101001

10
100100

1010101001001001000010101010
10101001001010100101001010100010101000010000101010100010100101010

100101010001000101
1010010100100001000000101001010100010101010

10010101010100
100010101001000010100001010000101010000101010010000100000001010001010101010101010010100010000010

101
10101010

10001000001001001000001001010101010010010010001001
10101000101010001000010101000001001000100101010100010

100100010101010000100000100101000100100100101010100101010000000000001001010101
10101010010010010101000101000100000000001010101000010

1000101000000101000100000100010100000101010010001000100001000100101000101010010100100101010101010010
1010100101001001001010

100010010100101000010101010010010101001000010100101001010000101
1010010010000010101001010010001001001010010101001000000000010010101000010

1001010000010101010010001000100000100100001000010
10000101010000001001001010010100101001000100010001010100101

10001001010100101010000010010001010010010001000
100101

1001
1010010100100100101000010100010010100010100010

10001010010000010101010100010010100101000001010101010001010010101000010100100010
10000100010101010010100010100000100000101000010010010101001001000100100010

1010001010000101000101000101010000001
101001000010101001010000000000100101001010010101010010100

1001000100010101010101000101010101001
101001000000100101010101000001000101010010000001010010001010000100100000000

10101000001000000100100101010101
10010100101001010001000101010010100010101001001001010100000010100100

10010010100000101010100100001010101010100000
10010010010100101000001010101010001010000010001000101000001010010000100100010101010010101

1000100100010100000100101010
100010101001010100000010010100000010101010001010010000010010100100100001010100101010

10100
101010100
Check input and AC output for thousands of problems on uDebug!
Top
RookiE3
New poster
Posts: 16
Joined: Tue Feb 18, 2014 7:59 pm

Re: 763 - Fibinary Numbers

Post by RookiE3 »

Hi brianfry713, I get correct answers for all of them, I checked up with UVa toolkit. STILL I am getting WA. This is really freaking me out :(
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 763 - Fibinary Numbers

Post by brianfry713 »

See http://ideone.com/oaziNU
If you scroll to the bottom you can see stderr:
*** Error in `./prog': malloc(): memory corruption: 0x0876e9c8 ***
Check input and AC output for thousands of problems on uDebug!
Top
hoangha84
New poster
Posts: 2
Joined: Sat Aug 09, 2014 7:17 am

Re: 763 - Fibinary Numbers

Post by hoangha84 »

Hello,
I'm trying to solve this problem. I had try some given examples here and got same answer. I tried to put or remove "cout<<endl;" but nothing is changed. My submission is still WA. Please help! Thanks in advance!

Code: Select all

/*
763 - Fibinary Numbers

Sample Input

10010
1

10000
1000

10000
10000

Sample Output

10100

100000

100100

*/
#include<iostream>
using namespace std;

const int M = 200;

void Balance(string &a, string &b) {
    if(a.length()<b.length()) {
        while(a.length()<b.length()) {
            a = "0" + a;
        }
    }
    else {
        while(b.length()<a.length()) {
            b = "0" + b;
        }
    }
}

int main () {
    string a, b;
    while(cin>>a>>b) {
        cout<<endl;
        Balance(a,b);
        int c[M];
        for(int i =0 ;i<M; i++) {
            c[i]=0;
        }
        int len = a.length();
        for(int i=0; i<len; i++) {
            c[a.length()-i-1]= (a[i]-48+b[i]-48);
//            c[i]=(a[i]-48+b[i]-48);
        }

        int vt = len - 1;
        while(vt>=0) {
            while(c[vt]>=1 && vt-1>=0 &&c[vt-1]>=1) {
                c[vt]--;
                c[vt-1]--;
                c[vt+1]++;
                if(vt+1+1>len) {
                    len++;
                }
                vt+=2;
            }
            while(c[vt]>1) {
                if(vt==0) {
                    c[0] -=2;
                    c[1] +=1;
                    if(vt+1+1>len) {
                        len++;
                    }
                    vt+=2;
                } else if(vt==1) {
                    c[1]-=2;
                    c[0]+=1;
                    c[2]+=1;
                    if(vt+1+1>len) {
                        len++;
                    }
                    vt+=2;
                } else {
                    c[vt]--;
                    c[vt-1]++;
                    c[vt-2]++;
                    if(c[vt]>=1 && vt-1>=0 &&c[vt-1]>=1) {
                        vt++;
                    }
                }
            }

            vt--;
        }
        for(int i = len-1; i>=0; i--) {
            cout<<c[i];
        }        
        cout<<endl;
    }
    return 0;
}
Top
RookiE3
New poster
Posts: 16
Joined: Tue Feb 18, 2014 7:59 pm

Re: 763 - Fibinary Numbers

Post by RookiE3 »

Check your outputs for the inputs(1589 lines) given by brianfry713 in this thread. In fact I checked your program's output with that from UVa toolkit and they do not match.

My program however gives correct output for all of them, yet I get WA, how come????????????????????????????????????????
This problem is really really freaking me out. Pleeeeeeeeeeeeeeease brianfry713, or someone else, tell me where am I doing wrong.........

P.S.: I got accepted for a number of other problems using this BigInteger class of mine
P.P.S.: Uses C++11

Code: Select all

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

#define MODDER 1000000000
#define DIGITSIZE 9

class BigInteger
{
	vector<int> digit;
	short signum;
	int setSignumInt(long long &);
	BigInteger add(BigInteger &);
	BigInteger subtract(BigInteger &);
	BigInteger multiply(int &);
	BigInteger multiply(BigInteger &);
	char* trim(char *);
	BigInteger getLower(int) const;
	BigInteger getUpper(int) const;
	void checkLength();
	static char *ZERO;
	static char *ONE;
public:
	BigInteger()
	{
		signum = 0;
	}
	BigInteger(long long);
	BigInteger(char*);
	BigInteger(string &);
	BigInteger(const BigInteger &);
	BigInteger operator = (long long);
	BigInteger operator = (char *);
	BigInteger operator = (string &);
	BigInteger operator = (BigInteger);
	BigInteger operator + (BigInteger &);
	BigInteger operator - (BigInteger &);
	BigInteger operator * (int &);
	BigInteger operator * (BigInteger &);
	bool operator == (const BigInteger &) const;
	bool operator < (const BigInteger &) const;
	bool operator <= (const BigInteger &) const;
	int getSign() { return signum; }
	string toString();
};

char* BigInteger::ZERO = "0";
char* BigInteger::ONE = "1";

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

BigInteger BigInteger::add(BigInteger &b)
{
	BigInteger temp;
	int len1 = digit.size();
	int len2 = b.digit.size();
	int minLen = len1 < len2 ? len1 : len2;
	int i, 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);
	}
	return temp;
}

BigInteger BigInteger::subtract(BigInteger &b)
{
	BigInteger temp;
	temp.signum = 1;
	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();
	if (size == biggerSize)
		return temp;
	while (prevBorrow)
	{
		if (digit[i] == 0)
			temp.digit.push_back(MODDER - 1);
		else
		{
			temp.digit.push_back(digit[i] - 1);
			prevBorrow = 0;
		}
		i++;
	}
	while (i < biggerSize)
	{
		temp.digit.push_back(digit[i]);
		i++;
	}
	return temp;
}

BigInteger BigInteger::multiply(int &n)
{
	int size = digit.size();
	if (size == 0)
		return ZERO;
	if (digit.size() == 1)
		return (BigInteger)((long long)digit[0] * n);

	BigInteger temp;
	int overflow = 0;
	long long digitProduct;
	for (int i = 0; i < size; i++)
	{
		temp.digit.push_back((digitProduct = ((long long)digit[i] * n) + overflow) % MODDER);
		overflow = digitProduct / MODDER;
	}
	if (overflow)
		temp.digit.push_back(overflow);
	temp.signum = 1;
	return temp;
}

BigInteger BigInteger::multiply(BigInteger &b)
{
	int size1 = digit.size();
	int size2 = b.digit.size();
	int half = size1 > size2 ? (size1 + 1) / 2 : (size2 + 1) / 2;

	BigInteger al = (*this).getLower(half);
	BigInteger ah = (*this).getUpper(half);
	BigInteger bl = b.getLower(half);
	BigInteger bh = b.getUpper(half);

	BigInteger p1 = ah * bh;
	BigInteger p2 = al * bl;
	BigInteger aDigitSum = ah.add(al);
	BigInteger bDigitSum = bh.add(bl);
	BigInteger p3 = aDigitSum * bDigitSum;
	BigInteger p1plusp2 = p1.add(p2);
	p3 = p3 - p1plusp2;

	int i;
	size1 = p1.digit.size();
	size2 = p3.digit.size();
	for (i = 1; i <= half; i++)
	{
		p1.digit.push_back(0);
		p1.digit.push_back(0);
		p3.digit.push_back(0);
	}
	for (i = size1 - 1; i >= 0; i--)
	{
		p1.digit[i + half * 2] = p1.digit[i];
		p1.digit[i] = 0;
	}
	for (i = size2 - 1; i >= 0; i--)
	{
		p3.digit[i + half] = p3.digit[i];
		p3.digit[i] = 0;
	}
	return p1.add(p2).add(p3);
}

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 ZERO;
	if (i != index)
	{
		while (i != len)
			nnew[index++] = n[i++];
	}
	nnew[index] = 0;
	return nnew;
}

BigInteger BigInteger::getLower(int n) const
{
	int len = digit.size();
	if (len <= n)
		return *this;

	BigInteger lowerHalf;
	for (int i = 0; i < n; i++)
		lowerHalf.digit.push_back(digit[i]);
	lowerHalf.checkLength();
	return lowerHalf;
}

BigInteger BigInteger::getUpper(int half) const
{
	int len = digit.size();
	if (len <= half)
		return ZERO;
	BigInteger upperHalf;
	for (int i = half; i < len; i++)
		upperHalf.digit.push_back(digit[i]);
	upperHalf.checkLength();
	return upperHalf;
}

void BigInteger::checkLength()
{
	int size = digit.size();
	if (size)
	{
		while (digit[size - 1] == 0)
		{
			digit.pop_back();
			if ((size = digit.size()) == 0)
				break;
		}
		signum = size ? 1 : 0;
	}
}
// END OF PRIVATE FUNCTION-DEFINITIONS

// START OF PUBLIC FUNCTION-DEFINITIONS

BigInteger::BigInteger(long long n)
{
	int status = setSignumInt(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(stoi(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(stoi(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] = 0;
	(*this) = num;
}

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

BigInteger BigInteger::operator=(long long n)
{
	digit.clear();
	if (setSignumInt(n) == 0)
		return ZERO;
	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+(BigInteger &b)
{
	if (b.signum == 0)
		return *this;
	if (signum == 0)
		return b;
	BigInteger temp;
	if (signum == b.signum)
	{
		temp = (*this).add(b);
		temp.signum = signum == 1 ? 1 : -1;
	}
	else
		temp = (*this) - b;
	temp.checkLength();
	return temp;
}

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

BigInteger BigInteger::operator*(int &num)
{
	if (signum == 0 || num == 0)
		return ZERO;

	int n = num > 0 ? num : -num;
	BigInteger temp = (*this).multiply(n);

	if ((signum == 1 && num < 0) || (signum == -1 && num > 0))
		temp.signum = -1;
	else
		temp.signum = 1;
	return temp;
}

BigInteger BigInteger::operator*(BigInteger &b)
{
	if (signum == 0 || b.signum == 0)
		return ZERO;

	BigInteger product;
	if (digit.size() == 1)
		product = b.multiply(digit[0]);
	else if (b.digit.size() == 1)
		product = (*this).multiply(b.digit[0]);
	else
		product = (*this).multiply(b);
	product.signum = signum == b.signum ? 1 : -1;
	product.checkLength();
	return product;
}

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;
}

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;
}

BigInteger fib[110];

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.getSign() != 0)
	{
		while (b < fib[i])
			i--;
		b = b - fib[i];
		chosenFibs.push_back(i);
	}
	char *fibinary = new char[length + 1];
	memset(fibinary, '0', length);
	int size = chosenFibs.size();
	for (int i = 0; i < size; i++)
		fibinary[length - chosenFibs[i]] = '1';
	fibinary[length] = 0;

	return fibinary;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	fib[1] = 1;
	fib[2] = 2;
	for (int i = 3; i < 110; i++)
		fib[i] = fib[i - 1] + fib[i - 2];

	string n1, n2;
	BigInteger sum;
	int len, i;
	char zero[] = "0";
	bool firsttime = true;
	while (cin >> n1 >> n2)
	{
		if (!firsttime)
			printf("\n");
		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];
		}
		if (sum.getSign() == 0)
		{
			cout << "0\n";
			continue;
		}
		cout << toFibinary(sum) << endl;
		sum = zero;
		firsttime = false;
	}
	return 0;
}
Top
hoangha84
New poster
Posts: 2
Joined: Sat Aug 09, 2014 7:17 am

Re: 763 - Fibinary Numbers

Post by hoangha84 »

Thanks! There is something wrong with my algorithm, I will try to find out. Using BigInteger, this problem is easy.
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 763 - Fibinary Numbers

Post by brianfry713 »

Input:

Code: Select all

0
0

0
1
AC output:

Code: Select all

0

1
Check input and AC output for thousands of problems on uDebug!
Top
RookiE3
New poster
Posts: 16
Joined: Tue Feb 18, 2014 7:59 pm

Re: 763 - Fibinary Numbers

Post by RookiE3 »

Thanks brianfry713. It really was a silly mistake, forgetting re-initialization of sum... :wink:
Top
wahidxp
New poster
Posts: 1
Joined: Wed Oct 15, 2014 12:16 pm

Re: 763 - Fibinary Numbers

Post by wahidxp »

Hello,
I have solved this problem. My solution can solve all critical input and it works for maximum of 110 digit as output but getting WA!! can anyone help me?

here is my code:
thanks in advance.

Code: Select all

AC; deleted
I have missed the input 0 0
Top
Post Reply

Return to “Volume 7 (700-799)”