12173번 - N-오미노 판 채우기 (Large) 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 512 MB | 73 | 32 | 30 | 50.000% |
문제
N-오미노는 이차원 평면 위에 N개의 정사각형이 연결된 도형이다. 1-오미노는 1*1 크기의 정사각형이다. 그래서 n-노미노는 n - 1오미노에 1-오미노, 즉 1*1짜리 정사각형을 추가 한 것과 같다. 단, 두 N-오미노가 합동이면 같다고 가정한다.
아래에는 가능한 5가지 4-오미노가 있다.
아래에는 전체 108가지의 7-오미노 중 일부가 있다.
철수와 동수는 변수 X, R, C가 정해진 상태에서 아래의 절차대로 게임을 진행하려고 한다.
1.철수는 가능한 X-오미노 중에서 하나를 고른다.
2.동수는 여러 가지 X-오미노를 이용해서 넘치지도 부족하지도 않게 R*C 판을 채운다. 단, 철수가 고른 X-오미노를 적어도 한개를 이용해야 하며 X-오미노를 뒤집거나 회전하여 이용해도 된다. 동수가 위의 조건을 만족하면서 판을 채우면 동수는 승리하고 판을 채우지 못하면 패배한다.
X, R, C가 주어질때 철수가 무조건 이길지 동수가 무조건 이길지 판별하라.
입력
입력의 첫째 줄에는 테스트케이스의 수 T가 주어진다
다음 T개의 줄에서는 각각 X, R, C가 차례대로 주어진다.
1 ≤ T ≤ 100, 1 ≤ X, R, C ≤ 20
출력
각각의 테스트케이스에 대하여 "Case #x:y"를 출력한다. 이때 x는 테스트케이스 번호(1부터 시작한다). 철수가 선택했을때 무조건 이기는 X-오미노가 하나라도 있으면 y는 RICHARD이고 하나도 없으면 y는 GABRIEL이다.
예제 입력 1
4 2 2 2 2 1 3 4 4 1 3 2 3
예제 출력 1
Case #1: GABRIEL Case #2: RICHARD Case #3: RICHARD Case #4: GABRIEL
힌트
Case #1에서는 철수는 선택할 수 있는 2-오미노가 하나 밖에 없다--1*2짜리 직사각형. 2*2판은 1*2 직사각형 두개로 무조건 채울수 있으므로 동수 승!
Case #2에서도 철수는 선택할 수 있는 2-오미노가 하나 밖에 없다--1*2짜리 직사각형. 하지만 동수가 그 2-오미노를 어느것에 놓더라도 1*1이 하나 남으므로 철수 승!
Case #3에서 철수가 이길수 있는 방법은 2*2짜리 4-오미노를 선택하는 것이다. 1*4판에다가 2*2정사각형은 절대 넣을 수 없으므로 철수 승!
Case #4에서는 1*3짜리 3-오미노 또는 L모양으로 생긴 3-오미노를 선택해야 한다. 두 경우 모두 동수가 2*3판에 하나를 놓고 똑같은 모양 하나를 더 넣으면 되므로 동수 승!
출처
Contest > Google > Code Jam > Google Code Jam 2015 > Qualification Round D2번
- 문제의 오타를 찾은 사람: cheetose
- 문제를 번역한 사람: seanrocket17
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호