## 763 - Fibinary Numbers

Moderator: Board moderators

outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

### Re: 763 - Fibinary Numbers

Try this
Input:

Code: Select all

``````100000001010001010001010001000101000101000101000010000000101000101000101000100010100010100010100001
100000001010001010001010001000101000101000101000010000000101000101000101000100010100010100010100001``````
Output:

Code: Select all

``1001000100001001001001001000100100100100100100010100100010000100100100100100010010010010010010001010``
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

### Re: 763 - Fibinary Numbers

I'm getting RE
Can anybody help?

Code: Select all

``ac``
Last edited by Yusif on Sun Sep 01, 2013 12:01 am, edited 1 time in total.

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

### Re: 763 - Fibinary Numbers

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
Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

### Re: 763 - Fibinary Numbers

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

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

### Re: 763 - Fibinary Numbers

Try input:

Code: Select all

``````0
0
``````
Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

### Re: 763 - Fibinary Numbers

Got it; thank you!

darksk4
New poster
Posts: 13
Joined: Sun Jul 29, 2012 7:10 pm

### Re: 763 - Fibinary Numbers

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.
Last edited by darksk4 on Fri Nov 01, 2013 6:11 am, edited 1 time in total.

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

### Re: 763 - Fibinary Numbers

The output may have more than 100 digits, it is less than 106 digits.
Check input and AC output for thousands of problems on uDebug!

darksk4
New poster
Posts: 13
Joined: Sun Jul 29, 2012 7:10 pm

### Re: 763 - Fibinary Numbers

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

rafid059
New poster
Posts: 13
Joined: Thu Feb 27, 2014 6:35 pm

### Re: 763 - Fibinary Numbers

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

Code: Select all

``````Silly mistakes  :P  Thanks BrianFry  :)
``````
Last edited by rafid059 on Wed Jul 30, 2014 11:32 am, edited 3 times in total.

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

### Re: 763 - Fibinary Numbers

Don't use a package, use class Main. Post the code you'd actually submit.
Check input and AC output for thousands of problems on uDebug!

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

### Re: 763 - Fibinary Numbers

Input:

Code: Select all

``````1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
``````
AC output:

Code: Select all

``````100010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101001
``````
Check input and AC output for thousands of problems on uDebug!

rafid059
New poster
Posts: 13
Joined: Thu Feb 27, 2014 6:35 pm

### Re: 763 - Fibinary Numbers

I get the same output

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

### Re: 763 - Fibinary Numbers

The code you posted does not, see http://ideone.com/xZxG9d
Check input and AC output for thousands of problems on uDebug!

RookiE3
New poster
Posts: 16
Joined: Tue Feb 18, 2014 7:59 pm

### 763 - Fibinary Numbers

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