아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

막대기 게임

시간 제한1초메모리 제한512 MB

요약
장애물이 있는 격자에 주어진 길이의 가로 막대를 겹치지 않게 놓으며 최적으로 둘 때 승자를 구한다.
난이도

보통10점 중 6점

유형
게임 이론, 구현
정답자
아직 제출이 없습니다

문제

영선이와 효빈이가 이번 컨테스트를 연다. 둘뿐이라 대회 스태프까지 겸하지만, 소규모 대회라서 실제 대회처럼 풍선을 달아 줄 일도 없고, 사고만 없으면 할 일이 거의 없다.

그래서 대회 동안 딴 짓으로 할 게임을 하나 준비했다. 이름은 막대기 게임이고 규칙은 다음과 같다.

  1. n×mn \times m 크기의 격자판이 있다.
  2. 일부 칸에는 장애물이 있고, 그 칸에는 막대기를 놓을 수 없다.
  3. 주어진 길이마다 1×p1 \times p 막대기가 무한히 있다.
  4. 두 사람이 번갈아 막대기를 하나 골라 원하는 위치에 놓는다.
  5. 더 놓을 곳이 없는 사람이 진다.
  6. 막대기는 겹쳐 놓을 수 없고, 돌릴 수도 없다.

막대기를 돌릴 수 없으므로 길이가 pp인 막대기는 한 행에서 가로로 연속한 빈 칸 pp개를 차지한다.

위 그림처럼 막대기를 놓을 수 있다.

두 사람은 생각할 시간이 넉넉해서 언제나 최적으로 둔다. 게임은 항상 영선이가 먼저 시작한다. 게임판이 주어졌을 때 이기는 사람의 아이디를 출력한다.

입력

첫째 줄에 nn과 mm이 주어진다. (1≤n,m≤10001 \le n, m \le 1000)

다음 nn개의 줄에는 길이가 mm인 문자열이 주어져 게임판의 각 행을 나타낸다. 빈 칸은 ., 장애물은 @이다.

다음 줄에 막대기 종류의 수 kk가 주어진다. (1≤k≤10001 \le k \le 1000)

다음 줄에 kk개의 정수 p1,p2,…,pkp_1, p_2, \dots, p_k가 오름차순으로 주어진다. (1≤pi≤10001 \le p_i \le 1000) pip_i는 ii번째 종류의 막대기 길이다.

출력

영선이가 이기면 nein을, 효빈이가 이기면 hyo123bin을 출력한다.

예제3

  1. 예제 1

    입력
    2 3
    .@.
    ...
    3
    1 2 3
    
    예상 출력
    nein
    
  2. 예제 2

    입력
    1 1
    @
    1
    1
    
    예상 출력
    hyo123bin
    
  3. 예제 3

    입력
    1 1
    .
    1
    1
    
    예상 출력
    nein