OJ Board

Posted: **Fri Oct 01, 2004 3:06 am**

Got it, thanks.

Posted: **Fri Oct 01, 2004 5:46 am**

Hi!! trashmai this bug was hard to take this are only a few inputs for what your programs give the bad ouputs, there are a lot of more and you have to check your code carefully to see whats the error
Inputs:

Code: Select all

your outputs:

Code: Select all

The Fibonacci number for 229 is 3226150438368547835801863092826500000354271239929
The Fibonacci number for 331 is 6689966153880050315310000081241745415306766517246774551964595292186469
The Fibonacci number for 676 is 843645135740916443113832571217701196011659994669538939065731942674862905
3974339797159317419590735252363050000074026438339415322804865241443907
The Fibonacci number for 707 is 253966629073281232189337259218152410852422549133431257743959463526688432
142507262909546057630000094211512963232351039521888530847428153536779619
22313
The Fibonacci number for 883 is 153674333621065775410236648042084662848933007661143980817104150291913024
432550388836715205238203065555551077282341319994362147315439893310354801
174814919204532789834000009134843095074197
The Fibonacci number for 1259 is 583383407137109552695513219117000889452560276181560389185306406504719105
574248327539873798779599048248777807405108011571417504604341139469749502
951032384890088109110694199323385025755211080077569007602267187819396794
861000006853565220909996090221575992411145026841
The Fibonacci number for 1281 is 231037330581201613541810332878320047610968044603927904276201130919668151
578332280814068820905015484222088668506982436676293106266035951346124145
138641474888037614360000011519986001438137772940652463498766997454913312
61345290543473787767781052429221179160066016980283106
The Fibonacci number for 1354 is 416658164472158071807004334011404711927666607437877761909757165990522629
372073953347821825733637582667189807220000005779204928063590304756708079
368880036349918299848247305901165170141448475237090581881627034394689924
70659897525400423246616595745419783065444393918471179930961988965047
The Fibonacci number for 1457 is 139799893979028759227121500000159855130950737882832056931993444610576633
191486820314303072981531995383574898970680105991014251835508971894751737
700068014881489090339915162368380430230277494790402145025349067475687573
521289419187221479911222033678107616022967556666725944711018417118037614
388065508852973437
The Fibonacci number for 1482 is 234529700146491714106444267259079300000563822415114892210296831097700361
599439774917985459968990802695003946883045903280232786306363211148294325
030277917998033362554592572516119877030072224731922518399843586480685765
039175769695008728602465157615574612684826383120000072573172905199389544
514613676964809840319416
The Fibonacci number for 1639 is 
151794965414245575475610557277367913657868530085935306898024677804332381
576028600052145775123817130102261797063133262881886719453262108729998163
976736294999445827509895136802056382838174903413894651348813115072124160
905521195128279291911391937000001882186786177559094392685074951575821648
87799547628124544188082939220697351008141459335979517261
The Fibonacci number for 1763 is 124659321435381971396290243033354856707490000029306907413118021184590814
978224710076182722066427798665925476044313148203890280058571617345860959
476669723263556029608450958579721041198777594025743381296443523734496607
988970944187171129099526952952452372797989325711379155288603825693592980
087360074901115492823372308658631509351460749939845244864514159039171977
9685843017
The Fibonacci number for 2074 is 123276664822441436802417912202266906557618363968891298464804812547681947
757546599762101329097449904139951834497802051982378337963149864691431740
062807323321653290725458035843833438209310272318105311673692785921921823
265175263222862328791594446699982499029989000006805778779220595452690751
429602631793206189081195838617678783129420515288491763988817830559379600
923971216551876929511120684553377626648465398022823371885948010159198648
407
The Fibonacci number for 2271 is 182576974275695146285730865253562912970948463826485206315031878888774112
658505557644300099714892829352811873231147915328715899859090200639020402
315250996991752328661366622635292199213633894412917233216738543821379455
006225214434028930051755328812562722869324582832961892403895965812733471
282488387377002233486518685812736841137048837090000057740990780020625243
889930085754991215013246114390093777056075882031106250250290227071112792
30143119635543337370882239064337292667715554
The Fibonacci number for 2454 is 320762929561828896801421550206212157187990950003192169549688148507307136
875401893375448890453978260944744399653349037266527236694420616552028266
145947141833427249255745627435188748719598808192743303578503677388708560
417600991443804090000037482530368830837555445098983643117766841642291685
057464047224116333200626507879039460242602181935065137363512178132953574
879432331831101753521189949148748334398851600569412041884977369262640138
305740579231107790310020056859832392975374316344797776115300505759027571
3225142472

My ouputs the diferences is for a digit in some case in others the diferences is for 2 digits

Code: Select all

The Fibonacci number for 229 is 322615043836854783580186309282650000354271239929
The Fibonacci number for 331 is 668996615388005031531000081241745415306766517246774551964595292186469
The Fibonacci number for 676 is 843645135740916443113832571217701196011659994669538939065731942674862905
397433979715931741959073525236305000074026438339415322804865241443907
The Fibonacci number for 707 is 253966629073281232189337259218152410852422549133431257743959463526688432
142507262909546057630000942115129632323510395218885308474281535367796192
2313
The Fibonacci number for 883 is 153674333621065775410236648042084662848933007661143980817104150291913024
432550388836715205238203065555551077282341319994362147315439893310354801
17481491920453278983400009134843095074197
The Fibonacci number for 1259 is 583383407137109552695513219117000889452560276181560389185306406504719105
574248327539873798779599048248777807405108011571417504604341139469749502
951032384890088109110694199323385025755211080077569007602267187819396794
86100006853565220909996090221575992411145026841
The Fibonacci number for 1281 is 231037330581201613541810332878320047610968044603927904276201130919668151
578332280814068820905015484222088668506982436676293106266035951346124145
138641474888037614360000115199860014381377729406524634987669974549133126
1345290543473787767781052429221179160066016980283106
The Fibonacci number for 1354 is 416658164472158071807004334011404711927666607437877761909757165990522629
372073953347821825733637582667189807220000057792049280635903047567080793
688800363499182998482473059011651701414484752370905818816270343946899247
0659897525400423246616595745419783065444393918471179930961988965047
The Fibonacci number for 1457 is 139799893979028759227121500001598551309507378828320569319934446105766331
914868203143030729815319953835748989706801059910142518355089718947517377
000680148814890903399151623683804302302774947904021450253490674756875735
212894191872214799112220336781076160229675566667259447110184171180376143
88065508852973437
The Fibonacci number for 1482 is 234529700146491714106444267259079300005638224151148922102968310977003615
994397749179854599689908026950039468830459032802327863063632111482943250
302779179980333625545925725161198770300722247319225183998435864806857650
391757696950087286024651576155746126848263831200007257317290519938954451
4613676964809840319416
The Fibonacci number for 1639 is 151794965414245575475610557277367913657868530085935306898024677804332381
576028600052145775123817130102261797063133262881886719453262108729998163
976736294999445827509895136802056382838174903413894651348813115072124160
905521195128279291911391937000018821867861775590943926850749515758216488
7799547628124544188082939220697351008141459335979517261
The Fibonacci number for 1763 is 124659321435381971396290243033354856707490000293069074131180211845908149
782247100761827220664277986659254760443131482038902800585716173458609594
766697232635560296084509585797210411987775940257433812964435237344966079
889709441871711290995269529524523727979893257113791552886038256935929800
873600749011154928233723086586315093514607499398452448645141590391719779
685843017
The Fibonacci number for 2074 is 123276664822441436802417912202266906557618363968891298464804812547681947
757546599762101329097449904139951834497802051982378337963149864691431740
062807323321653290725458035843833438209310272318105311673692785921921823
265175263222862328791594446699982499029989000068057787792205954526907514
296026317932061890811958386176787831294205152884917639888178305593796009
239712165518769295111206845533776266484653980228233718859480101591986484
07
The Fibonacci number for 2271 is 182576974275695146285730865253562912970948463826485206315031878888774112
658505557644300099714892829352811873231147915328715899859090200639020402
315250996991752328661366622635292199213633894412917233216738543821379455
006225214434028930051755328812562722869324582832961892403895965812733471
282488387377002233486518685812736841137048837090000577409907800206252438
899300857549912150132461143900937770560758820311062502502902270711127923
0143119635543337370882239064337292667715554
The Fibonacci number for 2454 is 320762929561828896801421550206212157187990950003192169549688148507307136
875401893375448890453978260944744399653349037266527236694420616552028266
145947141833427249255745627435188748719598808192743303578503677388708560
417600991443804090000374825303688308375554450989836431177668416422916850
574640472241163332006265078790394602426021819350651373635121781329535748
794323318311017535211899491487483343988516005694120418849773692626401383
057405792311077903100200568598323929753743163447977761153005057590275713
225142472

Hope it helps
Keep posting!!

Sorry for ocuped that kind of space but this is a friend that need help

Posted: **Fri Oct 01, 2004 8:54 am**

Thank you!!

I'll be more carefull next time!!

Posted: **Sun Oct 03, 2004 11:05 pm**

I try to solve the "Fibonacci" problem, but i receive a TLE.
I think my solution is well optimized and very fast. So i suppose that it may be a problem of input/output, something is wrong...
Are you any suggestion about it?

[cpp]
char b[5001];
big_int f[5001];

big_int a[2][2];
big_int **c;
big_int **tmp, **t;

void pow_r(int n) {
if (n==0) {
c[0][0] = 1;
c[1][1] = 1;
c[0][1] = 0;
c[1][0] = 0;
return;
}
pow_r(n>>1);

tmp[0][0] = c[0][0]*c[0][0] + c[0][1]*c[1][0];
tmp[0][1] = c[0][0]*c[0][1] + c[0][1]*c[1][1];
tmp[1][0] = c[1][0]*c[0][0] + c[1][1]*c[1][0];
tmp[1][1] = c[1][0]*c[0][1] + c[1][1]*c[1][1];
t = c;
c = tmp;
tmp = t;

if (n&1) {
tmp[0][0] = c[0][0]*a[0][0] + c[0][1]*a[1][0];
tmp[0][1] = c[0][0]*a[0][1] + c[0][1]*a[1][1];
tmp[1][0] = c[1][0]*a[0][0] + c[1][1]*a[1][0];
tmp[1][1] = c[1][0]*a[0][1] + c[1][1]*a[1][1];
t = c;
c = tmp;
tmp = t;
}

f[n+1] = c[0][0];
f[n] = c[0][1];
b[n+1] = b[n] = 1;

}

void calc(int n) {
if (b[n]) return;
int i;
for (i=1; i<10 && n-i>0; i++) if (b[n-i] && b[n-i-1]) break;
if (n-i>=0 && b[n-i]) {
for (int j = n-i+1; j<=n; j++) f[j] = f[j-1] + f[j-2], b[j] = 1;
return;
}
pow_r(n-1);

}

int main(void) {

f[0] = 0;
f[1] = 1;
memset(b, 0, sizeof(char)*5001);
b[0] = b[1] = 1;

c = new (big_int *)[2];
c[0] = new big_int[2];
c[1] = new big_int[2];

tmp = new (big_int *)[2];
tmp[0] = new big_int[2];
tmp[1] = new big_int[2];

a[0][0] = 1;
a[0][1] = 1;
a[1][0] = 1;
a[1][1] = 0;

int n;

while (1) {
cin >> n;
if (cin.eof()) break;
calc(n);
cout << "The Fibonacci number for " << n << " is " << f[n] << endl;
}
return 0;
}
[/cpp]

Posted: **Mon Oct 04, 2004 6:57 am**

Without testing your code, I can give you a hint:
Generate all 5000 fibonacci number and store them in a BigNum array and then start taking input and just print the output from the array index!

Posted: **Mon Oct 04, 2004 8:19 pm**

This code gets me AC in 3.2 seconds when I use my own bigint class.
(Although it only needs 0.13s to generate all fibonacci numbers on my computer)

You need to optimize either your bigint class or your algoritm.

Posted: **Mon Oct 04, 2004 9:35 pm**

Yes, the problem is in your Bignum class. I got ac with the algorithm in 3:8s. You may use java biginteger

Posted: **Tue Oct 05, 2004 5:33 am**

do you still need help in this one because I can tell you that class bignum is too huge, the mine is not so long,

, just post and i help you

Posted: **Tue Oct 05, 2004 6:32 am**

Yeah,i really appreciate ur help

Posted: **Wed Oct 06, 2004 5:12 am**

Hi !! Morning my class of bignum I found in http://www.cs.sunysb.edu/~skiena/392/programs/ here is bignum.c the only that you have to do is change the code by your use in C++ is not so hard

, and about the problem I only can say that you have to precalculated all the answers in a array is not so big the biggest number have less than 1100 digits

Hope it Helps
Keep posting !!

Posted: **Fri Oct 15, 2004 10:56 am**

Yes, finaly i realized that my big_int class is too slow in converting the binary numbers into decimals. Must think about fast multiplication algorithm (like Karatsuba) for fast coverting...

Posted: **Mon Oct 25, 2004 8:28 pm**

Hi all
I dont know why my problem is wrong, it gave OLE last time i submitted
Please, if anybody finds a silly mistake, reply the topic
Here is the source code

[c]
/* Fibonacci Freeze UVA 495 */
#include <stdio.h>
#include <string.h>

int fibo [5010] [1100];

int main () {
int llevo, i, j;
int n;

memset(fibo, 0, sizeof(fibo));
fibo [0][0] = 1;
fibo [1][1] = 1;
fibo [1][0] = 1;
for (i = 2; i <= 5000; i++) {
llevo = 0;
for (j = 1; j <= fibo [i-1][0] + 1; j++) {
fibo [j] = fibo [i-1][j] + fibo [i-2][j] + llevo;
llevo = fibo [j] / 10;
fibo [j] %= 10;
}
fibo [0] = fibo [i-1][0];
if ( fibo [fibo [0] + 1] )
fibo [0] ++;
}

for (;; ) {
if (!scanf ("%d", &n)) break;
printf ("The Fibonacci number for %d is ", n);
for (i = fibo[n][0]; i >= 1; i--)
printf ("%d", fibo [n]);

printf ("\n");
}

return 0;
}

[/c]

Thanks
Luis

Posted: **Mon Oct 25, 2004 10:03 pm**

[c]
for (;; ) {
if (!scanf ("%d", &n)) break;
/* change the line above to if(scanf("%d",&n)==EOF) break; */
printf ("The Fibonacci number for %d is ", n);
[/c]

hope this helps

Posted: **Tue Oct 26, 2004 11:31 pm**

I got AC !!!
Thanks very much, I had some headache with this problem

Posted: **Thu Nov 04, 2004 4:18 pm**

my programme generates exactly the same answer as urs (i pasted both our outputs into a text file to look at it very closely), but it always get WA. this is stupid =(, can someone point out where's problem?

i modified it to an applet u can try here
here is my code:
[java]
class Main
{
static int main(){
int n=-1,count=0;
char[] c=new char[5];
for(;;){
try{
for(;;){
n=System.in.read();
if((char)n=='\n')
break;
else if(n<0)
return 0;
c[count]=(char)n;
count++;
}
}catch(Exception e){}
char[] d=new char[count];
for(int i=0; i<count;i++)
d=c;
long input=Long.parseLong(new String(d));
count=0;
process(input);
}
}
static int process(long n){
char[] temp1={'0'},temp2={'1'};
long i=1;
if(n==0)
System.out.println("The Fibonacci number for "+n+" is 0");
else if(n==1 || n==2)
System.out.println("The Fibonacci number for "+n+" is 1");
else{
while(i!=n){
temp1=add(temp1,temp2);
i++;
if(i==n){
System.out.println("The Fibonacci number for "+(int)n+" is "+new String(temp1));
return 0;
}
temp2=add(temp1,temp2);
i++;
}
System.out.println("The Fibonacci number for "+(int)n+" is "+new String(temp2));
}
return 0;
}
static char[] add(char[] a, char[] b){
int maxlength=0;
boolean moreThanTen=false;
int diff=Math.abs(a.length-b.length);
if(a.length>b.length){
maxlength=a.length;
char[] c=new char[a.length];
for(int i=0;i<a.length;i++){
if(i<diff)
c='0';
else
c=b[i-diff];
}
b=c;
}
else if(b.length>a.length){
maxlength=b.length;
char[] c=new char[b.length];
for(int i=0;i<b.length;i++){
if(i<diff)
c='0';
else
c=a[i-diff];
}
a=c;
}
else
maxlength=a.length;
char[] result=new char[maxlength+1];
for(int i=maxlength-1;i>=0;i--){
int x=0;
int bb=(int)(b)-48;
int aa=(int)(a)-48;
if(moreThanTen==true)
x=aa+bb+1;
else
x=aa+bb;
if(x<=9){
result[i+1]=(char)(x+48);
moreThanTen=false;
}
else{
result[i+1]=(char)(x-10+48);
moreThanTen=true;
}
}
if(moreThanTen==true)
result[0]=(char)(1+48);
else{
char[] result2=new char[result.length-1];
for(int i=0;i<result2.length;i++)
result2=result[i+1];
return result2;
}
return result;
}
}
[/java]

OJ Board

495 - Fibonacci Freeze

495 (fibonacci) TLE because of in/out ???

495 - Fibonacci Freeze