10334 - Ray Through Glasses

[medv]

I tried a lot of times to solve the problem 10334 (I think it's easy - Fibonacci numbers). But I got wrong answer. I wrote a long arithmetic.

Can somebody tell me why I get WA and what is the best way to write long arithmetic (I use Borland (Turbo) Pascal, the maximum type here is Longint).

(* @JUDGE_ID: 4406RA 10334 PASCAL "Fibbonacci long arithmetic" *)

program Ray_Through_Glasses_10334;
const LEN=50;
MX=220;
type lng = array[1..LEN] of word;
prnt = array[1..MX] of byte;
var t,n1,n2,n3:lng;
n,a,b,i:longint;

function getBlocks(a:lng):word;
var i:word;
begin
i:=LEN;
while (a[i]=0) do Dec(i);
getBlocks := i;
end;

procedure add1(var a:prnt);
var i:word;
tt,c,t:word;
begin
c := 1;
tt:=MX;
while((a[tt]=0) and (tt>0)) do dec(tt);
if (tt < MX) then Inc(tt);
for i:=1 to tt do
begin
t:=a[i] + c;
c := t div 10;
a[i] := t mod 10;
end;
end;

procedure mult2(var a:prnt);
var i:word;
tt,c,t:word;
begin
tt:=MX;
while((a[tt]=0) and (tt>0)) do dec(tt);
if (tt < MX) then inc(tt);
c := 0;
for i:=1 to tt do
begin
t:=2*a[i] + c;
c := t div 10;
a[i] := t mod 10;
end;
end;

procedure toZero(var res:lng);
var i:word;
begin
for i:=1 to LEN do res[i] := 0;
end;

procedure add(a,b:lng;var res:lng);
var t,c:longint;
tt,i:word;
begin
toZero(res);
tt:=LEN;
while ((a[tt] = 0) and (b[tt] = 0) and (tt>0)) do Dec(tt);
if (tt < LEN) then Inc(tt);
c := 0; t:=0;
for i:=1 to tt do
begin
t := c + a[i] + b[i];
res[i] := t;
c := t shr 16;
end;
end;

procedure print(a:lng);
var res:prnt;
tt,i,j:word;
begin
for i:=1 to MX do res[i] := 0;
tt:=LEN-1;
while (a[tt] = 0) do Dec(tt);
for i:=0 to tt-1 do
begin
for j:=0 to 15 do
begin
mult2(res);
if (a[tt-i] and (1 shl (15-j))) > 0 then add1(res);
end;
end;
i := MX;
while ((res[i] = 0) and (i>0)) do Dec(i);
while (i>0) do
begin
write(res[i]); Dec(i);
end;
writeln;
end;

procedure copy(var a,b:lng);
var
i:integer;
begin
for i:=1 to LEN do b[i] := a[i];
end;

begin
while (not EOF(input)) do
begin
readln(n);
toZero(n1);n1[1] := 1;
toZero(n2);n2[1] := 2;
while (n > 0) do
begin
copy(n2,t);
add(n1,n2,n2);
copy(t,n1);
Dec(n);
end;
print(n1);
end;
end.


I tried to solve it in C, but got WA also. I heard that UVA compiler has LONG LONG type, but how to output variables of this type?

/* @JUDGE_ID: 4406RA 10334 C++ */
#include <stdio.h>

int main()
{
int n;
long long a,b,t;
long long m[100];
a = 1; b = 1;
n = 0;
while( n < 100)
{
t = b; b = a + b; a = t;
m[n] = a; n++;
}

while(scanf("%d", &n)==1)
printf("%ld\n",m[n]);
return 0;
}
[/quote]

[Picard]

i think the 1000th element has 210 digits.
you can read/write long long with "%lld", but it only has 18 digits.

[soyoja]

Yes. Picard is correct.

fibonacci number is exponential increase.

You must prepare a data structure for control biginteger.

( Many of people use char array. )

[LawrenceT]

personally, i use pointers and long array... its much faster than using a char array, cos u can then process 9 digits at once (for addition), and 4 digits at once (for multiplication).

So what you can do is to create 3 arrays, one to store your current total, one to store the next number to add, and one as a temporary array to store the answer, and create 3 pointers to point to these 3 arrays.

Code: Select all

long total[1000], next[1000], temp[1000];
long * pTotal, pNext, pTemp;

pTotal = total;
pNext = next;
pTemp = temp;

so everytime u add into the temp, den u reset the pointers, so u dont have to write code more than once to do the same thing...

Code: Select all

// pTemp = pTotal + pNext
pTotal = temp;
pNext = next;
pTemp = total;

i program primarily in C, so hope this helps...

[amd-RS]

I'm trying to understand this, but I can't. Can you explain a bit more how the pointers will work !!!

Thanks in advance,

Aur

[LawrenceT]

as above...

Code: Select all

int i;
long total[1000], next[1000], temp[1000]; 
long * pTotal, pNext, pTemp; 
long carry;

pTotal = total; 
pNext = next; 
pTemp = temp;
carry = 0;

for (i = 0; i < 1000; i++)
{
pTemp[i] += carry + pNext[i] + pTotal[i];
carry = pTemp[i] / 100000; /* assuming 5 digits stored per element */
pTemp[i] %= 100000;
}

the switch btw pTotal and pTemp is so that u can continue the addition after loading the next number to be added into pNext.

[amd-RS]

Thanks for the answer, it's more clear to me

I did the problem, but when I submit I get WA. Can you give me some sample input (output), to compare with my results ?

Thanks a lot, Aur

[LawrenceT]

haha... i did this question almost half a year back... dun think i still haf my source... y dun u email your code to me and i'll take a look for u?

[url]mailto:funkyboy2000@swirvemail.com[/url]

[amd-RS]

[quote="LawrenceT"]haha... i did this question almost half a year back... dun think i still haf my source... y dun u email your code to me and i'll take a look for u?

I've sent to you ...

Thanks, Aur

[anupam]

here is my code it got tle but i have found no reason...
will you please notice ...?

Code: Select all

[cpp]
#include<stdio.h>
#define N 300

int a[N],c[N],b[N];
void sum()
{
	int car=0,i,r;
	for(i=0;i<N;i++) c[i]=0;
	for(i=0;i<N-2;i++)
	{
		r=a[i]+b[i]+car;
		c[i]=r%10;
		car=r/10;
	}
	if(car) c[i]=car;
	for(i=0;i<N;i++) a[i]=b[i];
	for(i=0;i<N;i++) b[i]=c[i];
}

main()
{
	int i,n;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<N;i++) a[i]=b[i]=0;
		b[0]=1;
		for(i=0;i<n;i++)
			sum();
		for(i=N-2;i>=0;i--) if(c[i]) break;
		if(i==-1) printf("0");
		for(;i>=0;i--) printf("%d",c[i]);
		printf("\n");
	}
	fflush(stdout);
	return 0;
}[/cpp]

thank you all [/b]

[dispanser]

Hi,

i tried solving problem #10334, and i keep getting WA. (i wouldn't be posting otherwise )

i played around a bit and found the following recursive formula:

[cpp]
NumReflections = 2*NumReflections[i-2] + NumReflections[i-3];
[/cpp]

that makes a lot of sense to me, because:

There are three lines, and incoming rays are not reflected at the first one, so they can either be reflected at the second or third one. if they are reflected at the second line, they have to be reflected again at the first line (to stay within the glasses) and thus, we have the starting situation with two reflections less. The same applies when the first reflection is at the third line, and the second reflection at the first.

[cpp]
NumReflections = 2*NumReflections[i-2]
[/cpp]

if the first reflection is at the third and the second reflection at the second line, the third reflection must be at the 3rd line again (to keep the ray in) and thus, we have the situation as if we had three reflections less.

[cpp]
+NumReflections[i-3]
[/cpp]



my result for input 1000 is:
6578664823929873592011106699924335801872430242281
6889418509635076750588795656206934732480158842776
6368023274811673465745239781317521995983112319878
7005665591519630984812879468605654452001924485541
1976

and for 10:
144
for 20:
17711

i love my formula too much to just drop it, but every hint is highly appreciated.

thanks in advance,

thomas

[Dominik Michniewski]

If I correct remmber this problem is involwed with Fibbonacci numbers

Best regards
DM

[Per]

Yes, and Thomas' formula is indeed one way to express fibonacci numbers.

Thomas: your output for 10 and 20 are correct, but for 1000 you are way off. The correct answer contains 210 digits, begins with 11379... and ends with ...32376.

My guess is that you probably have some small mistake in your bignum code.

[anupam]

it is a big integer problem, you can get ac by using the long base system

[dispanser]

Fibonacci? Well it looked a bit like it, but the starting numbers did not look like it, so i figured that it would be slightly different. i feel dumb now .

anyway, thanks for your help.



off to track down the bug in my lovely bigint class

Thomas