A1024 | Contaminated Milk--Bronze
来源USACO
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Farmer John, known far and wide for the quality of the milk produced on his
farm, is hosting a milk-tasting party for $N$ of his best friends ($1 \leq N
\leq 50$). Unfortunately, of the $M$ types of milk featured at the party ($1
\leq M \leq 50$), exactly one of them has gone bad, but Farmer John does not
know which one! Anyone who drinks the bad milk will later become sick, either
during the remainder of the party or afterward.
You are given a transcript of the party -- who drinks what when, and also who
gets sick when. Based on this information, you can deduce which of the milks
could possibly be the bad one. Using this knowledge, help Farmer John
determine the minimum number of doses of medicine he will need to obtain in
order to guarantee that he can cure all of the individuals who become sick,
either during or after the party.
farm, is hosting a milk-tasting party for $N$ of his best friends ($1 \leq N
\leq 50$). Unfortunately, of the $M$ types of milk featured at the party ($1
\leq M \leq 50$), exactly one of them has gone bad, but Farmer John does not
know which one! Anyone who drinks the bad milk will later become sick, either
during the remainder of the party or afterward.
You are given a transcript of the party -- who drinks what when, and also who
gets sick when. Based on this information, you can deduce which of the milks
could possibly be the bad one. Using this knowledge, help Farmer John
determine the minimum number of doses of medicine he will need to obtain in
order to guarantee that he can cure all of the individuals who become sick,
either during or after the party.
输入格式
The first line of the input contains integers $N$, $M$, $D$, and $S$.
The next $D$ lines ($1 \leq D \leq 1000$) each contain three integers $p, m,
t$, indicating that person $p$ drank milk $m$ at time $t$. The value of $p$ is
in the range $1 \ldots N$, $m$ is in the range $1 \ldots M$, and $t$ is in the
range $1 \ldots 100$. A person may drink the same milk several times, and may
also drink several types of milk at the same point in time.
The next $S$ lines ($1 \leq S \leq N$) each contain two integers $p, t$,
indicating that person $p$ gets sick at time $t$. The value of $p$ is in the
range $1 \ldots N$, and $t$ is in the range $1 \ldots 100$. Each person gets
sick at most once, and they only get sick because they drank the bad milk at
some strictly earlier point in time.
The next $D$ lines ($1 \leq D \leq 1000$) each contain three integers $p, m,
t$, indicating that person $p$ drank milk $m$ at time $t$. The value of $p$ is
in the range $1 \ldots N$, $m$ is in the range $1 \ldots M$, and $t$ is in the
range $1 \ldots 100$. A person may drink the same milk several times, and may
also drink several types of milk at the same point in time.
The next $S$ lines ($1 \leq S \leq N$) each contain two integers $p, t$,
indicating that person $p$ gets sick at time $t$. The value of $p$ is in the
range $1 \ldots N$, and $t$ is in the range $1 \ldots 100$. Each person gets
sick at most once, and they only get sick because they drank the bad milk at
some strictly earlier point in time.
输出格式
A single integer, specifying the minimum number of doses of medicine Farmer
John needs to obtain so that he can guarantee that he will have sufficiently
many doses to treat all the people who become sick, both during and after the
party.
John needs to obtain so that he can guarantee that he will have sufficiently
many doses to treat all the people who become sick, both during and after the
party.
输入输出样例
输入 #1
3 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 8
输出 #1
3
There 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.
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.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted