10334 - Ray Through Glasses
Moderator: Board moderators
10334 - Ray Through Glasses
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]
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.
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...
i program primarily in C, so hope this helps...
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;
Code: Select all
// pTemp = pTotal + pNext
pTotal = temp;
pNext = next;
pTemp = total;
as above...
the switch btw pTotal and pTemp is so that u can continue the addition after loading the next number to be added into pNext.
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;
}
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]
[url]mailto:funkyboy2000@swirvemail.com[/url]
here is my code it got tle but i have found no reason...
will you please notice ...?
thank you all
[/b]
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]
![:oops:](./images/smilies/icon_redface.gif)
![:oops:](./images/smilies/icon_redface.gif)
![:oops:](./images/smilies/icon_redface.gif)
"Everything should be made simple, but not always simpler"
10334 - Ray Through Glasses [WA]
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
i tried solving problem #10334, and i keep getting WA. (i wouldn't be posting otherwise
![8)](./images/smilies/icon_cool.gif)
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
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
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.
![:)](./images/smilies/icon_smile.gif)
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.