하드코어 행맨
시간 제한2초메모리 제한1024 MB
각 질의마다 고른 문자 집합에 속하는 모든 위치가 주어질 때, 최대 7번의 질의로 숨겨진 소문자 문자열을 찾는 문제입니다.
문제
행맨(hangman)이라는 게임을 들어 본 적이 있을 것이다. 어릴 때 해 본 사람도 많을 것이다. 이 게임에서는 가능한 한 적은 추측으로 단어를 맞혀야 한다. 한 번의 추측에서 a처럼 문자 하나를 제시하면, 단어에서 a가 나타나는 모든 위치를 알 수 있다.
어려운 단어가 골라졌다면 추측이 꽤 많이 필요할 수 있다. 이 문제에서는 게임을 조금 바꾼다. 한 턴에 문자 하나만 추측하는 대신, 임의의 문자 집합을 한 턴에 추측할 수 있다. 그 결과 추측한 문자 중 하나를 포함하는 모든 위치가 주어진다.
단어가 'hangman'이고 첫 턴에 h, z, a 문자를 추측하면 1, 2, 6번 위치를 얻는다. 이 위치에 정확히 어떤 문자가 있는지는 여전히 모르지만, 세 문자 중 하나인 것은 확실하다.
최대 7번의 추측으로 숨겨진 단어를 찾아내는 것이 과제이다. 단어가 항상 올바른 영어 단어인 것은 아니며, 소문자 영문자로 이루어진 임의의 문자열일 수 있다.