Page 4 of 5
Re: 10183 - How many Fibs?
Posted: Sat Aug 02, 2008 9:24 pm
by x140l31
Can anyone help me?
I don't know why WA!! I've tried all I/O and I get correct answer, except
1 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
because it isn't a correct input, no?
Otherwise, a<=b<=10^100
Re: 10183 - How many Fibs?
Posted: Sat Aug 02, 2008 9:24 pm
by x140l31
I fix it changing the fib numbers that I calculate to 500
I don't why doesn't work with 475 fib numbers if the 475th number is:
1344719667586153181419716641724567886890850696275767987106294472017884974410332069524504824747437757
that have 101 digits...
it must be that the Input Specification is wrong....
Re:
Posted: Tue Oct 07, 2008 7:33 am
by stcheung
vijay03 wrote:Can`t binary be used only for searching an exact term? If we use lower_bound and upper_bound, we`ll have to find the smallest fib greater than lower_bound and the highest fib lower than upper_bound and subtract the indices of those two fibs to get the answer right? So how can we use binary search for that?
Here's another idea instead of using binary. Have an array that stores the sequence number of all fib numbers whose length corresponds to the array index. For instance, arr[2] would store the fib sequence number for 13, 21, 34, 55, 89. So if you are given "10 10000", you only need to compare "10" with the ones represented by arr[2] and "10000" with the ones represented by arr[5].
Re: 10183 - How many Fibs?
Posted: Thu Feb 12, 2009 7:20 am
by Obaida
I checked all the test cases in the board seems right.. I thing it's a silly mistake. But i can't figure it out!
Some 1 plz help...
Re: 10183 - How many Fibs?
Posted: Sat Feb 14, 2009 5:53 pm
by Moshiur Rahman
for the input:
your program returns 4. when the correct answer should be 2.
Re: 10183 - How many Fibs?
Posted: Sun Feb 15, 2009 1:37 pm
by Obaida
You know how stupid i am?
I was considering for the input 1. But why i didn't considered it for 0?
This is really a shame!!!
Re: 10183 - How many Fibs?
Posted: Thu Jul 30, 2009 10:08 am
by masud93
Why it is Compilation Error.Pls help
Code: Select all
#include<stdio.h>
#include<string.h>
char z[100000],a[100000],b[100000],sto[100000][100000];
int flag=0,result=0,k=2;
void reverse(char *x)
{
int i,j,n,temp;
n=strlen(x);
for(i=n-1,j=0;j<n/2;i--,j++)
{
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
void add_zero(char *x,char *y)
{
int i,j=0,n1,n2;
n1=strlen(x);
n2=strlen(y);
for(i=0;i<n2-n1;i++)
z[i]='0';
while(i<n2)
z[i++]=x[j++];
z[i]='\0';
strcpy(x,z);
}
int compare(char *sto)
{
int n_a,n_b,sum,n_sto,i=0;
if(flag==0)
{
n_a=strlen(a);
n_sto=strlen(sto);
for(i=result=0;a[i];i++)
{
sum=(a[i]-'0')-(sto[i]-'0');
if(sum<0)
{
result=-1;
break;
}
else if(sum>0)
{
result=1;
break;
}
}
}
else
{
n_b=strlen(b);
n_sto=strlen(sto);
if(n_sto>n_b)
result=-1;
else if(n_b>n_sto)
result=1;
else
{
for(i=result=0;b[i];i++)
{
sum=(b[i]-'0')-(sto[i]-'0');
if(sum<0)
{
result=-1;
break;
}
else if(sum>0)
{
result=1;
break;
}
}
}
}
return result;
}
void add(char *x,char *y)
{
int i,carry=0,sum=0,n;
n=strlen(x);
reverse(x);
reverse(y);
for(i=0;x[i];i++)
{
sum=x[i]-'0'+y[i]-'0'+carry;
if(sum>9)
{
sum=sum%10;
carry=1;
}
else
carry=0;
z[i]=sum+'0';
}
if(carry==1)
z[i++]='1';
z[i]='\0';
reverse(z);
strcpy(sto[k++],z);
}
int main()
{
int i,n1,n2,n,count,f;
char x[100000]="1",y[100000]="2";
strcpy(sto[0],x);
strcpy(sto[1],y);
for(i=1;i<=500;i++)
{
n1=strlen(x);
n2=strlen(y);
if(n1<n2)
add_zero(x,y);
else if(n1>n2)
add_zero(y,x);
add(x,y);
reverse(y);
strcpy(x,y);
strcpy(y,z);
}
while(scanf("%s%s",a,b)==2)
{
if(a[0]=='0' && b[0]=='0')
break;
count=flag=f=0;
n1=strlen(a);
for(k=0;;k++)
{
n=strlen(sto[k]);
if(n1==n)
break;
}
for(;;)
{
result=compare(sto[k]);
if(result<=0)
{
for(flag=1;;k++)
{
result=compare(sto[k]);
if(result>=0)
count++;
else
{
f=1;
break;
}
}
}
else
k++;
if(f==1)
break;
}
printf("%d\n",count);
}
return 0;
}
Re: 10183 - How many Fibs?
Posted: Thu Jul 30, 2009 10:43 am
by mf
Because "char sto[100000][100000]" is way too big.
Pls help
"Pls" is not a word! Get a spellchecker.
10183 - How many Fibs?
Posted: Mon Aug 03, 2009 2:56 am
by sayem
can u tell why wrong answer?
Code: Select all
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define MAX 1046
void sum(char first[],char sec[],char res[])
{
int f,s,sum,now;
f=strlen(first)-1;
s=strlen(sec)-1;
int x;
if(f>s) now=f;
else now=s;
x=now;
for(sum=0;(f>=0 && s>=0);now--)
{
sum=(first[f]-'0')+(sec[s]-'0')+sum;
res[now]=sum%10+'0';
sum=sum/10;
--f,--s;
}
if(f>=0)
{
for(;f>=0;now--)
{
sum=first[f]+sum-'0';
res[now]=sum%10+'0';
sum=sum/10;
--f;
}
}
else
{
for(;s>=0;now--)
{
sum=sec[s]+sum-'0';
res[now]=sum%10+'0';
sum=sum/10;
--s;
}
}
if(sum!=0)
{
for(int i=x;i>=0;--i)
res[i+1]=res[i];
res[0]=sum+'0';
}
}
int main()
{
int number=3;
char pre_1[MAX],pre_2[MAX];
strcpy(pre_1,"1");
strcpy(pre_2,"2");
char fibo[500][MAX];
strcpy(fibo[1],pre_1);
strcpy(fibo[2],pre_2);
while(strlen(pre_2)<=102)
{
char now[MAX]={" "};
sum(pre_1,pre_2,now);
strcpy(pre_1,pre_2);
strcpy(pre_2,now);
strcpy(fibo[number],pre_2);
++number;
}
char a[MAX],b[MAX];
while(scanf("%s%s",a,b)==2)
{
int i,k=strlen(a),temp=0;
bool flag=false;
for(i=0;i<k;++i)
{
if(!isdigit(a[i]))
{
flag=true;
break;
}
}
if(flag==true) break;
k=strlen(b);
for(i=0;i<k;++i)
{
if(!isdigit(b[i]))
{
flag=true;
break;
}
}
if(flag==true) break;
k=strlen(a);
while(a[temp]=='0') temp++;
for(i=0;temp<k;++i,temp++)
a[i]=a[temp];
a[i]='\0';
k=strlen(b);
temp=0;
while(b[temp]=='0') temp++;
for(i=0;temp<k;++i,temp++)
b[i]=b[temp];
b[i]='\0';
if((strlen(a)>strlen(b))||(strlen(a)==strlen(b) && strcmp(a,b)>0))
{
char t[1000];
strcpy(t,a);
strcpy(a,b);
strcpy(b,t);
}
if(strlen(b)==102 && strcmp(b,"100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")==0);
else if(strlen(b)==0 || strlen(a)>101 || strlen(b)>101) break;
int num=0;
for(i=1;i<=number;++i)
{
if(strlen(a)<=strlen(fibo[i]) && strlen(b)>=strlen(fibo[i]))
{
if(strlen(a)==strlen(fibo[i]) && strcmp(a,fibo[i])>0)
continue;
if(strlen(b)==strlen(fibo[i]) && strcmp(b,fibo[i])<0)
break;
num++;
}
}
printf("%d\n",num);
}
return 0;
}
10183 why worng answer?
Posted: Thu Jul 29, 2010 7:47 am
by @mjad
give me some critical input
to find out WA
Re: 10183 CE? any body help me pleaseee
Posted: Thu Jul 29, 2010 8:55 pm
by sohel
You should be able to see the reason for compile error by clicking on 'compile error' message in the submission page!
Re:
Posted: Mon Sep 06, 2010 4:07 am
by sh415
Caesum wrote:Can anyone confirm the following input:
10 100
1234567890 9876543210
3 5
5 8
0 1
1 2
0 2
0 7
298611126818977066918552 483162952612010163284885
1 36726740705505779255899443
8 12
8 13
1 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
21 1
0 0
gives the following output:
5
4
2
2
1
2
2
4
2
123
1
2
483
7
there is no such input such that 21 1
the input must be 1 21................
yeh; except last one my AC code gives same output...................
Re: 10183 why worng answer?
Posted: Thu Nov 04, 2010 3:59 am
by @mjad
please help me why WA?
Code: Select all
#include<iostream.h>
#include<string.h>
//using namespace std;
int compare(char a[100009],char b[100009]);
void sum(char a[100009],char b[100009]);
void fact(char f1[100009],char f2[100009]);
char f1[100009],f2[100009];
long z;
int main()
{
char first[100009],second[100009];
int n;
int i;
//freopen("test.txt","r",stdin);
while(1){
cin>>first>>second;
if(first[0]-48==0&&second[0]-48==0)
break;
fact(first,second);
}
return 0;
}
void fact(char first[100009],char second[100009])
{
long count=0,m,n=0;
f1[0]='1';
f2[0]='2';
f2[1]=f1[1]='\0';
m=compare(first,second);
if(m==2||m==1)
return ;
do
{
if(n==0){
m=compare(f1,first);
if(m==1){
m=compare(f1,second);
if(m==0)
{
count++;
n++;
}
}
}
sum(f1,f2);
m=compare(f1,second);
if(n!=0&&m==0)
count++;
} while(m!=1&&m!=2);
if(n!=0)
cout<<count<<endl;
return ;
}
void sum(char a[100009],char b[100009])
{
char num[100009],num2[100009],result[100009];
long l1,l2,carry=0,index=0,t,i,j=0;
l1=strlen(a);
l2=strlen(b);
if(l1>=l2){
strcpy(num,a);
strcpy(num2,b);
}
else{
strcpy(num,b);
strcpy(num2,a);
l1=l2;
}
l2=strlen (num2);
while(l2)
{
l2--;l1--;
t=(num[l1]-48)+(num2[l2]-48)+carry;
result[index++]=t%10+48;
carry=t/10;
}
if(l1!=0)
while(l1)
{
l1--;
t=(num[l1]-48)+carry;
result[index++]=(t%10)+48;
carry=t/10;
}
if(carry)
result[index++]=carry+48;;
result[index++]='\0';
strcpy(f1,f2);
for(i=index-2;i>=0;i--)
f2[j++]=result[i];
f2[j++]='\0';
return ;
}
int compare(char first[100009],char second[100009])
{
int i,l1,l2;
l1=strlen(first);
l2=strlen(second);
if(l1>l2)
return 1;
if(l2>l1)
return 0;
for(i=0;i<l1;i++){
if((first[i]-48)>(second[i]-48))
return 1;
if((first[i]-48)<(second[i]-48))
return 0;
}
return 2;
}
Re: 10183 - How many Fibs?
Posted: Sun Jul 01, 2012 7:59 pm
by sith
Hello
Why I'am getting WA
Code: Select all
import java.io.*;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
List<BigDecimal> fibonacciNumber = new ArrayList<BigDecimal>();
fibonacciNumber.add(BigDecimal.ONE);
fibonacciNumber.add(BigDecimal.valueOf(2));
Scanner scanner = new Scanner(reader);
BigDecimal maxValue = BigDecimal.valueOf(10).pow(100);
int index = 2;
BigDecimal newFib = BigDecimal.ZERO;
while (newFib.compareTo(maxValue) <= 0) {
newFib = fibonacciNumber.get(index - 1).add(fibonacciNumber.get(index - 2));
fibonacciNumber.add(newFib);
index++;
}
try {
BigDecimal first;
BigDecimal second;
while (!(first = new BigDecimal(scanner.next())).equals(BigDecimal.ZERO) && !(second = new BigDecimal(scanner.next())).equals(BigDecimal.ZERO)) {
int start = 0;
int end = 0;
for (int i = 0; i < fibonacciNumber.size(); i++) {
BigDecimal bigDecimal = fibonacciNumber.get(i);
if (first.compareTo(bigDecimal) <= 0) {
start = i;
break;
}
}
for (int i = start; i < fibonacciNumber.size(); i++) {
BigDecimal bigDecimal = fibonacciNumber.get(i);
if (second.compareTo(bigDecimal) <= 0) {
end = i;
break;
}
}
int result = end - start;
if (fibonacciNumber.get(start).equals(first) && fibonacciNumber.get(end).equals(second)) {
result++;
}
writer.write(Integer.valueOf(result).toString());
writer.write("\n");
}
writer.flush();
} catch (IOException e) {
}
}
}
Re: 10183 - How many Fibs?
Posted: Mon Jul 02, 2012 9:59 pm
by brianfry713