문자열 집합으로 접두사를 늘려가는 게임을 k번 반복하며 매번 진 사람이 다음 게임을 시작할 때, 마지막 게임의 승자를 판정한다.
어려움8트라이게임 이론DFS동적 계획법아직 제출이 없습니다시간 제한2초메모리 제한512 MBAndrew와 Alex가 두 명이서 하는 게임을 만들었다. 규칙은 다음과 같다.
Andrew와 Alex는 시간이 아주 많아서 이 게임을 k번 반복하기로 했다. i번째 게임에서 진 사람이 i+1번째 게임에서 먼저 플레이한다. 마지막 게임에서 이긴 사람을 최종 승자로 하기로 둘은 합의했다.
두 플레이어가 모두 최적으로 플레이할 때 마지막 게임에서 이기는 사람이 누구인지 구하는 프로그램을 작성하시오.
첫 줄에 그룹에 포함된 문자열의 개수 n과 진행하는 게임의 수 k가 주어진다 (1≤n≤100000, 1≤k≤109).
다음 n개의 줄에 그룹에 포함된 비어 있지 않은 문자열이 한 줄에 하나씩 주어진다. 문자열은 알파벳 소문자로만 이루어지고, 모든 문자열의 길이의 합은 100000을 넘지 않는다.
첫 번째 게임에서 먼저 플레이하는 사람이 마지막 게임에서 이기면 First를 출력한다. 나중에 플레이하는 사람이 마지막 게임에서 이기면 Second를 출력한다.