게임을 해보자!

대회 소개 글이다.

모두가 게임을 좋아한다! 게임은 새로운 여가의 시대를 열었고, 즐거움뿐 아니라 배움의 기회도 준다. 게임은 아이를 가르치고 필수 기술을 기르는 데 도움이 될 수 있다. 장르가 무궁무진해서 누구나 자신의 관심사에 맞는 게임을 찾을 수 있다.

사람마다 게임을 고르는 기준이 다르다. 전략과 기술이 가장 중요한 고전 보드게임을 좋아하는 사람이 있고, 여러 난이도에서 문제 해결 능력을 시험하는 퍼즐 게임에서 재미를 찾는 사람도 있다. 창의력과 코딩 실력이 최대한 시험받는 경쟁 프로그래밍에 빠진 사람도 있다. 무작위 요소가 전혀 없어서 실력과 전략만으로 승부가 갈리는 두 명용 게임을 선호하는 사람도 있다. 반면 확률 요소가 섞여 예측할 수 없는 긴장감을 즐기는 사람도 많다. 가볍게 즐기고 싶은 사람에게는 특별한 준비물 없이 바로 재미를 주는 간단한 게임이 알맞다. 최근에는 여럿이 함께하는 협력형 비디오 게임도 늘었다. 팀워크와 협업이 승리에 필수인 환경이다.

전략적 통제, 우연이 주는 설렘, 협력 플레이 중 무엇을 좋아하든 모든 취향에 맞는 게임 경험이 있다.

대부분의 게임 팬은 자신의 취향이 분명하다. 하지만 선택지가 너무 많아 길을 잃은 사람은 어떨까? 그런 사람이 자신에게 맞는 게임을 찾도록 어떻게 안내할 수 있을까? 이를 위해 플레이어를 이상적인 게임으로 이끄는 대화형 다이어그램을 만들어 보자.

여러 게임이 여러 평가 항목으로 평가된다고 하자. 게임 $i$의 점수를 벡터 $g_i = \{g_{i,j}\}$로 나타낸다. 여기서 $i$는 게임 번호, $j$는 항목 번호다.

플레이어가 항목별로 선호하는 값을 고르면 이를 벡터 $r = \{r_j\}$로 나타낸다. 각 게임 $i$에 대해 항목별 평점 차이의 최댓값 $d_i = \max_j |g_{i,j} - r_j|$를 계산한다. 플레이어에게 최적인 게임은 모든 게임 가운데 $d_i$가 가장 작은 게임 $i$다. 최소 $d_i$를 갖는 게임이 여럿일 수도 있다.

그러나 가장 알맞은 게임을 찾기는 어렵다. 과정을 단순하게 만들어 보자. 플레이어에게 "이것을 좋아하나요?" 또는 "저것을 싫어하나요?"처럼 예나 아니오로 답할 수 있는 질문을 차례로 던진다. 답에 따라 다음 질문으로 넘어가며, 가장 좋은 선택지가 드러날 때까지 이어간다.

선호는 사람마다 크게 다르므로 어떤 답이 와도 대비해야 한다. 따라서 과제는 완전한 결정 다이어그램을 설계하는 것이다. 각 노드는 게임 이름을 나타내는 종단 노드이거나, 플레이어의 평점에 관한 질문을 담은 중간 노드다. 중간 노드에는 "Yes" 방향과 "No" 방향의 두 경로가 있고, 각 경로는 서로 다른 노드로 이어진다.

다이어그램은 다음 제약을 따라야 한다.

1. 시작 노드는 정확히 하나여야 한다. 들어오는 링크가 없는 노드가 시작 노드다.
2. 모든 중간 노드는 "Yes"와 "No" 응답에 해당하는 나가는 링크를 정확히 두 개 가져야 한다.
3. 한 노드에서 나가는 두 링크는 서로 다른 노드로 향해야 한다. 또한 노드에서 자기 자신으로 가는 링크는 허용되지 않는다.
4. 질문은 "<category> <sign> <value>" 형식이어야 한다. 여기서
   • "<category>"는 평점 항목의 이름이다.
   • "<sign>"은 "<", ">", "=" 중 하나다.
   • "<value>"는 1부터 5까지의 정수다.
5. 항상 의미 없는 질문, 즉 평점이 1보다 작은지 또는 5보다 큰지를 묻는 질문은 허용되지 않는다.
6. 전체 노드 수는 350개를 넘을 수 없다.
7. 같은 게임을 가리키는 종단 노드가 여러 개이거나, 같은 조건을 검사하는 중간 노드가 여러 개인 것은 허용된다.
8. "Yes"와 "No" 레이블은 각각 문자 "Y"와 "N"으로 적는다. 레이블은 자신이 표시하는 노드와 나가는 링크 양쪽에 모두 인접해야 한다. 여기서 인접은 변을 공유하는 격자 칸을 뜻한다. 레이블의 위치는 노드에서 시계 방향으로 바로 다음에 있는 인접 칸이어야 한다. 또한 한 레이블이 둘 이상의 노드에 인접할 수 없다.
9. 주어진 평점에 대해 만들어진 경로를 따라가면 반드시 최적의 선택지 중 하나에 도달해야 한다. 달리 말해, 더 잘 맞는 다른 게임이 있어서는 안 된다.

입력은 평점 표다. 열은 평점 항목, 행은 게임을 나타내며, 칸에는 1부터 5까지의 평점이 들어 있다. 평점 숫자는 해당 항목 이름 바로 아래에 맞춰 정렬되어 있다. 연속된 열 사이에는 공백이 최소 한 칸 있다.

게임 수와 평점 항목 수는 각각 2개 이상 8개 이하다. 항목 이름에는 영문 대소문자가 들어갈 수 있다. 게임 이름에는 영문 대소문자, 숫자, 하이픈, 쉼표, 공백이 들어갈 수 있다. 이름의 앞뒤에는 공백이 없다. 게임 이름과 평점 항목 이름의 길이는 6자 이상 25자 이하다.

출력은 위에서 설명한 형식을 따르는 다이어그램이어야 한다. 행 수와 각 행의 열 수는 1,000을 넘을 수 없다. 각 노드는 다음 형식을 따라야 한다.

*--------*
| <text> |
*--------*

텍스트 앞뒤에는 공백이 정확히 한 칸씩 있어야 한다.

노드 사이의 연결에는 다음 문자를 쓴다.

• "/": 위에서 왼쪽, 또는 아래에서 오른쪽으로 이어지는 대각선 연결
• "\\": 위에서 오른쪽, 또는 아래에서 왼쪽으로 이어지는 대각선 연결
• "|": 위와 아래를 잇는 세로 연결
• "-": 왼쪽과 오른쪽을 잇는 가로 연결
• "+": 세로선과 가로선이 만나는 교차점. 두 선은 합쳐지지 않고 각자 제 길을 간다.

공백으로 둘러싸인 별표나 어디로도 이어지지 않는 링크처럼 불필요한 문자가 있으면 안 된다. 각 대각선 연결은 정확히 하나의 링크에서만 써야 한다.

두 번째 예제의 정답은 제공되지 않는다. 다만 대회 시스템의 "예제로 테스트" 기능으로 풀이를 시험해 볼 수 있다. 어떤 것이 허용되는지 확신이 없다면 예제로 직접 테스트해 보라.