30959번 - 앙상블할래?

서울사이버대학교 인공지능학과 개설을 기념하여, 노교수와 천교수는 학생들에게 이진 분류 인공지능 모델을 각자 하나씩 개발해 오라는 과제를 내줬다. 개발된 모델들의 성능을 평가하던 중, 두 교수는 모델들을 결합하여 앙상블 기법으로 성능을 향상시킬 수 있는지 궁금해졌다. 앙상블은 여러 모델의 결과를 조합하는 방법론으로, 이번에는 각 예측 항목마다 더 많은 모델이 출력한 값을 최종 결과로 채택하는 하드 보팅 앙상블을 사용해 보기로 했다. 이 문제에서는 앙상블 시 홀수 개의 모델만을 선택한다고 가정한다.

예를 들어, 6개의 예측 항목에 대한 정답이 $[0, 1, 0, 1, 1, 0]$이고, 네 학생의 모델 예측 결과가 아래와 같이 주어진다고 하자.

• 1번 학생: $[1, 0, 0, 1, 1, 0]$
• 2번 학생: $[0, 1, 1, 1, 1, 0]$
• 3번 학생: $[0, 1, 0, 0, 0, 0]$
• 4번 학생: $[0, 0, 1, 0, 1, 0]$

이 모델들 중 1번 학생, 2번 학생, 4번 학생의 모델을 선택해 하드 보팅으로 앙상블했을 때의 결과는 $[0, 0, 1, 1, 1, 0]$이며, 하나하나 살펴보면 다음과 같다.

• 첫 번째 예측 항목: $0$은 두 번, $1$은 한 번 나왔으므로 최종 예측은 $0$
• 두 번째 예측 항목: $0$은 두 번, $1$은 한 번 나왔으므로 최종 예측은 $0$
• 세 번째 예측 항목: $0$은 한 번, $1$은 두 번 나왔으므로 최종 예측은 $1$
• 네 번째 예측 항목: $0$은 한 번, $1$은 두 번 나왔으므로 최종 예측은 $1$
• 다섯 번째 예측 항목: $0$은 없고, $1$은 세 번 나왔으므로 최종 예측은 $1$
• 여섯 번째 예측 항목: $0$은 세 번, $1$은 없으므로 최종 예측은 $0$

이렇게 앙상블한 결과를 정답과 비교하여 정확도를 계산한다. 이 경우 6개 항목 중 4개가 일치하므로 정확도는 $\frac{4}{6}$다.

만약 정확도가 가장 뛰어난 하나의 모델만 선택했을 때보다 더 높은 정확도를 가지는 앙상블 조합이 존재할 경우, 앙상블로 성능을 향상시킬 수 있다고 판단한다. 그러한 조합이 있는지 확인하라.

첫 번째 줄에 모델의 수 $N$와 예측 항목의 수 $M$이 주어진다. $(1 \le N \le 16;$ $1 \le M \le 100)$

두 번째 줄에 $M$개의 각 예측 항목에 대한 정답이 순서대로 주어진다.

세 번째 줄부터 $N$개의 줄에 걸쳐 각 모델의 예측 결과 $M$개가 순서대로 주어진다.

정답과 예측 결과는 모두 $0$ 또는 $1$로만 구성되며, 공백으로 구분되어 주어진다.

첫 번째 줄에 하드 보팅 앙상블로 가장 정확도가 높은 단일 모델의 정확도를 뛰어넘는 조합이 있다면 1을, 그렇지 않다면 0을 출력한다.