CodeChef A String Game(SG)

A String Game   Problem code: ASTRGAME

Submit All Submissions

 

All submissions for this problem are available.

Teddy and Tracy like to play a game based on strings. The game is as follows. Initially, Tracy writes a long random string on a whiteboard. Then, each player starting with Teddy makes turn alternately. Each turn, the player must erase a contiguous substring that exists in the dictionary. The dictionary consists of N words.

Of course, the player that can't erase any substring in his turn loses the game, and the other player is declared the winner.

Note that after a substring R is erased, the remaining substring becomes separated, i.e. they cannot erase a word that occurs partially to the left of R and partially to the right of R.

Determine the winner of the game, assuming that both players play optimally.

Input

The first line contains a single integer T, the number of test cases. T test cases follow. The first line of each testcase contains a string S, the string Tracy writes on the whiteboard. The next line contains a single integer N. N lines follow. The i-th line contains a single string w_i, the i-th word in the dictionary.

Output

For each test case, output a single line containing the name of the winner of the game.

Example

Input:
3
codechef
2
code
chef
foo
1
bar
mississippi
4
ssissi
mippi
mi
ppi

Output:
Tracy
Tracy
Teddy

Constraints

• 1 <= T <= 5
• 1 <= N <= 30
• 1 <= |S| <= 30
• 1 <= |w_i| <= 30
• S and w_i contain only characters 'a'-'z'

SG博弈

#include <bits/stdc++.h>
using namespace std ;
const int N = 33 ;
bool check[N][N] ;
int sg[N][N] , vis[10010] ;
string s , word ;
int main() {
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    int _ , n ; cin >> _ ;
    while( _-- ) {
        cin >> s ; int slen = s.length() ;
        memset( check , false , sizeof check );
        memset( vis , 0 , sizeof vis);
        memset( sg , 0 , sizeof sg );
        cin >> n ;
        for( int i = 0 ; i < n ; ++i ) {
            cin >> word ; int wlen = word.length() ;
            for( int j = 0 ; j + wlen <= s.length() ; ++j ) {
                if( word == s.substr( j , wlen ) )
                    check[j][j+wlen] = true ;
            }
        }
        int cnt = 0;
        for( int len = 1 ; len <= slen ; ++len ) {
            for( int be = 0 ; be < slen ; ++be ) {
                cnt++ ; int ed = be + len ; if( ed > slen ) continue ;
                for( int i = be ; i < ed ; ++i ){
                    for( int j = i + 1 ; j <= ed ; ++j ) if( check[i][j] ){
                        vis[ sg[be][i]^sg[j][ed] ] = cnt ;
                    }
                }
                int z = 0 ;
                while( vis[z] == cnt ) z++;
                sg[be][ed] = z ;
            }
        }
        if( sg[0][slen] ) cout << "Teddy" << endl ;
        else cout << "Tracy" << endl ;

    }
}