455B


  Posted on 05 Dec 2014
games trie

Tutorial


Trie can be implemented with a two dimentional array.

Solution


#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define D(x) x

const int MAX_CHAR_NUM = 30;
const int MAX_N = int(1e5) + 10;
const int MAX_NODE_NUM = MAX_N;

int trie[MAX_NODE_NUM][MAX_CHAR_NUM];
int node_num;

int n, round_num;
char st[MAX_N];
bool leaf;

void trie_init()
{
	memset(trie, -1, sizeof(trie));
	node_num = 1;
}

int convert(char ch)
{
	return ch - 'a';
}

void add(char* st)
{
	int u = 0;
	for (int i = 0; st[i]; i++)
	{
		int index = convert(st[i]);
		if (trie[u][index] == -1)
		{
			trie[u][index] = node_num++;
		}
		u = trie[u][index];
	}
}

void input()
{
	scanf("%d%d", &n, &round_num);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", st);
		add(st);
	}
}

bool dfs(int u)
{
	bool have_child = false;
	bool ret = false;
	for (int i = 0; i < 26; i++)
	{
		if (trie[u][i] != -1)
		{
			have_child = true;
			ret = ret || !dfs(trie[u][i]);
		}
	}
	if (have_child)
		return ret;
	return leaf;
}

void output()
{
	for (int i = 0; i < 24; i++)
	{
		for (int j = 0; j < 26; j++)
		{
			printf("%d ", trie[i][j]);
		}
		puts("");
	}
}

int main()
{
	trie_init();
	input();
	leaf = false;
	bool win = dfs(0);
	leaf = true;
	bool lose = dfs(0);
	if (win && lose)
	{
		puts("First");
	}else if (win && !lose)
	{
		if (round_num & 1)
			puts("First");
		else
			puts("Second");
	}else if (!win)
	{
		puts("Second");
	}
	return 0;
}