시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1537 | 469 | 298 | 25.297% |
위대한 수학자 김선영은 선형대수학 교과서를 집필하는 과정에서 다음과 같은 문제를 만들었다.
\(N\times N\)행렬 \(A\)에 대해 다음 명제들이 동치임을 증명하라:
이런 문제를 해결하는 일반적인 방법은 일련의 함축(implication)을 이용하는 것이다.
예를 들어, 선영이의 예시 답안은
(a)이면 (b)이고, (b)이면 (c)이며 (c)이면 (d)이고, 마지막으로 (d)이면 (a)이다. 이 네 함축은 네 가지 명제가 동치임을 보여준다.
라고 되어있다.
다른 방법으로는 (a)이면 (b)이고, (b)이면 (a)이므로 (a)와 (b)가 동치라고 증명한 다음,
같은 방식으로 (b)와 (c)가 동치임을 증명하고, 마지막으로 (c)와 (d)가 동치임을 증명하는 방법이 있다.
하지만 이건 무려 여섯 번의 함축을 필요로 한다.
선영이는 선형대수학 책을 집필하는 과정에서 수없이 많은 명제가 동치임을 증명해야 하기 때문에 이러한 비효율성은 치명적이다.
선영이가 다음 학기 시작 전에 교재를 모두 집필할 수 있도록 되도록이면 적은 수의 함축을 이용해서 명제가 동치임을 증명할 수 있도록 도와주자.
첫 번째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 100)가 주어지고,
각 테스트 케이스에 대해서는 다음과 같은 입력이 주어진다:
각 테스트 케이스마다 한 줄을 출력한다:
2 4 0 3 2 1 2 1 3
4 2
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2008 B번