Anubhav has a crush on Anu. Therefore he likes the letters A,N and U the most.
He likes those strings which consists of only A N U
According to him, the strings containing A,N and U only are "LOVABLE" If they contain either of these patterns:
1) ANU
2) AUN
3) NAU
4) NUA
5) UAN
6) UNA
He asks you to find out how many LOVABLE strings are there of length N.
Note: Assume all strings are made of A,N,U. Consider all other alphabets as non-existent.
Input format: First line contains T the number of test cases. Next T lines contain a single integer N, denoting the length of string
Output format: Output the count of LOVABLE strings of length N in a single line for each test case
Constraints:
1<= T <= 30
1<= N <= 30
Solution :
// Online C++ compiler to run C++ program online
#include<bits/stdc++.h>
using namespace std;
class Solution{
int a = 1;
int n1 = 7;
int u = 3;
public :
int solve(int n , int pre , int pre_pre , int sum , bool x )
{
if(n ==0)
{
if(x)
return 1;
return 0;
}
long long result =0;
if(sum == a + pre + pre_pre )
{
result += solve(n-1 , a , pre , sum , true );
}
else
result += solve(n-1 , a , pre , sum , x);
if(sum == n1 + pre + pre_pre )
{
result += solve(n-1 , n1 , pre , sum , true );
}
else
result += solve(n-1 , n1 , pre , sum , x);
if(sum == u + pre + pre_pre )
{
result += solve(n-1 , u , pre , sum , true );
}
else
result += solve(n-1 , u , pre , sum , x);
return result;
}
int Loveable(int n )
{
if(n == 0 || n==1 || n==2)
{
return 0;
}
return solve(n , -1 , -1 , 11 , false);
}
};
int main() {
Solution s ;
int n = 4;
int x = s.Loveable(n);
cout << x << " "<<"\n";
}
|
The dynamic programming solution will be uploaded soon, Stay tuned.
Comments
Post a Comment