Menu Close

Unique set of characters that occur in string one or more times…[Cprogm]FTC

For a string S let the unique set of characters that occur in it one or more times be C. Consider a permutation of the elements of C as (c1,c2,c3…). Let f(c) be the number of times c occurs in S.

If any such permutation of the elements of C satisfies f(ci)=f(ci−1)+f(ci−2) for all i≥3, the string is said to be a dynamic string.

Mr Hardik is given the task to check if the string is dynamic, but he is busy playing with sandpaper. Would you help him in such a state?

Note that if the number of distinct characters in the string is less than 3, i.e. if |C|<3, then the string is always dynamic.

Input:
First line contain T, number of testcases. Then the testcases
Each testcase contains of a single line of input, a string S.

Output:
For each testcase, output print "Dynamic" if the given string is dynamic, otherwise print "Not". (Note that the judge is case sensitive)
#include <stdio.h>
#include <string.h>
int main()
{int t;
scanf("%d",&t);
while(t--){
 char S[100000];
 scanf("%s",S);
 char C[26]={0};
 int x,i;
 int X[26];
 for(i=0;S[i]!='\0';i++){
 x=S[i]-'a';
 C[x]++;
 }
 int count=0,j=0;
 for(i=0;i<26;i++){
 if(C[i]!=0){
 X[j]=C[i];
 count++;
 j++;
 }
 }
 if(count<3){
 printf("Dynamic\n");
 continue;
 }
 int round,temp,flag;
 for(round=1;round<=count-1;round++){
 flag=0;
 for(i=0;i<=count-1-round;i++){
 if(X[i]>X[i+1]){
 flag=1;
 temp=X[i];
 X[i]=X[i+1];
 X[i+1]=temp;
 }
 }
 if(flag==0)
 break;
 }
 int yo=0;
 for(i=count-1;i<count;i++){
 if(X[i]!=X[i-1]+X[i-2]){
 yo=1;
 break;
 }
 }
 if(yo==1){
 printf("Not\n");
 flag=1;
 }
 else printf("Dynamic\n");
}
return 0;
}

INPUT_1:
2
ffffgff
ggttrr

OUTPUT:
Dynamic
Not


INPUT_2:
5
hthehth
feeeefe
tttyyyt
uuuiuii
ccyycci

OUTPUT:
Not
Dynamic
Dynamic
Dynamic
Not


ILLUSTRATION

Executed using gcc