# KCC04 - EDITORIAL

DIFFICULTY:
EASY

PREREQUISITES:
Dynamic Programming , Fibonacci Series

PROBLEM:
We have to find number of ways in which an N day plan for gym can be executed given that we can not go to the gym on more than one consecutive days.

Quick Explanation:
We can clearly observe the pattern to be a Fibonacci series and using DP we can compute the N day plan from 1 <= N <= 10^8.

Explanation:

``````The plan can be shown as :

0 : Did not went to the gym on a day
1 : Went to gym on a day
Plan[i] : Number of ways of going to gym on i th day

Plan[1] = 2 (He goes on first day or he does not go on that day as 0 or 1)
Plan[2] = 3 (He can go by 3 ways as 00,10,01)
Plan[3] = 5

and so on...

hence on clear observation we can see that :
Plan[i] = Plan[i-1] + Plan[i-2];

We can compute the Plan array earlier by DP with a complexity of O(10^8) for 1<=N<=10^8

Pseudo Code :

Plan[1]=2;
Plan[2]=3;
for i in range 3 to N:
Plan[i] = Plan[i-1] + Plan[i-2];

Now we can give the answer to each query in O(1) time hence total complexity for T queries can be O(T).

Result = Plan[N]  for N day plan.

Time Complexity : O(T+10^8) where T<=60000 hence it can be O(10^8)
``````

Editorialistâ€™s Solution:
Can be found here.