10334 - Ray Through Glasses

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

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;

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;

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
toZero(n1);n1 := 1;
toZero(n2);n2 := 2;
while (n > 0) do
begin
copy(n2,t);
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;
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
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
i think the 1000th element has 210 digits.
you can read/write long long with "%lld", but it only has 18 digits.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Yes

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
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:
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, next, temp;
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
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am

10334

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

Aur

LawrenceT
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:
as above...

Code: Select all

int i;
long total, next, temp;
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
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am
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
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:
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
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am
[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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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=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]
"Everything should be made simple, but not always simpler"

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:

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.

thomas

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
If I correct remmber this problem is involwed with Fibbonacci numbers

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
it is a big integer problem, you can get ac by using the long base system "Everything should be made simple, but not always simpler"

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:  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