FEST02 - Editorial

Problem Link:
[CONTEST][1]
[PRACTICE][3]

Author- [Sameer Taneja][4]

Tester- [Vipin Khushu][2]

Editorialist- [Sameer Taneja][4]

Difficulty:
Simple

Prerequisites:
Easy

Problem:
We have to check nth element of unique series is positive or not? Where unique series just like fibbonaci series u(n)=u(n-2)-u(n-1)

Explanation:
Firstly we have to find nth unique number of the series .we can find this simple recursion or simple loop with 2-3 variables where a=100,b=97 initially.
For(i=2;i<n;i++){
nbsp;nbsp; c=a-b;
nbsp;nbsp;a=b; b=c;
}
Recurrsion:
Uni(int n){
If (n==1) return 100;
Else if (n==2)return 97;
Else return Uni(n-2)-Uni(n-1);
}
But it takes a lot time to calculate nth number in series as testcases< 10^5 and n< 10^5.it will lead to TLE in problem so we use an array to store unique series upto 10^5 elements. And can excess it at any time according to testcases.There will be no problem of TLE in it as we just have to apply a single loop upto 10^5 only.
For(i=2;i<n;i++){
U[n]=U[n-2]-U[n-1];} where U[0]=100 and U[1]=97
Now we check nth number is positive or not with a conditional statement.

Solution:
http://ideone.com/cC1vRN
[1]: https://www.codechef.com/CDWR2016/problems/FEST10
[2]: http://www.codechef.com/users/vipinkhushu
[4]: http://www.codechef.com/users/sameer87
[5]: http://www.codechef.com/users/vipinkhushu
[3]: https://www.codechef.com/problems/FEST10

//