NTERM-Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Rajendra Prajapat
Tester: Amitabh Paliwal
Editorialist: Rajendra Prajapat

DIFFICULTY:

EASY

PREREQUISITES:

simple-DP knowledge

PROBLEM:

Given a series, where T0,T1 = 1 and T2,T3 = 2 else Tn = Tn+2 -Tn-2 where n >=4. Find Nth term.

QUICK EXPLANATION:

Tn = Tn+2 -Tn-2 can be written as Tn = Tn-2 + Tn-4 then it can be solved easily.

EXPLANATION:

Tn = Tn+2 -Tn-2
Tn+2 = Tn + Tn-2
Tn = Tn-2 + Tn-4

T0 = 1
T1 = 1
T2 = 2
T3= 2

This problem has two subtasks.
Subtask 1 can be solved easily by brute-forcing but subtask 2 can not be, because (number of test cases)*N is very long, which requires more time, but the time limit is only 0.5 seconds. So instead of calculating each term again and again, first we calculate all the values up to 10 5 and store in an array, then for each test-case just print the value from the array.

SOLUTIONS:

Setter's Solution 
#include<iostream>
using namespace std;
int f[100005];
void setup()
{
    for(int i=0;i<100000;i++)
    {
        if(i<=1)
        {
             f[i] = 1;
         }
         else if(i>1 and i<=3)
         {
              f[i] = 2;
          }
          else
          {
              f[i]= (f[i-2]%1000000007 + f[i-4]%1000000007)%1000000007;
          }     
    }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  setup();
  int t;
  cin>>t;
  while(t--)
  {
    int n;
    cin>>n;
    cout<<f[n]<<endl;
  }
}