## 763 - Fibinary Numbers

Moderator: Board moderators

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### 763 - Fibinary Numbers

Hi!

I thought it is quite easy problem but i cannot get Accepted..

Does anyone know any tricky inputs for this task ??

Thanx in advance Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
No special case (from my side)

But you must remember about few rules in Fibonnacci number arithmetic ...
When I try to solve this problem I had problem with sumation of two numbers - it's not linear, but recursive !

Maybe it help Dominik

PS. Don't remember about 'normalization' such numbers after addition LeoST
New poster
Posts: 7
Joined: Thu Dec 25, 2003 5:10 pm
Location: Russia

### 763

Help me plz to understand why my program gets the WA

Code: Select all

``````[pascal]program n763;
var
a,b,res : array[1..1000] of integer;
i,j : integer;
s : string;
len : integer;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
while not eof do
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(res,sizeof(res),0);
for i := length(s) downto 1 do
begin
case s[i] of
'0' : a[length(s)+1-i] := 0;
'1' : a[length(s)+1-i] := 1;
end;
end;
len := length(s);
for j := length(s) downto 1 do
begin
case s[j] of
'0' : b[length(s)+1-j] := 0;
'1' : b[length(s)+1-j] := 1;
end;
end;
if length(s) > len then len := length(s);
for i := 1 to len do res[i] := a[i] + b[i] ;
i := 1;
while i <= len + 5 do
begin
if res[i] = 0 then
begin
inc(i);
continue;
end;
if (res[i] = 1)and(res[i+1] =1 ) then
begin
res[i] := 0;
res[i+1] := 0;
inc(res[i+2]);
inc(i);
continue;
end;
if res[i] > 1 then
begin
if i > 2 then
begin
dec(res[i]);
dec(res[i]);
inc(res[i-2]);
inc(res[i+1]);
i := i -2;
end;
if i < 2 then
case i of
1 :
begin
res := res - 2;
inc(res);
end;
2 :
begin
res := res - 2;
inc(res);
end;
end;
continue;
end;
inc(i);
end;
i := len + 10;
while res[i] = 0 do dec(i);
while i <> 0 do
begin
write(res[i]);
dec(i);
end;
writeln;
writeln;

end;

end.

[/pascal]``````
Thanks
Best reguards

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### don't get it

Can somebody verify the following input and output..
I am getting WA.

input
[c]
101010
11

1101010
101010

1
1

1
0

101010
1000000000

0
0

11
11

1111111111111111111
1111111111111111111
[/c]

my output:
[c]
1000010

100001000

10

1

1000101010

0

1001

1000101010101010100101
[/c]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I get:

Code: Select all

``````1000010

100001001

10

1

1000101010

0

1001

1000101010101010100101
``````

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
<b> Sohel<b> you made small mistake in last case becouse it is written
<b>"Write a program that takes two valid Fibinary numbers and prints the sum in Fibinary form."<b> Remember Never Give Up
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
Sohel you made small mistake in last case becouse it is written
"Write a program that takes two valid Fibinary numbers and prints the sum in Fibinary form." [/b]
Remember Never Give Up
Miras

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
I currently get TLE on that problem. I need to make sure my
algorithm is logically correct. So ...

Could someone verify this I/O ?

INPUT

Code: Select all

``````0
1

0
0

1
1

10
1

10
10

11
11

11
10

10
11

101
100

101
101

1010101
101010

1000101
101001

101010101010101
1010101000101010

101010101010101010101010
101000101000101000101000101000101000101000

1010101010101010101010101010001010001010001010001
101000101000101000101000101000101000101000``````

OUTPUT

Code: Select all

``````1

0

10

100

101

1001

1000

1000

1010

10000

10101001

10010010

10101010010101001

1010001010001010010001010001010001010010001

10000000101000101000101000100010100010100010100001``````

Thanks in advance to anyone who would help.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I get:

Code: Select all

``````1

0

10

100

101

1001

1000

1000

1010

10000

10101001

10010010

10101010010101001

101000101000101010001000101000101000100101

10000000101000101000101000100010100010100010100001``````

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Well, I guess this output is from an ACC program Our outputs differ for the 2nd last test case.

Seems apart from the TLE I have some logical bug too.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
It is interesting that this problem can be solved using ordinary big ints.

Zaspire
New poster
Posts: 36
Joined: Sun Apr 23, 2006 2:42 pm
Location: Russia
It is interesting that this problem can be solved using ordinary big ints.
Certainly.
2) summarized them
3) correct number (contains only 0,1)

Sorry For my bed Endlish[/i]

eniu9350
New poster
Posts: 1
Joined: Wed May 28, 2008 4:29 am

### Re: 763 - Fibinary Numbers

I test all the cases in this post, seems there's nothing wrong with my code , anyone has any idea?
(I print result immediately after each test case, is that right?)

Code: Select all

``````#include<stdio.h>
#include<string.h>

#define TRUE 1
#define FALSE 0
#define DIGITMAX 100

void fibsum(char n1[DIGITMAX], char n2[DIGITMAX]);
void fibinc(char n1[DIGITMAX + 2], int d);

int main()
{

char line[DIGITMAX + 1];
char a[DIGITMAX + 2];
char b[DIGITMAX + 2];

int len;
int i;

while(gets(line) != NULL)               // get a
{
memset(a, '0', DIGITMAX + 2);
memset(b, '0', DIGITMAX + 2);

len = strlen(line);
memcpy(a + (DIGITMAX + 2 - len), line, len);

// get b
gets(line);
len = strlen(line);
memcpy(b + (DIGITMAX + 2 - len), line, len);

// get blank line
gets(line);

// sum (result is still stored in variable a)
fibsum(a, b);

// output result
i = 0;
while(a[i] == '0')
i++;
if(i == DIGITMAX + 2)
i--;
while(i < DIGITMAX + 2)
{
putchar(a[i]);
i++;
}
putchar('\n');

// output blank line
putchar('\n');
}
return 0;
}

void fibsum(char n1[DIGITMAX + 2], char n2[DIGITMAX + 2])
{
int i;
int c = 0;
for(i = 2; i <DIGITMAX + 2; i++)
{
if(n2[i] == '1')
fibinc(n1, i);
}
}

void fibinc(char n1[DIGITMAX + 2], int d)
{
int c = 0;

if(n1[d] == '0')
{
if(d < 2)
n1[d] = '1';
else if(d == 2)
{
if(n1 == '0' && n1 == '1')
{
n1 = '1';
n1 = '0';
n1 = '0';
}
else
n1 = '1';
}
else
{
if(n1[d-1]	 == '1')
{
n1[d-1] = '0';
n1[d] = '0';
fibinc(n1, d-2);
}
else
n1[d] = '1';
}
}
else
{
n1[d] = '0';

fibinc(n1, d-1);

if(d < DIGITMAX + 2 - 2)
fibinc(n1, d+2);
else if(d == DIGITMAX + 2 - 2)
fibinc(n1, d+1);
else if(d == DIGITMAX + 2 - 1)
;
}

}``````

tkcn
New poster
Posts: 5
Joined: Wed Apr 02, 2008 3:42 pm

### Re: 763 - Fibinary Numbers

Hello.
I solved this problem just a moment ago.

I noticed that the problem said:
Write a program that takes two valid Fibinary numbers and prints the sum in Fibinary form. These numbers will have at most 100 digits.
I consider it means the sum of two values is at most 100 digits at first, but always got WA.
Actually, the sum of values is more than 100 digits.
I think it is easily lead to misunderstanding...

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

### Re: 763 - Fibinary Numbers

what is wrong?? I get correct output but still WA. Is there any difficulty in getting input?Here says there is a blank line between two input.
But if I get input with scanf("%s %s",a,b)...should I consider the blank line?
My output is correct for the given output in the other post. And also I do not print blank line after the last output.

Plzzz...help..... 