### 10334 - Ray Through Glasses

Posted:

**Sun Jul 14, 2002 1:30 pm**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]

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]