POPEYE- Editorial

PROBLEM LINK:

Contest

Author: Rutuja Deshmukh
Tester: Vallabh Deshpande

DIFFICULTY:

Easy

PREREQUISITES:

Greedy, Math, Fibonacci.

PROBLEM:

Popeye has N different spinach cans. Each can have energy ei which is equal to the sum of energy that can be consumed from the previous two cans. The energy of the first two cans will be given to you. You have to calculate the energy he will get by consuming N-th can.

EXPLANATION:

As the energy of first two cans are given we can add them to find the energy of third can. Similarly , we can add the energy of pervious two cans to find the energy of next can. We can repeat this till N-th can. Your algo may fail due to the Overflow of Fibonacci Number beyond the range of 64 bit int hence we need to use long long in C++.

SOLUTIONS:

Setter's Solution
        t=int(input())
        while t>0:
            n,a,b = map(int,input().split())
            for i in range(2,n):
                c=a+b
                a=b 
                b=c
            print(b)
            t-=1
Tester's Solution
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
typedef long long ll;
typedef long double ld;

void solve(){
    ll a[3] = {0, 0, 0}, n;
    cin>>n>>a[0]>>a[1];
    if(n <= 2){
        cout<<a[n-1]<<"\n";
    }
    else{
        while(n-- > 2){
            a[2] = a[0];
            a[0] = a[1];
            a[1] = a[1] + a[2];
        }
        cout<<a[1]<<"\n";
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//oJudge();
	int t = 1;
	cin>>t;
	while(t--){
        solve();
	}
	return 0;
}