Page 2 of 3

### Re: 763 - Fibinary Numbers

Posted: Mon Jul 09, 2012 5:00 pm
Try this
Input:

Code: Select all

100000001010001010001010001000101000101000101000010000000101000101000101000100010100010100010100001
100000001010001010001010001000101000101000101000010000000101000101000101000100010100010100010100001
Output:

Code: Select all

1001000100001001001001001000100100100100100100010100100010000100100100100100010010010010010010001010

### Re: 763 - Fibinary Numbers

Posted: Thu Aug 29, 2013 3:36 am
I'm getting RE
Can anybody help?

Code: Select all

ac

### Re: 763 - Fibinary Numbers

Posted: Thu Aug 29, 2013 10:12 pm
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

### Re: 763 - Fibinary Numbers

Posted: Fri Aug 30, 2013 1:25 am
I changed that to 198 and then to 140 yet the same result!

### Re: 763 - Fibinary Numbers

Posted: Fri Aug 30, 2013 10:16 pm
Try input:

Code: Select all

0
0

### Re: 763 - Fibinary Numbers

Posted: Sun Sep 01, 2013 12:00 am
Got it; thank you!

### Re: 763 - Fibinary Numbers

Posted: Wed Oct 30, 2013 5:37 pm
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.

### Re: 763 - Fibinary Numbers

Posted: Thu Oct 31, 2013 10:07 pm
The output may have more than 100 digits, it is less than 106 digits.

### Re: 763 - Fibinary Numbers

Posted: Fri Nov 01, 2013 6:07 am
thanks haha I see @_@ I thought it's my algorithm thanks

### Re: 763 - Fibinary Numbers

Posted: Sat Jul 26, 2014 9:53 pm
Getting wrong answer Don't bother with the package name and the class name

Code: Select all

Silly mistakes  :P  Thanks BrianFry  :)

### Re: 763 - Fibinary Numbers

Posted: Mon Jul 28, 2014 7:56 pm
Don't use a package, use class Main. Post the code you'd actually submit.

### Re: 763 - Fibinary Numbers

Posted: Tue Jul 29, 2014 7:17 pm
Input:

Code: Select all

1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
AC output:

Code: Select all

100010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101001

### Re: 763 - Fibinary Numbers

Posted: Tue Jul 29, 2014 7:30 pm
I get the same output

### Re: 763 - Fibinary Numbers

Posted: Wed Jul 30, 2014 12:15 am
The code you posted does not, see http://ideone.com/xZxG9d

### 763 - Fibinary Numbers

Posted: Thu Jul 31, 2014 2:51 pm
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 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 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)
if (signum == 1 && b.signum == -1)
return (*this).subtract(b);
if (signum == -1 && b.signum == 1)
return b.subtract(*this);
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)
if (signum == -1 && b.signum == 1)
{
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;
}