레이팅 미적용언제나처럼 편의상 \(1 \ldots N\)으로 번호가 매겨진 농부 존의 \(N\)마리 소들(\(2 \leq N \leq 100\))은 발굽 위의 시간이 너무 많이 남아돈다. 그 결과, 소들은 농부 존이 매일 아침 우유를 짜는 순서와 관련된 복잡한 사회 구조를 만들어 냈다. 몇 주간의 연구 끝에 농부 존은 이 구조가 두 가지 핵심 성질에 기반한다는 것을 발견했다.
첫째, 소들의 사회적 위계 때문에 일부 소들은 각 소의 사회적 지위 수준에 따라 다른 소들보다 먼저 착유되기를 고집한다. 예를 들어 소 3의 지위가 가장 높고 소 2가 평균 지위, 소 5가 낮은 지위라면, 소 3이 가장 먼저 착유되어야 하고, 그다음에 소 2, 마지막으로 소 5가 착유되어야 한다.
둘째, 일부 소들은 순서상의 특정 위치에서만 착유되는 것을 허락한다. 예를 들어 소 4는 모든 소들 중 두 번째로 착유되기를 고집할 수 있다.
다행히 농부 존은 항상 이 모든 조건을 만족하는 순서로 소들의 우유를 짤 수 있다.
안타깝게도 소 1이 최근 병에 걸려서, 농부 존은 이 소가 헛간으로 돌아가 꼭 필요한 휴식을 취할 수 있도록 가능한 한 순서상 이른 시점에 착유하고 싶다. 착유 순서에서 소 1이 나올 수 있는 가장 이른 위치를 구하도록 농부 존을 도와주자.
출제자: Jay Leeds
출제자: Jay Leeds
첫째 줄에 \(N\), \(M\) (\(1 \leq M < N\)), \(K\) (\(1 \leq K < N\))가 주어진다. 이는 농부 존에게 \(N\)마리의 소가 있고, 그중 \(M\)마리가 사회적 위계를 이루고 있으며, \(K\)마리가 순서상의 특정 위치에서 착유될 것을 요구함을 뜻한다. 다음 줄에는 서로 다른 정수 \(m_i\) (\(1 \leq m_i \leq N\)) \(M\)개가 주어진다. 이 줄에 나오는 소들은 이 줄에 나온 순서와 같은 순서로 착유되어야 한다. 다음 \(K\)개의 줄에는 두 정수 \(c_i\) (\(1 \leq c_i \leq N\))와 \(p_i\) (\(1 \leq p_i \leq N\))가 주어지며, 이는 소 \(c_i\)가 위치 \(p_i\)에서 착유되어야 함을 뜻한다.
이 제약 조건들 아래에서 농부 존이 유효한 착유 순서를 만들 수 있음이 보장된다.
착유 순서에서 소 1이 차지할 수 있는 가장 이른 위치를 출력한다.
milkorder.in · 출력을 쓸 파일 milkorder.out6 3 2
4 5 6
5 3
3 14In this example, Farmer John has six cows, with cow 1 being sick. He needs to
milk cow 4 before cow 5 and cow 5 before cow 6. Moreover, Farmer John has to
milk cow 3 first and cow 5 third.
FJ has to milk cow 3 first, and since cow 4 has to come before cow 5, cow 4 must
be milked second, and cow 5 third. Thus, cow 1 can be fourth at earliest in the
order.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > US Open > Bronze