1824번 - 도미노 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 128 MB | 314 | 69 | 58 | 23.108% |
문제
각 칸에 번호가 붙어 있는 N×M 크기의 체스판이 있다. 이 판에는 몇 개의 선이 그러져 있는데, 각각의 선은 두 개의 서로 다른 칸의 경계에 그려진다. 예를 들어 아래의 체스판은 N=4, M=5이고, 9개의 선이 그려져 있는 모습이다.
이 체스판을 1×2 또는 2×1 크기의 도미노로 모두 덮으려고 한다. 단, 선으로 분리되어 있는 두 칸을 하나의 도미노로 덮을 수는 없다. 예를 들어, 위의 그림에서 1번 칸과 2번 칸은 하나의 도미노로 덮을 수 있지만, 6번 칸과 7번 칸은 하나의 도미노로 덮을 수 없다. 아래는 이와 같은 조건을 만족하면서 체스판을 모두 덮은 예이다.
입력
첫째 줄에 N과 M(1≤N, M≤100)이 빈 칸을 사이에 두고 주어진다. N과 M 중 적어도 하나는 짝수이다. 둘째 줄에는 선의 개수 L(0≤L≤5,000)이 주어진다. 이어서 L개의 줄에 걸쳐 선을 나타내는 두 개의 칸 번호가 빈 칸을 사이에 두고 주어진다. 이는 두 칸을 분리시키는 선이라는 의미이다. 번호는 N×M 이하의 자연수로 왼쪽으로부터 i번째, 위로부터 j번째 칸이 (j-1)×M+i 번이 된다.
출력
첫째 줄부터 N×M÷2개 줄에 도미노를 놓을 두 칸의 번호를 빈 칸을 사이에 두고 출력한다. 1×2 또는 2×1 크기의 도미노를 놓을 두 칸은 반드시 인접해 있어야 하며, 선으로 분리되어 있는 두 칸을 덮어서는 안 된다. 하나의 칸에 여러 개의 도미노를 놓아서도 안 되며, 반드시 모든 칸을 겹치지 않게 덮는 해를 출력해야 한다. 출력하는 순서는 상관이 없으며, 도미노를 놓는 방법이 둘 이상인 경우 그 중 한 경우만 출력한다.
예제 입력 1
4 5 9 8 7 13 14 14 19 6 7 12 7 4 9 12 13 14 9 9 10
예제 출력 1
3 4 1 6 2 7 8 9 5 10 14 15 11 16 12 17 13 18 19 20
힌트
출처
Olympiad > International Olympiad in Informatics > IOI 2005 > Practice 2번
- 문제를 번역한 사람: author5
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호