10450 - World Cup Noise

[Red Scorpion]

Thanks, Turuthok.
Got AC now.

[Zhao Le]

i have tried my ways but still got WA.
i know someone use long long but i still got WA
i here use double and precision set to zero.
but still failed, who can help me?
Here is my code.
----------------------------------
#include <iostream.h>
#define Max 51

double S[Max]={2,3};

void Cal()
{
int i;
for(i=2;i<Max;i++)
S=S[i-1]+S[i-2];
}

void main()
{
Cal();
int n;
cin>>n;
while(n--)
{
int i;
cin>>i;
cout<<"Scenario #"<<i<<":"<<endl;
cout.setf(ios::fixed);
cout.precision(0);
cout<<S[i-1]<<endl<<endl;
}
}

[Monzer Hossain]

cout<<"Scenario #"<<i<<":"<<endl;

In this line i is wrong.
Here should be a counter for number of current input
which starts from 1 instead of i which is input.

Monzer.

[Observer]

It's nice to see that so many various problems can be solved by Fibonacci Numbers!!

If there are more such prob. in ACM, tell me!!!

Btw, when n = 50, the answer should contain 11 digits.

[Thanatos]

Hey guys, I did the World Cup problem and did figure out why the answer was a Fibonacci number. So i coded this...

[cpp]
#include <iostream>
#include <math.h>

using namespace std;

long long fibo(int x)
{
return (long long)((pow((1+sqrt(5.))/2,x)-pow((1-sqrt(5.))/2,x))/sqrt(5.));
}

int main()
{
int x,i=1;
while (cin >> x)
cout << "Scenario #" << i++ << endl << fibo(x+2) << endl << endl;
return 0;
}[/cpp]

But i get WA?! Yes there is a formula for fibonacci's number and it does work...anyone help please?[/cpp]

[alu_mathics]

I think what you generate ,its an approximate value of fibo n.
You can use the general recursive formula.
that is
fibo[n]=fibo[n-1]+fibo[n-2];
Hope this will help you

[worldguy]

I tried to solve this problem using the long long type but failed. Well, when I shifted long long type to double type, I got it accepted. I'm wondering, why long long type gives out the incorrect answers?

[J&Jewel]

Hello friends....
I want to solve this problem....it was only the trick of fibonacci num...
I save them in an array. and compare each of the input of above....and all same....
But my program get WA why....?
I cant understand I use double too...
Here is my code.....Please Checked the code....

Code: Select all

#include<stdio.h>
double array[60];
void fibonacci(long a)
{
	 long i;
	 array[0]=0;
	 array[1]=1;
	 for(i=2;i<=a;i++)
	 {
			array[i]=array[i-1]+array[i-2];
	 }
}
int main()
{
	int input,n,i;
	//freopen("d:\\10450.txt","r",stdin);
	fibonacci(55);
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
			scanf("%d",&input);
			if(input==0)
				printf("0\n");
			else
				printf("%0.lf\n",array[input+2]);
	}
	return 0;
}

[vinit_iiita]

I am getting damn stupid WA ??..

Code: Select all

#include <iostream> 
#include <cmath> 
using namespace std; 
int main() 
{ 
int x,i=1;
int n;
cin>>n; 
while (i<=n){
cin >> x; 
long long int a,b,c;
a=1;b=1;
for (int j=3;j<=x+2;j++)
{
    int t;
    t=a;
    a=a+b;
    b=t;
}
cout << "Scenario #" << i++ <<":"<< endl << a << endl << endl; 
}
return 0; 
}

plz help me out...

[kolpobilashi]

you need to change following things:

Code: Select all

for (int j=3;j<=x+2;j++) 
{ 
    int t; 
    t=a; 
    a=a+b; 
    b=t; 
} 

in the above part declare j and t as long long.
moreover, for

Code: Select all

x=0
a=0

but yours one gives 1.

hope you'll get AC

[vinit_iiita]

thanx i got ac

[Obaida]

Code: Select all

Accepted

[Jan]

Just think that how many times the recursive calls being used? Say, for n = 6 you have to calculate for both 5 and 4, again for 5 you have to calculate both 4 and 3. 4 is calculated twice. So, if you think a while you will find that the number of calls are increasing exponentially.

[Obaida]

Thanks jan bi.
i got acc.

[newton]

Its a simple Java code
but ONLINEJUDGE says me RE!!
why can u find plz.

Code: Select all

import java.util.*;
import java.io.*;
import java.math.BigInteger;

class WorldCup{		
	WorldCup(){};	
	public static void main(String args[]){
		int i,n,num;
		BigInteger B[] = new BigInteger[55];
		Scanner sc = new Scanner(System.in);
				
		B[0] = new BigInteger("1");
		B[1] = new BigInteger("2");
		for(i = 2; i< 55; i++){
			B[i] = B[i-1].add(B[i-2]);			
		}
		n = sc.nextInt();
		for(i = 1; i <= n; i++){
			num = sc.nextInt();
			System.out.println("Scenario #"+i+":\n"+B[num]);
			System.out.println("");		
		}
	}
}