# CFR 455 B. A Lot of Games ( Game Theory + Trie )

Problem - 455B - Codeforces

```int N, K;
vs word;

void init(){
cin >> N >> K;
word = vs( N );
for( int i = 0; i < N; ++i )
cin >> word[ i ];
}

struct trie{
trie *ch[ 26 ];
trie(){
for( int i = 0; i < 26; ++i )
ch[ i ] = NULL;
}
friend void add( trie *&t, const string &s, int x ){
if( x == s.size() )
return;
if( t->ch[ s[ x ] - 'a' ] == NULL )
t->ch[ s[ x ] - 'a' ] = new trie();
add( t->ch[ s[ x ] - 'a' ], s, x + 1 );
}
} *root_trie;

int state; // 0 : win, 1 : controlable, 2 : uncontrolable, 3 : lose

int dfs( const trie *t ){
vi chstcnt( 4 ); // children state count
for( int i = 0; i < 26; ++i ){
if( t->ch[ i ] )
++chstcnt[ dfs( t->ch[ i ] ) ];
}
if( chstcnt[ 2 ] or ( chstcnt[ 0 ] and chstcnt[ 3 ] ) )
return 1;
if( chstcnt[ 3 ] )
return 0;
if( chstcnt[ 0 ] or ( chstcnt[ 0 ] + chstcnt[ 1 ] + chstcnt[ 2 ] + chstcnt[ 3 ] == 0 ) )
return 3;
return 2;
}

void preprocess(){
root_trie = new trie();
for( int i = 0; i < N; ++i )
add( root_trie, word[ i ], 0 );
state = dfs( root_trie );
}

void solve(){
if( state == 2 or state == 3 )
cout << "Second" << endl;
else{
if( state == 1 )
cout << "First" << endl;
else{
if( K & 1 )
cout << "First" << endl;
else
cout << "Second" << endl;
}
}
}
```