알파카컵 3회: E - 알파카의 식량 생산

알파카 왕국에는 식량 생산을 담당하는 \(N \times M\) 크기의 목초지가 존재한다. 이곳의 풀들은 조금 특이하게 자란다.

풀이 존재하는 상태를 \(1\), 존재하지 않는 상태를 \(0\)이라 하자. 위치 \((i, j)\)의 초기 상태를 \(a_{i,j}\)라 했을 때, 그 다음 상태 \(p_{i,j}\)는 다음과 같이 정의된다.

$$ p_{i,j} = a_{i+1,j} \oplus a_{i-1,j} \oplus a_{i,j+1} \oplus a_{i,j-1} $$

여기서 \(\oplus\)는 XOR 연산자이다. 목초지 밖의 영역은 모두 풀이 존재하지 않는 것(\(0\))으로 간주한다.

해당 목초지를 운영하는 알파카 경현이는 식량 생산을 극대화하기 위해, 초기 상태의 풀을 적절히 배치하여 그 다음 상태에서 모든 칸에 풀이 존재하도록 만들고 싶다. 즉, 목초지 내 모든 위치 \((i, j)\)에 대해 \(p_{i,j} = 1\)이 되어야 한다.

효율적인 식량 생산을 위해 초기 상태에 배치하는 풀의 개수는 최소화해야 한다. 그 다음 상태의 모든 칸에 풀이 존재하도록 하는 최소 풀의 개수를 출력하는 프로그램을 작성하시오. 만일 해가 존재하지 않는다면 ALPACA SAD를 출력한다.

• \(1 \le N \le 10\)
• \(1 \le M \le 10^9\)

첫째 줄에 두 정수 \(N\)과 \(M\)이 공백으로 구분되어 주어진다.

해가 존재한다면 그 다음 상태의 모든 칸에 풀이 존재하도록 하는 최소 풀의 개수를 한 줄에 출력한다.

해가 존재하지 않는다면 ALPACA SAD를 출력한다.

pythonprominhyeong 작성

출처 알파카컵 3회