만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

초콜릿 쪼개기 게임

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

요약
N×M 초콜릿에서 두 사람이 번갈아 조각 하나의 가장자리가 아닌 행이나 열을 떼어 먹는다. 움직일 수 없는 사람이 지며, 최적으로 두었을 때 누가 이기는지 구한다.
난이도

보통10점 중 7점

유형
게임 이론, 동적 계획법
정답자
아직 제출이 없습니다

문제

서현과 현서는 N×MN \times M 격자 모양의 초콜릿을 쪼개 먹으려고 한다. 하지만 커다란 초콜릿을 쪼개는 일은 너무 지루해서 둘은 게임을 하기로 했다. 게임은 서현부터 시작하여 번갈아 턴을 진행한다. 자신의 턴이 되면 초콜릿 조각 중 하나를 고르고, 그 조각에서 가로줄 또는 세로줄 하나를 고른다. 단, 맨 위나 아래 가로줄, 또는 맨 왼쪽이나 오른쪽 세로줄은 고를 수 없다. 그다음 고른 줄을 먹고 조각을 나머지 두 조각으로 쪼갠다. 자신의 턴에 행동할 수 없는 플레이어가 진다. 초콜릿이 너무 커서 둘은 게임을 하는 것에도 지쳐버렸다. 둘 모두 최선의 전략을 쓴다면 누가 이기는지 구하라.

입력

초콜릿의 세로 길이 NN과 가로 길이 MM이 공백으로 구분되어 차례로 주어진다.

출력

서현이 이기면 sh를, 현서가 이기면 hs를 출력한다.

제한

1≤N,M≤1051 \leq N, M \leq 10^5

힌트

2×22 \times 2 조각은 쪼갤 수 없다. 3×33 \times 3 조각은 가운데 1×31 \times 3 줄을 먹어 1×31 \times 3 조각 두 개로 쪼개는 경우밖에 없다.

예제1

  1. 예제 1

    입력
    3 3
    
    예상 출력
    sh