소개 세션 조직 timer 20s memory 1024MB

Apricot Rules LLC가 조직 개편을 거친 뒤, \mathbf{M}명의 관리자(manager)와 \mathbf{N}명의 비관리자(non-manager)를 포함하는 새로운 대규모 팀이 구성되었다. 팀 내에는 서로 모르는 사람이 많기 때문에, 여러 차례의 소개 세션(introduction session)을 일정에 넣으려 한다. 우리는 어떤 팀원 쌍이 이미 서로를 알고 있는지 정확히 알고 있다.

소개 세션은 1분짜리 시간 슬롯(time slot)들로 구성되어 진행된다. 첫 번째 시간 슬롯은 오전 8:00에 시작해서 8:01에 끝난다. i번째 시간 슬롯은 8:00으로부터 i-1분 뒤에 시작해 8:00으로부터 i분 뒤에 끝난다. 각 시간 슬롯 동안 하나 이상의 소개 세션이 열릴 수 있다. 한 팀원은 한 시간 슬롯에서 최대 한 소개 세션에만 배정될 수 있다. 각 소개 세션은 정확히 3명의 팀원으로 이루어져야 한다: 배정된 관리자 a(반드시 관리자여야 함) 1명과, 나머지 두 사람 b, c(관리자/비관리자 모두 가능)이다. 소개 세션이 열리려면, 배정된 관리자 a가 b와 c를 모두 이미 알고 있어야 한다. 소개 세션이 끝난 뒤에는 b와 c도 서로를 알게 된 것으로 간주한다. 만약 b와/또는 c가 관리자라면, 둘을 모두 포함하는 미래의 소개 세션에서 그들 중 누구든 배정된 관리자가 될 수 있다.

팀원들 중 일부 쌍에 대해, 위 과정으로 결국 서로를 알게 되기까지 필요한 최소 시간을 알고 싶다. 혹은 그 과정으로는 서로를 알게 만드는 것이 불가능한지도 알고 싶다. 어떤 두 사람이 소개 세션이 시작되기 전부터 이미 서로를 알고 있다면, 그 최소 시간을 0분으로 정의한다.

여러 쌍을 동시에 다루지만, 우리는 각 쌍의 상황을 서로 독립적으로 고려한다. 즉, 어떤 쌍의 최소 시간은 그 쌍만을 위한 특정 소개 세션 구성에 따라 달라질 수 있다.