codeforces

B. A Lot of Games

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players.

Given a group of n non-empty strings. During the game two players build the word together, initially the word is empty. The players move in turns. On his step player must add a single letter in the end of the word, the resulting word must be prefix of at least one string from the group. A player loses if he cannot move.

Andrew and Alex decided to play this game k times. The player who is the loser of the i-th game makes the first move in the (i + 1)-th game. Guys decided that the winner of all games is the player who wins the last (k-th) game. Andrew and Alex already started the game. Fedor wants to know who wins the game if both players will play optimally. Help him.

Input

The first line contains two integers, n and k (1 ≤ n ≤ 105; 1 ≤ k ≤ 109).

Each of the next n lines contains a single non-empty string from the given group. The total length of all strings from the group doesn't exceed 105. Each string of the group consists only of lowercase English letters.

Output

If the player who moves first wins, print "First", otherwise print "Second" (without the quotes).

Examples

input

2 3
a
b

output

First

input

3 1
a
b
c

output

First

input

1 2
ab

output

Second

题意：有n（n<=100000）个单词，两个人比赛，规则为：最开始字符串为空，两人轮流每次填一个字母，使该字符串为这n个单词其中一个的前缀，当一个人不能再填入字母时，他就输了，比赛进行k次，第k次比赛胜者为最终胜者。
思路：最开始毫无思路，跟着别人的题解走了一遍。将所有单词构建一颗字典树,再进行博弈。第一道博弈和字典树。1表示先手败，2表示先手胜，3表示能胜能负。先手必败则，先手一直先手，最后一局后手胜；先手胜则下一局成后手，即为胜败交替，此时，最后一句的胜败决定于k的奇偶性；能胜能败，则先手前k-1局败，最后一句先手且胜。简单博弈。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<malloc.h>

using namespace std;

#define maxn 100005

char s[maxn];

//int next[maxn][30],root,top;

struct Trie

{

    Trie *next[];

};

Trie* createtrie(char *str,Trie* root)    //创建字典树

{

    int len=strlen(str);

    Trie *p=root,*q;

    for(int i=; i<len; i++)

    {

        int id=str[i]-'a';

        if(p->next[id]==NULL)

        {

            q=(Trie *)malloc(sizeof(Trie));

            //q->v=1;

            for(int j=; j<; j++)

                q->next[j]=NULL;

            p->next[id]=q;

            p=p->next[id];

        }

        else

        {

            //p->next[id]->v++;

            p=p->next[id];

        }

    }

    //p->v=-1;

    return root;

}

int solve(Trie *root)    //博弈

{

    int ok=,ans=;

    for(int i=; i<; i++)

    {

        if(root->next[i]!=NULL)

        {

            ok=;

            ans|=solve(root->next[i])^;

        }

    }

    if(!ok)

        ans=;

    return ans;

}

int main()

{

    int n,k;

    //top=root=1;

    Trie* root;

    scanf("%d%d",&n,&k);

    root=(Trie*)malloc(sizeof(Trie));

    for(int j=; j<; j++)

            root->next[j]=NULL;

    for(int i=; i<n; i++)

    {

        scanf("%s",s);

        root=createtrie(s,root);

    }

    //output(root);

    int tmp=solve(root);

    //cout<<tmp<<endl;

    if(tmp==)

        printf("First\n");

    else if(k&&&tmp==)

        printf("First\n");

    else

        printf("Second\n" );

    return ;

}

巴特西

codeforces_455B

最新文章

热门文章