A String Game
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.
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 wi, the i-th word in the dictionary.
For each test case, output a single line containing the name of the winner of the game.
Input: 3 codechef 2 code chef foo 1 bar mississippi 4 ssissi mippi mi ppi Output: Tracy Tracy Teddy
- 1 <= T <= 5
- 1 <= N <= 30
- 1 <= |S| <= 30
- 1 <= |wi| <= 30
- S and wi contain only characters 'a'-'z'
|Tags||dec10, easy, fushar|
|Time Limit:||0.188482 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.