레이팅 미적용농장에서 생산하는 우유의 품질로 널리 이름난 농부 존이 가장 친한 친구 \(N\)명(\(1 \leq N \leq 50\))을 위해 우유 시음회를 열고 있다. 안타깝게도 시음회에 나온 \(M\)종류의 우유(\(1 \leq M \leq 50\)) 중 정확히 하나가 상해 버렸는데, 농부 존은 어느 것인지 알지 못한다! 상한 우유를 마신 사람은 파티가 진행되는 동안 또는 그 이후에 병이 나게 된다.
파티의 기록, 즉 누가 언제 무엇을 마셨는지와 누가 언제 병이 났는지가 주어진다. 이 정보를 바탕으로 어느 우유가 상한 우유일 수 있는지 추론할 수 있다. 이 지식을 활용하여, 파티 중이든 이후든 병이 나는 모든 사람을 반드시 치료할 수 있도록 보장하기 위해 농부 존이 구해 두어야 하는 약의 최소 개수를 결정하는 것을 도와주자.
Problem credits: Austin Anderson and Brian Dean
Problem credits: Austin Anderson and Brian Dean
입력의 첫째 줄에 정수 \(N\), \(M\), \(D\), \(S\)가 주어진다.
다음 \(D\)개의 줄(\(1 \leq D \leq 1000\))에는 각각 세 정수 \(p, m, t\)가 주어지며, 이는 사람 \(p\)가 시각 \(t\)에 우유 \(m\)을 마셨음을 의미한다. \(p\)는 \(1 \ldots N\) 범위, \(m\)은 \(1 \ldots M\) 범위, \(t\)는 \(1 \ldots 100\) 범위이다. 한 사람이 같은 우유를 여러 번 마실 수도 있고, 같은 시각에 여러 종류의 우유를 마실 수도 있다.
다음 \(S\)개의 줄(\(1 \leq S \leq N\))에는 각각 두 정수 \(p, t\)가 주어지며, 이는 사람 \(p\)가 시각 \(t\)에 병이 났음을 의미한다. \(p\)는 \(1 \ldots N\) 범위, \(t\)는 \(1 \ldots 100\) 범위이다. 각 사람은 최대 한 번 병이 나며, 엄밀히 더 이른 시각에 상한 우유를 마셨기 때문에만 병이 난다.
파티 중과 이후에 병이 나는 모든 사람을 치료하기에 충분한 약을 반드시 갖추도록 보장하기 위해 농부 존이 구해 두어야 하는 약의 최소 개수를 하나의 정수로 출력한다.
badmilk.in · 출력을 쓸 파일 badmilk.out3 4 7 2
1 1 1
1 4 1
1 3 4
1 2 2
3 1 3
2 1 5
2 2 7
1 3
2 83There are 3 people and 4 milk types. Person 1 gets sick at time 3
and person 2 gets sick at time 8. Person 3 does not get sick at the
party, although we may still need to consider the possibility that
he could become sick later, after the party ends. Let's consider
the milk types one by one to see which ones could be contaminated; we
know a milk type is potentially bad if everyone who became sick drank
that milk type before becoming sick.
Milk 1: Both of the sick people (1 and 2) drank this milk before
getting sick, so this could be the bad milk. If so, person 3 also
drank it, so it would cause a total of 3 people to get sick (person 3
would become sick after the party).
Milk 2: Both of the sick people drank this milk before getting
sick, so this could also be the bad milk. Nobody else drank this
milk, so at worst 2 total people could be sick if this is the bad
milk.
Milk 3: This cannot be the bad milk because person 1 did not drink
it before getting sick -- person 1 drank it at time 4, and got sick at
time 3. For milk 3 to be implicated in person 1 getting sick, person
1 would have needed to drink this milk by time 2 at the latest.
Milk 4: This cannot be the bad milk because person 2 did not drink
it, and yet person 2 became sick.
The answer is therefore that Farmer John must obtain 3 doses of
medicine, since if milk 1 is bad, then a total of 3 people will need
to be cured.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > December > Bronze