직소 퍼즐
시간 제한1초메모리 제한1024 MB
홈, 평평한 면, 돌기로 표시된 조각들로 직사각형 퍼즐을 만들 수 있는지 점점 엄격해지는 세 가지 기준으로 판정합니다.
문제
가능한 퍼즐 조각 (회전과 뒤집기가 가능함)
완성된 퍼즐 예시
같은 크기의 정사각형 빈 조각들로 퍼즐을 만들 수 있는가? 단, 가장자리 홈과 돌기의 개수와 위치는 따지지 않는다. 어떤 돌기든 어떤 홈에든 맞는다고 가정한다. 어느 면이든 위로 향하게 하여 임의로 회전할 수 있다. 그림의 네 자리 숫자는 홈의 구성을 나타낸다. '1'은 평평한 면, '0'은 홈이 있는 면, '2'는 돌기가 있는 면이다. 회전과 뒤집기를 고려하면 같은 조각을 나타내는 표현이 여러 개 있다. 예를 들어 1201 조각은 2011, 0112, 1120, 1021, 1102, 2110, 0211과 같은 조각이다.
이 문제는 퍼즐에 대한 일반적인 전제를 따른다. 각 조각은 네 개의 면을 가진다. 인접한 조각은 모두 맞물린다(퍼즐의 가장자리 외에는 평평한 면이 없다). 조각은 행과 열로 배열되어 빈틈없는 직사각형을 이룬다. 완성된 직사각형의 가장자리는 모두 평평한 면으로 이루어진다. 퍼즐은 보통 한 행이나 한 열로 만들어지지 않지만, 그럴 이유가 없으므로 이 경우도 허용한다.
이 문제는 결론을 확실히 내리기 어렵다. 그래서 점점 엄격해지는 다음 기준에 따라, 퍼즐을 만들 가능성이 있는지만 판단한다.
- 모든 조각을 사용해 직사각형 퍼즐을 만들 수 있는 유효한 조각 수가 있는가? 직사각형이 두 개 이상 가능할 수도 있다.
- 첫 번째 기준이 허용하는 어떤 크기의 직사각형 퍼즐이든 만들 수 있도록, 평평한 가장자리의 수와 모서리의 수, 모서리의 종류가 알맞은가?
- 첫 번째와 두 번째 기준이 허용하는 직사각형 퍼즐을 만들 수 있도록, 홈과 돌기의 수가 알맞은가?
입력
첫 줄에 퍼즐 조각의 개수를 나타내는 정수가 하나 주어진다. 이 값은 1000 이하이다. 이후 각 줄에는 조각 하나가 위에서 설명한 방식의 네 자리 숫자로 주어진다.
출력
세 질문에 대해 순서대로 "Yes", "No", "Unsolved" 중 하나를 출력한다. 각 답은 별도의 줄에 출력한다.