레이팅 미적용베시는 컴퓨터 과학 대학원에 지원하고 있으며, 명망 있는 컴퓨터 과학 연구실의 면접 기회를 얻었다. 그런데 누구의 기분도 상하게 하지 않기 위해, 베시는 그 연구실의 현재 구성원 \(N\)명(\(1 \leq N \leq 100\))의 상대적인 연차(선임 정도)를 파악하고 싶어 한다. 연구실의 어떤 두 구성원도 연차가 같지 않지만, 연차를 알아내는 것은 까다로울 수 있다. 이를 위해 베시는 연구실의 출판물들을 살펴보기로 했다.
각 출판물에는 저자 목록이 있는데, 이는 연구실 구성원 \(N\)명 전원의 순서 배열이다. 이 목록은 각 구성원이 논문에 기여한 노력의 내림차순으로 정렬되어 있다. 여러 연구자가 같은 정도의 노력을 들였다면 알파벳 순서로 정렬된다. 더 선임인 연구실 구성원은 추가적인 행정 업무가 있으므로, 더 선임인 연구자가 더 후임인 연구자보다 많은 노력을 들이는 일은 결코 없다.
예를 들어, 후임 학생 엘시, 그보다 선임인 밀드레드 교수, 매우 선임인 딘 교수로 이루어진 연구실에서, 셋이 모두 서로 다른 정도의 노력을 들였다면 (즉 엘시가 밀드레드보다, 밀드레드가 딘보다 많은 노력을 들였다면) (Elsie-Mildred-Dean) 순서의 논문이 있을 수 있다. 하지만 밀드레드와 딘이 같은 정도의 노력을 들이고 엘시가 더 많은 노력을 들였다면 (Elsie-Dean-Mildred) 순서의 논문도 있을 수 있다.
이 연구실의 출판물 \(K\)개(\(1 \leq K \leq 100\))가 주어질 때, 연구실의 모든 연구자 쌍에 대해 누가 더 선임인지 (판별이 가능하다면) 알아내는 것을 도와주자.
문제 제공: Dhruv Rohatgi
문제 제공: Dhruv Rohatgi
첫째 줄에 두 정수 \(K\)와 \(N\)이 주어진다.
둘째 줄에 공백으로 구분된 \(N\)개의 문자열이 주어지며, 이는 연구실 구성원들의 이름이다. 각 이름은 소문자로만 이루어지며 길이는 최대 10이다.
다음 \(K\)개의 줄에는 각각 공백으로 구분된 \(N\)개의 문자열이 주어지며, 이는 한 출판물의 저자 목록을 나타낸다.
출력은 \(N\)개의 줄로 이루어지며, 각 줄에는 \(N\)개의 문자가 있어야 한다. \(i\)번째 줄에서, \(j \neq i\)인 각 \(j\)에 대해 \(j\)번째 문자는 \(i\)번째 구성원이 \(j\)번째 구성원보다 확실히 선임이면 \(1\), 확실히 후임이면 \(0\), 주어진 출판물로는 판별할 수 없으면 \(?\)이어야 한다.
\(i\)번째 줄의 \(i\)번째 문자는 \(B\)이어야 하는데, 그것이 베시가 가장 좋아하는 글자이기 때문이다.
1 3
dean elsie mildred
elsie mildred deanB11
0B?
0?BIn this first example, the single paper (elsie-mildred-dean) does not give
enough information to determine whether Elsie is more senior than Mildred or
vice versa. However, one can deduce that Dean must be more senior than both, so
the seniority orderings Elsie<Mildred<Dean and Mildred<Elsie<Dean are both
possible.
2 3
elsie mildred dean
elsie mildred dean
elsie dean mildredB00
1B0
11BIn this second example, the only seniority ordering consistent with both papers
is Elsie<Mildred<Dean, since one can second paper builds on the knowledge from
the first example above and helps us deduce that Mildred is also more senior than
Elsie.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > US Open > Bronze