763 - Fibinary Numbers

[cyfra]

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]

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]

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

[sohel]

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]

I get:

Code: Select all

1000010

100001001

10

1

1000101010

0

1001

1000101010101010100101

[miras]

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

[miras]

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]

[Sedefcho]

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]

I get:

Code: Select all

1

0

10

100

101

1001

1000

1000

1010

10000

10101001

10010010

10101010010101001

101000101000101010001000101000101000100101

10000000101000101000101000100010100010100010100001

[Sedefcho]

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]

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

[Zaspire]

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]

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]

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]

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