0

I have been taking part in competitive coding of csacademy site. There I have come up with some question I guess it is well-known to most of you, which is about the following : given a number of stairs, calculating the number of ways we can traverse them; with each step of foot, one may land on the next step , or may skip one step and land on the following step.

As you probably know , it involves the Fibonacci method.
The base cases are as the following:

-in case of one step given - we have one way to traverse it.

-in case of two steps given - we have two ways to traverse them.

The input will start with a single line containing one integer t (1≤t≤5) specifying the number of instances of the problem. Each subsequent line will contain one instance of the problem – a single integer n (1≤n≤22000) specifying the number of steps in the stair case.

For each instance of the problem, the program must output one line containing a single integer – the number of ways the steps could be traversed.

The code I wrote for this problem with cpp - fails in some three test which I can not investigate since I run it with the platform of csacadamy site :

#include <iostream>
using namespace std;

int main()
{
  long long int t, n,res=0;
   cin>>t;
   while (t>0) {
     cin>>n;

    if (n==1)
    cout<<1<<endl;
    else if (n==2)
    cout<<2<<endl;


    else{
        long long int temp1=1,temp2=2;

        for (long long int i=2;i<n;i++){
         res = temp1 + temp2 ;
         temp1=temp2;
         temp2=res;

        }
        cout<<res<<endl;
    } 
   t--;

  }
  return 0;
}

However, I wrote the exact same code with Python, and it runs in 100% well:

t = int(input())
for i in range(t):
    res = 0
    n = int(input())  
    if n == 1:
        print(1)
        continue
    if n == 2:
        print(2)
        continue
    temp1 =1
    temp2 =2
    for j in range(2,n):
        res = temp1 + temp2
        temp1 = temp2
        temp2 = res
    print(res)

May you please help me know the reason for that?

galik
  • 15
  • 3
  • 1
    Please avoid `using namespace std;`. It is considered bad practice. See [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721) Also, `long long int` is equivalent to `long long`, so you can safely omit the `int`. – L. F. Jul 30 '19 at 06:38
  • 5
    Check what happens when you have one case and the input is 100 (see the output with the two programs) – ChatterOne Jul 30 '19 at 06:43
  • 1
    Its simple enough to check yourself, just run the code with the input of 22000 and you will see the incorrect result due to integer overflow – Alan Birtles Jul 30 '19 at 06:57
  • What is `sizeof(long long int)` ? Is it big enough to represent the result for the largest possible input ? (hint : unlikely) – Sander De Dycker Jul 30 '19 at 07:02
  • using the formula in https://www.mathsisfun.com/numbers/fibonacci-sequence.html only the 92nd Fibonacci number is representable in a 64 bit integer, the 93rd is `1.2e19`, the limit for 64 bit numbers is `9.2e18` – Alan Birtles Jul 30 '19 at 07:09
  • You might be interested in : [Big numbers library in c++](https://stackoverflow.com/questions/12988099/big-numbers-library-in-c) – Sander De Dycker Jul 30 '19 at 07:12
  • @L.F. `using namespace std` is safe inside a scope. In this case, inside the function. – Robert Andrzejuk Jul 30 '19 at 07:20
  • @RobertAndrzejuk I don't see how the `using namespace std;` in question is inside the function. – L. F. Jul 30 '19 at 07:22
  • Python has built in indefinite precision, C++ does not. Therefore the programs aren't the same. Recode the C++ version with a multiple precision integer library and you'll get the same result. – john Jul 30 '19 at 07:33
  • @L.F. It is not inside the function. It should/can be used inside the function. (Sorry if that was formulated unclearly) – Robert Andrzejuk Jul 30 '19 at 09:03

0 Answers0