교집합과 격자판
문제 설명
크기가 인 집합 의 서로 다른 부분집합은 총 개 존재한다.
여러분에게 크기의 격자판이 주어진다. 격자판의 각 행에는 의 서로 다른 부분집합이 하나씩 겹치지 않게 배정되어 있다. 격자판의 각 열에 대해서도 마찬가지이다.
격자판의 각 칸은 다음과 같은 조건을 만족하면 색칠되고, 만족하지 않으면 색칠되지 않는다.
- 칸이 위치한 행에 배정된 부분집합과 열에 배정된 부분집합의 교집합이 공집합이 아니다 (즉, 두 집합의 공통 원소가 존재한다).
격자판의 초기 상태는 오른쪽에 주어져 있다. 여러분은 오른쪽 격자판을 왼쪽 격자판과 같이 만들어야 한다. 즉, 왼쪽 격자판에서 색칠된 칸은 오른쪽 격자판에서도 색칠되어 있어야 하며, 왼쪽 격자판에서 색칠되지 않은 칸은 오른쪽 격자판에서도 색칠되어 있지 않아야 한다.
기능
오른쪽 격자판에서 현재 각 행과 열에 배정된 부분집합이 무엇인지 확인할 수 있다. 집합의 각 원소는 서로 다른 색으로 표시되어 있다.
오른쪽 격자판에서 서로 다른 두 행을 연속해서 클릭하면 두 행에 배정된 부분집합을 서로 바꿀 수 있다. 열에 대해서도 마찬가지이다. 아래 그림은 크기의 격자판에서 두 행과 두 열에 배정된 부분집합을 서로 바꾸는 예시를 보여준다.
두 격자판에서 같은 행 또는 같은 열을 두 번 연속해서 클릭하면 그 행 또는 열을 밝게 표시할 수 있다. 다시 두 번 연속해서 클릭하면 원래대로 돌아간다. 아래 그림은 크기의 격자판에서 몇 개의 행과 열을 밝게 표시하는 예시를 보여준다.
오른쪽 격자판의 칸에 마우스를 올리면 칸이 위치한 행에 배정된 부분집합과 열에 배정된 부분집합의 교집합이 무엇인지 확인할 수 있다.
제출 버튼을 누르면 격자판의 현재 상태가 저장된다. 만약 여러분이 오른쪽 격자판의 모든 칸을 왼쪽 격자판과 같이 만들었다면 만점을 받는다.
주의사항
만약 오른쪽 격자판을 왼쪽 격자판과 같이 만드는 방법이 여러 가지라면, 그 중 어떠한 방법을 선택해도 좋다.
최소 횟수로 교환할 필요는 없다.
오른쪽 격자판의 모든 칸을 왼쪽 격자판과 같이 만들었다면, 반드시 제출 버튼을 눌러 제출해야 한다.
문제 형식
출처
- KOI 2023 1차대회 고등부 1교시 20번
