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

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

763 - Fibinary Numbers

Post by cyfra » Tue Sep 24, 2002 3:58 pm

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 :wink:

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Sep 25, 2002 7:57 am

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

Post by LeoST » Wed Jan 07, 2004 9:05 pm

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);
  readln(s);
  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);
  readln(s);
  readln;
  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[1] := res[1] - 2;
               inc(res[3]);
             end;
           2 :
             begin
               res[2] := res[2] - 2;
               inc(res[3]);
             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

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

don't get it

Post by sohel » Sun Jun 20, 2004 2:47 pm

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:

Post by Larry » Tue Aug 03, 2004 7:53 pm

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

Post by miras » Sat Jan 01, 2005 7:51 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>
:lol:
Remember Never Give Up
Regrads
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Sat Jan 01, 2005 7:52 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."
:lol:[/b]
Remember Never Give Up
Regrads
Miras

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sun May 29, 2005 11:47 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 30, 2005 1:13 am

I get:

Code: Select all

1

0

10

100

101

1001

1000

1000

1010

10000

10101001

10010010

10101010010101001

101000101000101010001000101000101000100101

10000000101000101000101000100010100010100010100001

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon May 30, 2005 9:31 am

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Feb 17, 2006 9:08 am

It is interesting that this problem can be solved using ordinary big ints.

User avatar
Zaspire
New poster
Posts: 36
Joined: Sun Apr 23, 2006 2:42 pm
Location: Russia

Post by Zaspire » Tue May 09, 2006 10:00 am

It is interesting that this problem can be solved using ordinary big ints.
Certainly.
1) Read numbers
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

Post by eniu9350 » Wed May 28, 2008 4:42 am

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] == '0' && n1[1] == '1')
				{
					n1[0] = '1';
					n1[1] = '0';
					n1[2] = '0';
				}
				else
					n1[2] = '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

Post by tkcn » Fri Jun 04, 2010 3:59 pm

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

Post by receme » Fri Dec 10, 2010 6:45 pm

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..... :(

Post Reply

Return to “Volume 7 (700-799)”