소 접촉자 추적

전염성이 매우 강한 소 질병 COWVID-19가 발생한 후, 농부 존은 (여느 때처럼 \(1 \ldots N\)으로 번호가 매겨진) 소들의 건강을 걱정하고 있다.

최근 농부 존은 모든 소를 검사했고, 그중 일부가 이 병에 양성인 것을 발견했다. 헛간 내부의 영상 기록을 이용해 그는 소들 사이의 최근 상호작용을 검토할 수 있다. 알고 보니 소들은 서로 인사할 때 발굽을 맞잡는데, 이 동작이 안타깝게도 한 소에서 다른 소로 감염을 퍼뜨릴 수 있다. 농부 존은 상호작용한 소 쌍들의 시각이 기록된 목록을 만들었는데, 각 항목은 \((t, x, y)\) 형태로, 시각 \(t\)에 소 \(x\)가 소 \(y\)와 발굽을 맞잡았다는 의미이다. 농부 존은 다음 사실들도 알고 있다.

(i) 농장에서 처음에 병을 지니고 있었을 수 있는 소는 정확히 한 마리이다(이 소를 "최초 감염자"라고 부르자).

(ii) 소는 일단 감염되면 그다음 \(K\)번의 발굽 맞잡기에서 감염을 옮긴다(같은 상대 소가 여러 번 포함될 수도 있다). 발굽을 \(K\)번 맞잡은 후에는 이후의 발굽 맞잡기에서 더 이상 감염을 옮기지 않는다(이 시점에 자신이 감염을 퍼뜨리고 있다는 것을 깨닫고 발굽을 깨끗이 씻기 때문이다).

(iii) 소는 일단 감염되면 계속 감염된 상태로 남는다.

안타깝게도 농부 존은 \(N\)마리의 소 중 어느 소가 최초 감염자인지도, \(K\)의 값도 알지 못한다! 그의 데이터를 바탕으로 이 미지수들의 가능한 경우를 좁히도록 도와주자. 적어도 하나의 가능성이 유효함이 보장된다.

문제 제공: Brian Dean

문제 제공: Brian Dean

입력 파일의 첫째 줄에 \(N\)(\(2 \leq N \leq 100\))과 \(T\)(\(1 \leq T \leq 250\))가 주어진다. 다음 줄에 농부 존의 소 \(N\)마리의 현재 상태를 나타내는, 0과 1로 이루어진 길이 \(N\)의 문자열이 주어진다. 0은 건강한 소를, 1은 현재 병에 걸린 소를 나타낸다. 다음 \(T\)개의 줄 각각에 농부 존의 상호작용 목록의 기록 하나가 세 정수 \(t\), \(x\), \(y\)로 주어진다. \(t\)는 상호작용이 일어난 양의 정수 시각(\(t \leq 250\))이고, \(x\)와 \(y\)는 시각 \(t\)에 발굽을 맞잡은 소들을 나타내는 \(1 \ldots N\) 범위의 서로 다른 정수이다. 각 시점에는 많아야 하나의 상호작용만 일어난다.

세 정수 \(x\), \(y\), \(z\)를 한 줄에 출력한다. \(x\)는 최초 감염자였을 수 있는 소의 수, \(y\)는 데이터와 모순되지 않는 \(K\)의 최솟값, \(z\)는 데이터와 모순되지 않는 \(K\)의 최댓값이다(데이터로부터 유추할 수 있는 \(K\)의 상한이 없으면 \(z\) 자리에 "Infinity"를 출력한다). \(K=0\)일 수도 있음에 주의한다.

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Bronze