FIBGAME - Editorial

editorial
,
1

PROBLEM LINK:

Practice

Author: Vaibhav Gautam
Tester: Illisha Singh , Jackson JoseKabir Kanha Arora, Nishank Suresh
Editorialist: Vaibhav Gautam

DIFFICULTY:

EASY

PREREQUISITES:

Math, Careful Observation

PROBLEM:

Given three consecutive integers a, b and c,
Is f(b) \times f(b)> f(a)* f(c)?
f(n): represents the n-th Fibonacci number.
f(1)=1 and f(2)=1.
f(n)= f(n-1)+f(n-2), n\geq3

QUICK EXPLANATION:

EXPLANATION:

First Subtask

Let’s try to solve the first subtask. Here, all the input numbers are less than or equal to 50. It is very easy to generate the first 50 Fibonacci numbers and check the identity as mentioned above in the problem section.
The code for the same is as follows:

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;
int main() {

    vector<ll>fibn(51);fibn[0]=0;fibn[1]=1;fibn[2]=1;
    for(int i=3;i<51;i++)
        fibn[i]=fibn[i-1]+fibn[i-2];
    int t ;cin>>t;
    while (t-- > 0) {
        ll a, b, c;
        cin>>a>>b>>c;
        if((fibn[b]*fibn[b])>(fibn[a]*fibn[c]))
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
}

The above code will give you 30 points for the first subtask.

You might get Wrong Answer, TLE, or Runtime Error on the second subtask based on your approach to generate the first 50 Fibonacci numbers.

Second Subtask

There are many ways to solve this. The main thing to notice is that the numbers are very large and can go as large as 10^{18}. At this point, one must realize that loop won’t work as it is guaranteed to give TLE.

Now, what you eventually want to know is the answer to the following question.
For what a, b & c $, f(b)*f(b) is greater than f(a)*f(c).
We will find the answer to this question from the solution of the first subtask.
Observe carefully, there can be no more than 50 cases in subtask 1. It is very easy to generate the answer for all of the 50 cases.
The answer to all the cases are given below:

1 2 3 NO

2 3 4 YES

3 4 5 NO

4 5 6 YES

5 6 7 NO

6 7 8 YES

7 8 9 NO

8 9 10 YES

9 10 11 NO

10 11 12 YES

11 12 13 NO

12 13 14 YES

13 14 15 NO

14 15 16 YES

15 16 17 NO

16 17 18 YES

17 18 19 NO

18 19 20 YES

19 20 21 NO

20 21 22 YES

21 22 23 NO

22 23 24 YES

23 24 25 NO

24 25 26 YES

25 26 27 NO

26 27 28 YES

27 28 29 NO

28 29 30 YES

29 30 31 NO

30 31 32 YES

31 32 33 NO

32 33 34 YES

33 34 35 NO

34 35 36 YES

35 36 37 NO

36 37 38 YES

37 38 39 NO

38 39 40 YES

39 40 41 NO

40 41 42 YES

41 42 43 NO

42 43 44 YES

43 44 45 NO

44 45 46 YES

45 46 47 NO

46 47 48 YES

47 48 49 NO

48 49 50 YES

I hope that everyone sees the pattern now. The answer is always alternating and depends only on the value of b. If b is odd the answer is YES and if b is even the answer is NO.

Alternate Explanation:

Use: Cassini’s Identity

SOLUTIONS:

Setter's Solution (C++) 
    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long int;
    int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t ;cin>>t;
    while (t-- > 0) {
        ll a, b, c;
        cin>>a>>b>>c;
        if(b%2==0)
            cout<<"NO\n";
        else
            cout<<"YES\n";
    }
}
Setter's Solution( Python ) 
    T=int(input())
    while(T>0):
        a,b,c=map(int,input().split())
        if(b%2==0):
            print("NO")
        else:
            print("YES")
        T-=1
Tester's Solution(Kabir Kanha Arora)( JAVA ) 
    import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            long a = scanner.nextLong();    // Useless
            long b = scanner.nextLong();
            long c = scanner.nextLong();    // Useless
            // Use Cassini's identity
            String ans = b % 2 == 0 ? "NO" : "YES";
            System.out.println(ans);
        }
    }
}
2

I think this solution works based on the above editorial:

#include <bits/stdc++.h>
using namespace std;
int main()
{
      int T;
       cin >> T;
       for(int i = 0; i < T; i++)
       {
             int a, b, c;             
             cin >> a >> b >> c;
             if(b%2 == 0)
             {
                     cout << "NO\n";
             }
             else{cout << "YES\n";}
       }

}

Yes @vaicr7bhav and @first_semester
I did make some silly mistakes indeed. I think I have corrected them now.

1 Like
4

It won’t work. You haven’t declared a,b and c. Also you are not printing a new line character.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
for(int i = 0; i < T; i++)
{
long long int a,b,c;
cin >> a >> b >> c;
if(b%2 == 0)
{
cout << “NO\n”;
}
else{cout << “YES\n”;}
}

}
The above code will work fine.

5

yes you are correct, his solution would not work due to silly mistakes :stuck_out_tongue: