곰곰이와 테트리스
시간 제한2초메모리 제한1024 MB
두 사람이 N×M 보드에 테트리스 블록이나 1×1 블록을 번갈아 놓아 점수를 겨룹니다. 선공의 0.5점 감점을 적용해 승자를 구합니다.
문제
곰곰이와 총총이가 재미있는 테트리스 게임을 하려고 한다.
테트리스 게임은 세로 칸, 가로 칸인 빈 직사각형 게임판에서 시작한다.
곰곰이부터 번갈아 가며 원하는 테트리스 블록 또는 1×1 블록을 빈 공간에 하나씩 배치한다.
블록은 회전시켜 배치할 수 있지만 뒤집을 수는 없다. 기존 블록과 겹치거나 격자와 테두리를 벗어나게 배치해서는 안 된다.
[그림 1] 배치할 수 있는 블록의 종류와 번호
각 플레이어는 블록을 배치할 때마다 그 블록 종류에 정해진 점수를 얻는다.
게임판에 더 이상 블록을 배치할 수 없게 되면 게임이 끝나고, 최종 점수로 승패를 가린다.
동점을 막기 위해 곰곰이는 선공 페널티로 최종 점수에서 0.5점을 뺀다.
두 사람이 최적의 방법으로 게임을 진행했을 때, 최종 점수가 더 높은 사람이 누구인지 출력하자.
테트리스 블록과 1×1 블록은 종류마다 개수가 무한하므로 블록이 떨어지는 경우는 없다고 가정한다.
입력
첫째 줄에 게임판의 크기 이 주어진다.
둘째 줄에 [그림 1]에 표시된 번호에 해당하는 블록의 점수 8개 가 차례대로 주어진다.
입력은 모두 양의 정수로 주어진다.
출력
곰곰이가 이기는 경우에는 GomGom, 총총이가 이기는 경우에는 ChongChong을 출력한다.