아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

질병

면접 대비

시간 제한2초메모리 제한512 MB

요약
각 검사가 어떤 균을 확인하며 결과가 양성인지 음성인지 주어질 때, 모든 균을 불가능, 반드시 존재, 판단 불가로 분류하고 결과가 모순이면 Incorrect를 출력한다.
난이도

보통10점 중 5점

유형
구현, 완전 탐색, 수학, 그리디
정답자
아직 제출이 없습니다

문제

바이틀란디아에 위험한 질병이 유행했다. 이 질병의 원인은 nn종류의 서로 다른 병원성 세균이다.

환자를 제대로 치료하려면 의사는 환자의 병이 정확히 무엇 때문에 생겼는지 알아야 한다. 이를 위해 환자는 mm개의 검사를 받는다. 각 검사는 특정 세균들의 존재 여부를 확인한다. 검사는 검사 대상 병원체 중 하나라도 환자의 혈액에 있으면 양성 결과를 낸다.

검사 결과를 바탕으로 의사가 각 세균에 대해 환자가 감염되었는지 알아내도록 도와라.

입력

첫째 줄에는 서로 다른 병원체의 수 nn (1≤n≤1001 \le n \le 100)과 검사의 수 mm이 주어진다. 다음 mm (1≤m≤10 0001 \le m \le 10\,000)개 줄에는 각각 n+1n + 1개의 수가 있다. 처음 nn개의 수는 이 검사가 어떤 병원체를 검출하는지 나타낸다. ii번째 수는 검사가 ii번째 병원체의 존재를 확인하면 1, 아니면 0이다.

줄의 마지막 수는 검사가 양성 결과를 냈으면 1, 아니면 0이다.

출력

입력 데이터가 모순이면 출력 파일에 <<Incorrect>> 한 줄만 출력한다. 그렇지 않으면 출력 파일에 세 줄을 출력한다. 각 줄은 세균의 수와 그 번호들을 나열하는 형식이다.

첫째 줄에는 질병의 원인이 될 수 없는 세균의 번호를, 둘째 줄에는 질병의 원인이라고 확실히 말할 수 있는 세균의 번호를, 셋째 줄에는 검사 결과로는 아무것도 단정할 수 없는 세균의 번호를 출력한다.

예제3

  1. 예제 1

    입력
    3 3
    1 0 0 0
    1 1 1 1
    0 1 0 0
    
    예상 출력
    2 1 2
    1 3
    0
    
  2. 예제 2

    입력
    2 2
    1 1 0
    1 0 1
    
    예상 출력
    Incorrect
    
  3. 예제 3

    입력
    2 1
    1 1 1
    
    예상 출력
    0
    0
    2 1 2